Another Self-Balancing BST explained step by step
In this post, I will go over the process of building AVL tree.
If you walked through the earlier Red-Black Post, I promise you this one only takes you 5 mins to digest (it’s much simpler) 🙂
the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. from wiki
Let’s start with the Insertion process.
This is the first and only node. nothing to do.
2 nodes on the tree. root node left and right tree height difference is 1, it is still balanced.
Of course, the same as other auto-balance binary search trees, the insertion position is done by binary search.
Oops, the problem happens. the tree is not balanced anymore. right tree height=3 however left tree height=1. left rotation(center node=2) happens (will explain details below). for now, let’s call this as “Case #1”
Still balanced. continue.
“Case #1” happens again. so we just apply the same rotation fix (will explain later).
Now Tree is not balanced anymore. however, if you look carefully, it is still “Case#1”(Left rotation, center=12)
Rotation(left rotate, center node=13; right rotate, center node=14) needs to happen, and this seems to be a new case. let’s call it “Case#2” (left-right rotation)
still balanced. continue.
You can see the imbalanced point happened. which is a new case (Case#3). yes, here we apply right rotation(center node 2) to fix it. (since this is reverse of Case#1)