AVL TREES

A binary search tree can be constructed in any way based on the values of nodes being added to it. And there can be many cases where the tree can be unbalanced. Such a case is shown above, if the tree is constructed from the values, 5 2 7 9 11 13.

What happens if a tree is unbalanced?

If a tree is unbalanced, it shows that storage and retrieval of data from our data structure is not efficient as per the use cases.

The first and foremost reason to use a binary tree over linked list is its ability to efficiently search, insert or delete in O(log n) time.

If the balanced property of a binary tree fails, it’ll not be as efficient as it could be, or it could be very inefficient in practical sense.

How do we exactly know when tree is unbalanced?

We find out the height difference between the left subtree and the right subtree, not just for the root node, but for every single node.

Balance = H[L] - H[R]

To put simply, the height difference between the left deepest leaf node and the right deepest leaf node should not be greater than one, and not just for root, but for every internal node.

How does height determine the balancing factor of the tree?

The height of a left subtree will find the left deepest leaf node, and the height of a right subtree will find the right deepest leaf node. Together, they show us how many levels have to be visited before reaching the end. Then the tree is said to be balanced when the number of levels visited across the left and right subtree are nearly same, with an acceptable difference of one.

Acceptable Height Difference = H [ 1, 0, -1 ]

A perfectly balanced node will have height difference as zero, because we are calculating the difference between how many levels do we have to visit to reach the leaf node that is farthest from our node at both the left and the right sides. And if that is equal to zero, that means the level for both the deepest leaf nodes at left and right subtrees are same.

If the height difference for our node is one, then the leaf node at left side is one level deeper than the leaf node on the right side, and the subtree from that node is said to be left heavy.

If the height difference for our node is minus of one, then the leaf node at right side is one level deeper than the leaf node on the left side, and the subtree from that node is said to be right heavy.

Height difference is obvious to be calculated for all the internal nodes, because the leaf nodes have no children, so height difference of leaf nodes is always zero, or perfect balance.

Let us see an example,

The first tree is balanced, as the height difference is not more than one, and the difference between the levels of the leaf nodes at both sides are also same.

The second and three tree is badly unbalanced, where one seems to be left-heavy and other looks like right-heavy. It can also be clearly seen that the difference of levels between leaf nodes are also more than one, apart from the height difference. It clearly needs balancing.

If the tree is unbalanced such as the example below,

what could be the possible solution?

SELF BALANCING BINARY TREES

Let us see an example, we have to construct a binary tree from the keys 30, 20, 10. There can be 3! = 6 ways to construct it. However, out of these, two ways are balanced, and other four are unbalanced.

30, 20, 10

balanced ways

unbalanced ways

The first unbalanced tree is left-left heavy, the second unbalanced tree is left-right heavy, and third unbalanced tree is right-left heavy, and the last unbalanced tree is right-right heavy.

Every node having a left and right child will have four unbalanced binary trees, so there will be four ways to balance it, as each of the four unbalanced ways are unique.

ROTATIONS

Rotations are done only on three nodes whatever the size of a binary search tree may look like. We adjust them by performing rotations in such a way that the unbalanced way of that node is converted to a balanced way.

How do we find out those three nodes?

A balanced tree can become unbalanced while insertion or deletion takes place. In either of the cases, the node’d be inserted or deleted at a particular place, based on the property of binary search trees.

From the place of insertion or deletion, when the caller goes back to its ancestor parent nodes from where the function was called, the parent node also checks for its own height difference before returning to the next caller, it happens upto root node.

If the height difference of any caller [ancestor nodes of the inserted or deleted node] is greater than 1 or less than -1, then we are sure that unbalancing has occurred at that particular node itself, and not the entire tree.

Since unbalancing has occurred only at that node, we can rotate its structure taking its two child nodes to make it a balanced node.

How to know which way to rotate?

When the height difference of the ancestor nodes is greater than 1, that clearly shows left heavy unbalancing, for which rotation can be left-left or left-right depending on the structure.

And when the height difference of the ancestor nodes is less than -1, that clearly shows right heavy unbalancing, for which rotation can be right-right or right-left depending on the structure.

LEFT LEFT ROTATION

How do we find out the left-left case?

1. The parent node has the height difference of +2 or more

2. The child node has a positive or zero height difference

LL case:

bf(parent) == +2
bf(parent.left) >= 0

How to code?

Step 1 ~ We first store the address of child node’s right subtree in a temporary node. Here, in this case, it’s t3

Step 2 ~ Make the right of child node point to the parent node’s address directly

Step 3 ~ Make the parent’s left node point to the initial temporary node

Step 4 ~ Return the child node to the caller which is an ancestor of the parent node

Code:

Node t3 = child.right;

child.right = parent;

parent.left = t3;

return child;

LEFT RIGHT ROTATION

How do we find out the left-right case?

1. The parent node has the height difference of +2 or more

2. The child node has a negative height difference

LR case:

bf(parent) == +2
bf(parent.left) < 0

How to code?

Step 1 ~ We store the left of grandchild node t2 in a temporary node

