AVL Trees & Where To Find (Rotate) Them

AVL Trees & Where To Find (Rotate) Them

Ordinary binary search tree. Nobody cares for these. Source: [Self]

to this:

So much better! Source: [Self]

Two different properties will be added to my BST constructor: a link to the parent node, and a height method. The height of a tree is the longest path from root node to any leaf node. In this post, we will be working exclusively with inserting nodes, and rotating nodes when the AVL rules are violated.

AVL Rules

1. A tree is height-balanced when the heights of its child trees differ by at most 1.

2. The balance factor is defined as an integer in the range of [-1, 1] where -1 will be an extra node on the right child tree, and 1 is an extra node on the left child tree, accounting for an odd number of nodes.

3. A tree is considered unbalanced when the balance factor falls outside that range, and nodes undergo rotations to rebalance the tree. There are 4 different categories of rotations: left-left, left-right, right-right, and right-left.

4. The resulting height of the tree is then log2(n), which will make traversal time O(log2(n)).

Now, looking at those rules, you might be wondering: why do I care? Why go through all of this extra effort just to make a tree look more like its namesake?

With smaller data sets, the lookup time for a regular tree and a balanced tree is similar, but when your data sets become thousands of nodes deep, or even tens of thousands, suddenly the range of possibility is at best O(lg n) and at worst O(n), or that of traversing a linked list. With a balanced BST, you can always guarantee O(lg n) lookup time in both average and worst-case scenarios. I like guarantees.

The Visual Logic

Let?s take a look at the initial example of creating a BST of 20 as its root (Step 1), and then inserting the following: [15, 25, 10, 7]

The rules for a BST are as follows: if the value is less than or equal to the root move to the left, else move to the right.

The first insertion (Step 2) will place 15 to the left of 20.

The only parent is 20, whose height will be 1, and balance factor is 1.

These second insertion (Step 3) will place 25 to the right of 20.

The only parent is 20, whose height is 1, and balance factor is 0.

The third insertion (Step 4) places 10 to the left of 15.

15 has a height of 1, and balance factor of 1. 20 has a height of 2 and a balance factor of 1.

The fourth insertion (Step 5) places 7 to the left of 10.

10 has a height of 1 and balance factor of 1. 15 has a height of 2, and a balance factor of 2. Unbalanced!

Step 5 has now violated the rule of an AVL tree. The resulting situation forces nodes to rotate. When the root node (15) is unbalanced, and its left side is longer than the other. The rotation will come from the side that is longer ? the left side. The root?s left node (10) is known as the ?pivot? node. This node will determine whether the rotation will be right or left depending on whether it has a balance factor of 1. If it has a balance factor of 1, then the left side is longer than the right, and this situation is known as a left-left, for the left node as a pivot, and the longer left side, which will force a right rotation. The root node will move to the pivot node?s right side, and the pivot node will be directly attached to the rest of the tree. If the pivot node had a right side, it will move to the root node?s left.

The same situation but mirrored is known as a right-right, causing a left rotation.

The other 2 scenarios are left-right and right-left. There will be 2 resulting rotations instead of 1, as explained below:

The opposite situation is if 14 were placed instead of 7 in Step 5.

10 has a height of 1 and balance factor of -1. 15 has a height of 2, and a balance factor of 2. Unbalanced!

Now the ?pivot? node has a balance factor of -1, which is going to cause a left rotation using the pivot node as the root node, and its right node as the pivot. Once that is complete, the second rotation is a right rotation with the original root node and the new pivot node. Both of these rotations have already been defined above. The mirrored situation results in the right-left rotations.

These are the general rules of an AVL tree in particular. There are many other methods to a height-balanced tree, and even algorithms to optimize the height of the tree over a given amount of time.

Now let?s dive into Javascript.

Code Base Logic:

To determine the height of a tree, a recursive function defined as BinarySearchTree.prototype.height returns -1 if the root is null, and otherwise sums the maximum of the tree?s left and right sub-tree heights + 1. The code is defined below:

