We use rotations.
RotationsVisual representation of what will happen with our nodesThere are 4 possible rotations we may need to do, depending on the “balance factors” of our nodes.
“Balance factor” is the same thing as “difference” from the tables above.
The 4 rotations we can have are left, right, left-right, and right-left rotations.
Let’s take a look at some very basic examples of each.
This tree is right-heavy, so we rotate it left.
Node “1” has a balance factor of -2, so it is an unbalanced BST.
Since it is right-heavy, we rotate left to balance it.
Node “1” becomes the left child of “2”, and 3 remains the left child of “1”.
Now let’s look at the mirror case, a left-heavy tree requiring a right rotation.
Node “3” becomes the right child of node “2”, node “1” remains the left child of node “2”.
Simple enough.
But let’s look at a more complex example.
What if we need to make a rotation where we are moving nodes around that have children of their own?Before node “16” was inserted, this was a balanced tree.
Now that we’ve added “16”, the balance factor of node “8” is -2, so we must perform a left rotation.
“12” will become the parent of “8”, but “12” already has two children.
AVL trees are BSTs, so we need to figure out what to do with the two children.
We know that node “10” is greater than node “8”, since “10” is in the right subtree of “8".
We also know that it is less than node “12”, since it is in the left subtree of “12”.
Because of these two facts, we can make it the new right child of “8”.
This is the resultant tree:This is now a balanced tree.
The same works for the mirror case.
We may need to break off a child and attach it to the opposite side of the subtree.
So that covers single rotations.
As mentioned before, there are also left-right and right-left rotations.
Again, let’s begin with some very simple cases.
Here we can’t just make “1” the root, because “2” is the right child, but “3” is also greater than “1”, so it would also needs to be on the right subtree of “1”, but that would still be an unbalanced tree.
So what we do is first we rotate “2” to the left, giving it the left child of “1” and making it the left child of “3”.
This gives us the following tree:Now we can rotate right and end up with the balanced tree.
Right-left rotation is just the mirror case of this.
Rotate right:Rotate left:So those are the 4 types of rotations that will be required to balance an AVL tree after inserting a new node.
Searching an AVL tree is the exact same as searching a BST, since AVL trees are BSTs.
We look at a node, if it matches, we can return it.
If the value is less than the node, we check the left child, and if the value is greater, we check the right child.
Repeat until we find our node or reach the bottom of our tree.
In the next article we will look at implementation of search and insertion for an AVL tree, but before we get there, let’s think about some of the variables we will have to keep track of based on what we just went over.
Just as we do with BSTs, we need to keep track of left and right children of each node, as well as the values.
With AVL trees, however, we need to keep a few more things in mind.
We need the height of each node in order to calculate the balance factor.
We also need to keep a pointer to each parent node, as rotations will require parents to become children of whichever node we are pivoting around.
I will leave it here, and hope you have learned something and can appreciate the value of AVL trees.
.