Step 2 ~ We make grandchild of left point to child node

Step 3 ~ We make the left of parent node point of grandchild

Step 4 ~ We make the right of child point to t2 temporary node

Step 5 ~ Call the function of left-left rotation on parent node

Node t2 = child.right.left; // Step 1

child.right.left = child; // Step 2

parent.left = child.right; // Step 3

child.right = t2; // Step 4

return rightRotate(parent); // Step 5

(LL rotation)

RIGHT RIGHT ROTATION

How do we find out the right-right rotation?

1. The parent node has the height difference of -2 or less

2. The child node has a negative or zero height difference

RR Case:

bf(parent) == -2
bf(parent.right) <= 0

How to code?

Step 1 ~ Store left of child node in a temporary node

Step 2 ~ Make left of child point to the parent node

Step 3 ~ Make right of parent node point back to temporary node

Step 4 ~ Return the child node to the caller which is an ancestor of the parent node

Node t2 = child.left; // Step 1

child.left = parent; // Step 2

parent.right = t2; // Step 3

return child; // Step 4

RIGHT LEFT ROTATION

How do we find out the right-left rotation?

1. The parent node has the height difference of -2 or less

2. The child node has a positive height difference

RL Case:

bf(parent) == -2
bf(parent.right) > 0

How to code?

Step 1 ~ Store right of grandchild t3 in temporary node

Step 2 ~ Make right of grandchild point to child node

Step 3 ~ Make parent point to the grandchild node

Step 4 ~ Make left of child equal to stored t3 temporary node

Step 5 ~ Call the function of right-right rotation on parent node

Node t3 = child.left.right; // Step 1

child.left.right = child; // Step 2

child.left = t3; // Step 3

parent.right = child.left; // Step 4

return leftRotate(parent); // Step 5

(RR rotation)

AVL TREES IMPLEMENTATION IN C

#include <stdio.h>
#include <stdlib.h>
typedefstructNode {
int val;
structNode* left;
structNode* right;
} Node;
voidinitialize(int e, Node* root){
root->val = e;
root->left = NULL;
root->right = NULL;
}
voiddisplay(Node* root){
if(root == NULL){
return;
}
display(root->left);
printf("%d ", root->val);
display(root->right);
}
Node* createNode(int e){
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->val = e;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
intheight(Node* root) {
if (root == NULL)
return0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (leftHeight > rightHeight)
return leftHeight + 1;
else
return rightHeight + 1;
}
Node* leftleftcase(Node* root){
Node* child = root->left;
Node* t3 = root->left->right;
root->left->right = root;
root->left = t3;
return child;
}
Node* leftrightcase(Node* root){
Node* t2 = root->left->right->left;
root->left->right->left = root->left;
root->left = root->left->right;
root->left->left->right = t2;
return leftleftcase(root);
}
Node* rightrightcase(Node* root){
Node* child = root->right;
Node* t2 = root->right->left;
root->right->left = root;
root->right = t2;
return child;
}
Node* rightleftcase(Node* root){
Node* t3 = root->right->left->right;
root->right->left->right = root->right;
root->right = root->right->left;
root->right->right->left = t3;
return rightrightcase(root);
}
Node* insert(int e, Node* root){

if(root == NULL){
return createNode(e);
}

if(e < root->val){
root->left = insert(e, root->left);

} elseif(e > root->val){
root->right = insert(e, root->right);

} else {
return root;
}

int heightdiff = height(root->left) - height(root->right);

if(heightdiff >= 2){

// left cases
heightdiff = height(root->left->left) - height(root->left->right);

// height of left child
if(heightdiff >= 0){
root = leftleftcase(root);
} else {
root = leftrightcase(root);
}

} elseif(heightdiff <= -2){

// right cases
heightdiff = height(root->right->left) - height(root->right->right);

// height of right child
if(heightdiff <= 0){
root = rightrightcase(root);
} else {
root = rightleftcase(root);
}

}

return root;
}
intmain(){

Node* root = NULL;

int e, scan;
printf("Enter number of elements: ");
scanf("%d", &e);

for(int i = 0; i < e; i++){
scan = i;
root = insert(scan, root);
}

printf("In-order traversal: ");
display(root);

printf("\nMax Height: %d\n", height(root));

return0;
}

OUTPUT

Our AVL Tree has been implemented amazingly ! What we did is inserted nodes in ascending order, like 1..2..3.. which would normally create a very long right skewed binary search tree, but our avl tree has efficiently balanced it.

On inserting 50 nodes, the max height is just 6, which is ( log 50 to the base 2 ), max height will be 6 upto 64 nodes.

On inserting 100 nodes, max height is just 7, means 2^7 = 128, so total of 128 nodes can be stored at a height of 7.

On inserting 999 nodes, max height is just 10, as 2^10 = 1024, so total of 1024 nodes can be stored at a height of 10.

And as amazing as it sounds, it’d only take 10 steps to traverse a thousand of nodes, to search our element, whereas a linked list would have taken 1000 steps.