BST height function. Source: [https://gist.github.com/sarahzhao25/41fa7849acce3b679050273498b229da]

With the height method available, I can then determine the balance factor of each of my successive parent nodes after the insertion of a leaf node as the difference of the two, defined as BinarySearchTree.prototype.balanceFactor:

BST balanceFactor function. Source: [https://gist.github.com/sarahzhao25/88cb4f27cbb2e1f666fb5aa67c60291d]

Part 1: Insertion of a leaf node:

The code block of the insert prototype method takes the new value, and performs a recursive call until it hits a node with no corresponding right/left. After inserting the node, it performs this function on the node, now aliased as root:

Utility function taking in the ?root? to determine the need for rotation. Source: [https://gist.github.com/sarahzhao25/1baa9f5bbb80df6dfdf0b5f1ca8b3093]

Walking through this: if the root?s balance factor is outside of the balance range, it will need to be rotated. Otherwise, until the root no longer exists, this function will recursively check the parent node.

Part 2: Establishing the rotation process:

The idea here is that the nodes will either move left or right (imagine a 45 degree diagonal plane for this) depending on the status of its balanceFactor. The 4 rotations take into account the possible positions of unbalanced situations: the first two consider whether the unbalanced situation has extra nodes on the left or right side, and then consider the same situation for the designated pivot node.

Source: [https://gist.github.com/sarahzhao25/98821a090fa9726f6083eaece757dd18]

Note that because the balanceFactor is >0 or <0, there is automatically going to be a child node on either side, so there is no need to verify if there exists a left or right root.

Part 3: Rotating nodes:

Now that we have been able to establish the direction of the rotation, we can perform the rotation itself. I have generated an example of a rightRotate method to be clear, but since there exists a mirrored method for leftRotate, I also have implemented a generalized method rotateChoice that accounts for both situations. Today, we will walk through the rightRotate method for clarity.

Source: [https://gist.github.com/sarahzhao25/41c26587c000a5f9393fbe6db73f363d]

Here, we need to understand that a BST has the following in its constructor:

Source: [https://gist.github.com/sarahzhao25/345f520cd9d2e7355a66f14e96ccbf41]

And note that the BST rotation requires a pivot node in addition to the root node from the first portion of our talk.

Let?s walk through the workflow.

We are on Step 5 of inserting into the tree, and we have hit our first unbalanced scenario: we?ve inserted 7 into the tree, but now our tree?s balanceFactor is out of range. As we perform checkAndRotateRoots up the tree from the leaf node, we find the following:

7 has a height balance of 0, 10 has a height balance of 1, and 15 has a height balance of 2, breaking the rule on the left side.

So on 15, we will need to perform rotate.

Now, we have to check the pivot node, which is the tree on 15?s left (10), whose height balance indicates an extra node on the left side. This results in 1 rotation: a left-left situation results in a right rotation on the root, as per our diagram.

Now comes the fun part: rotation and re-assignment! Here is what that particular branch looks like, individual node-wise:

Tree view. Source: [https://gist.github.com/sarahzhao25/7822547cea10d741709f899d1754a6b3]

As we can see, there are several links between each node that we have to be careful of when disconnecting and reconnecting links.

In order to perform a right rotation, the root node (15) will move to the right, and its pivot node (10) will take its place. This will re-establish the following:

The pivot node?s parent is now going to be the parent node (20), and the parent node?s new left is going to be the old pivot node. The pivot node?s right will be the old root node, and the old root node?s parent will be the pivot node, or new root node. The old root node?s left will now be null. If the new root node initially had a right child, that would have become the old root node?s left. This takes care of all of the relationships included.

This is as seen below:

Establishing NEW connections. Source: [https://gist.github.com/sarahzhao25/5da550a5c0358ac083b25c71c10e38d9]

The same will apply for a left rotation. For left-right and right-left rotations, each of the 2 rotations apply the same logic.

For this particular scenario, a BST is defined with a root value. This current application will rotate the tree, and the diagram of the tree will be rendered as such. However, should the tree need to rotate its root node, the tree itself will remain the same, except that the root node will now be off-center. There are other ways to approach creating a BST where we start with an empty tree, and insert values with a pointer to the root node.

Thank you, and please let me know if you have any questions!

Sarah

Sources:

  • Introduction to Algorithms 3rd Edition by Cormen, Leiserson, Riverst, & Stein
  • CS241 ? Lecture Notes: Self-Balancing Binary Search Tree: [https://www.cpp.edu/~ftang/courses/CS241/notes/self%20balance%20bst.htm]
1

No Responses

Write a response