In this post I will cover the concepts of an AVL tree, including balancing methods and the idea behind the rotations. Also a full implementation in C++, so make sure you reach the end of the post before rambling between the google search tabs you’re likely opened already!

Binary Search Trees – BST

When speaking of BST, we simply refer to your average and humble binary tree with one additional property to it: the value of right child of any node have a value which is larger than the value of its parent, also, the left child, has a value less than the value of its parent, as well.

To wrap it all up in a nice way:
     (r)
     / \
   (L) (R)
(L) < (r) < (R)

Balanced Tree

The theoretical definition of a balanced tree, is a tree which has a height of O(log(n)) where n is the number of vertices that the tree has. Although this might not say much to you right now, however, it plays a major role of making AVL trees special. So, please carry on reading.

For the sake of this section, let’s go ahead and define what is  exactly the Balance Factor(BF):
Firstly, it’s a property for each node in the tree, means, each node has its own balance factor, Why? well, it’s because the balance factor is defined as:
BF(node) = height(node->left) - height(node->right) Where height() is a function that returns the height of the tree which root is the node that was passed as an argument to the function. Now, the definition of an AVL tree, is a tree where each and every node’s balanceFactor ranges between 1 and -1, means that if there is a node which BF = 2 or -2, then the tree lost the AVL property..

Since the mathematical proof is somewhat interesting, I will encourage you to read the proof. Unless you’re a hardcore bad-ass, please spare this part for a potential geek!

Rotations

So…why the hell should we rotate the living shit out of an AVL?

Other than this is a good question(horrible syntax :O ), when you insert or delete a node from the tree, the height of the tree changes. More specifically, there is a node which balance factor is now equals to -2 or 2 along the path to which we added or deleted the node. Now, in order to preserve the property of height=O(log(n)) , We need to rotate/adjust the distribution of the nodes to accomplish the following:

  1. Regain the property of being an AVL tree
  2. Preserve the fact that the tree is BST ( left nodes < root < right nodes)

Note that if the balance factor = -2, means that the height of the right > height of the left, thus, think of it as “Right Heavy”! Similarly, when the balance factor = 2, then it’s “Left Heavy”.

Now, we want everything to be balanced, in other words, we don’t want one side to be “heavier” than the other side. Of course, you already guessed that when we have “left heavy” we need to perform a rotation to the right in order to balance the “weight”, right? That is the correct intuition, take your time to grasp it before you carry on for a crazy part.

Every-time we encounter a node with a balance factor of 2 or -2, always check the other two sons(the left and right sons). Now consider the following scenario:

  1. The node is left heavy(with BF = 2) and it’s son is also left heavy(with BF = 1) : in this case, perform a rotation to the right on the node with BF = 2. Well call this case LL.
  2. Same as ‘LL’ case, however, this time the node and its son are right heavy, therefore, perform a left rotation on the node with BF = -2. We’ll call this case RR.
  3. This time, it’s quit different. Say, the node with BF = 2(aka left heavy, right?) but the son is right heavy(with BF = -1). In this case we’ll perform a left rotation for the right-heavy son, then a right rotation to the left-heavy node. We’ll call this an LR.
  4. Symmetric to ‘LR’, so try to figure it yourself, it’ll be a good exercise as we’ll. Also, it’s completely logical to call this on  RL.

Code

I’ll not post the FULL code here, rather I would encourage you to check it on my GitHub
However, i included here the code of the rotations:

/* Balancing the given node.*/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::balance(Node&amp;amp;lt;T&amp;amp;gt;* node) {
if (getBalanceFactor(node) == 2) {
if (getBalanceFactor(node-&amp;amp;gt;leftSon) &amp;amp;gt;= 0) {
node = LL(node);
} else if (getBalanceFactor(node-&amp;amp;gt;leftSon) == -1) {
node = LR(node);
}
} else if (getBalanceFactor(node) == -2) {
if (getBalanceFactor(node-&amp;amp;gt;rightSon) &amp;amp;lt;= 0) {
node = RR(node);
} else if (getBalanceFactor(node-&amp;amp;gt;rightSon) == 1) {
node = RL(node);
}
}
return node;
}
/***************************************************************/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::RR(Node&amp;amp;lt;T&amp;amp;gt;* node) {
return rotateLeft(node);
}
/***************************************************************/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::LL(Node&amp;amp;lt;T&amp;amp;gt;* node) {
return rotateRight(node);
}
/***************************************************************/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::LR(Node&amp;amp;lt;T&amp;amp;gt;* node) {
if (node) {
node-&amp;amp;gt;leftSon = rotateLeft(node-&amp;amp;gt;leftSon);
node = rotateRight(node);
}
return node;
}
/***************************************************************/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::RL(Node&amp;amp;lt;T&amp;amp;gt;* node) {
if (node) {
node-&amp;amp;gt;rightSon = rotateRight(node-&amp;amp;gt;rightSon);
node = rotateLeft(node);
}
return node;
}
/***************************************************************/
/*Perform a right rotation to the given node*/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::rotateRight(Node&amp;amp;lt;T&amp;amp;gt;* node) {
if (!node) {
return NULL;
}
Node&amp;amp;lt;T&amp;amp;gt;* temp = node-&amp;amp;gt;leftSon;
node-&amp;amp;gt;leftSon = temp-&amp;amp;gt;rightSon;
temp-&amp;amp;gt;rightSon = node;
updateHeight(node);
updateHeight(temp);
return temp;
}
/***************************************************************/
/*Perform a left rotation to the given node*/
template&amp;amp;lt;typename T&amp;amp;gt;
Node&amp;amp;lt;T&amp;amp;gt;* AVL&amp;amp;lt;T&amp;amp;gt;::rotateLeft(Node&amp;amp;lt;T&amp;amp;gt;* node) {
if (!node) {
return NULL;
}
Node&amp;amp;lt;T&amp;amp;gt;* temp = node-&amp;amp;gt;rightSon;
node-&amp;amp;gt;rightSon = temp-&amp;amp;gt;leftSon;
temp-&amp;amp;gt;leftSon = node;
updateHeight(node);
updateHeight(temp);
return temp;
}

Thank you for being interested in an amazing concept ~

Advertisements