AVL Tree and Balancing

The AVL Tree is a binary search tree that has an additional balance condition. This balance condition must be easy to maintain and ensures that the depth of the tree is O(logN). The simplest idea is to require that the left and right sub-trees have the same height. Recursion dictates that this idea applies to all nodes in the tree, since each node is itself a root of some sub-tree.

AVL is a height balanced tree. A height balanced tree is one in which the difference in the height of the two sub-trees for any node is less than or equal to some specified amount.

---

Balance Factor

---

Balance is defined by height of left sub-tree - height of right sub-tree. For an AVL tree the value of the balance factor of any node is -1, 0, or 1. If it is other than these three values then the tree is not balanced.

---

Insertion In AVL Tree

---

We can insert a new node in an AVL tree by finding its appropriate position similar to that of the binary search tree.

1. If the data item with key 'k' is inserted into an empty AVL tree, then the node with key 'k' is set to be the root node.
2. If tree contains only single node i.e. root node then the insertion of the node with key 'k' depends upon its value. If the value of 'k' is less than the key value of the root then it is inserted to the left of the root otherwise right of the root.
3. If on inserting the node with key 'k' the height of the right sub-tree of the root has increased. Similarly if on inserting a node with key 'k' the height of the left sub-tree of the root is increased.

LL Rotation: The new node 'x' is inserted in the left sub-tree of root node whose(root) balance factor becomes +2 after insertion. Below in the Fig 2 we will see the LL rotation.

RR Rotation: Unbalance occurs due to insertion in the right sub-tree of the right child of the root node and balance factor of root node becomes -2.We will see the RR rotation in the following Fig 3.

LR Rotation: Unbalance occurred due to the insertion in the right sub-tree of the left child of the root node. We will clear this rotation in the following Fig 4.

RL Rotation: Unbalance occurred due to the insertion in the left subtree of the right child of the root node. We will clear this rotation in the following Fig 5.

Insertion In AVL Tree Using C

#include <stdio.h> #include <stdlib.h> struct Node { int key; struct Node *left; struct Node *right; int height; }; int max(int a, int b); int height(struct Node *N) { if (N == NULL) return 0; return N->height; } int max(int a, int b) { return (a > b)? a : b; } struct Node* newNode(int key) { struct Node* node = (struct Node*) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; // new node is initially added at leaf return(node); } struct Node *rightRotate(struct Node *y) { struct Node *x = y->left; struct Node *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; // Return new root return x; } struct Node *leftRotate(struct Node *x) { struct Node *y = x->right; struct Node *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; // Return new root return y; } int getBalance(struct Node *N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } struct Node* insert(struct Node* node, int key) { /* 1. Perform the normal BST insertion */ if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys are not allowed in BST return node; /* 2. Update height of this ancestor node */ node->height = 1 + max(height(node->left), height(node->right)); /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int balance = getBalance(node); // If this node becomes unbalanced, then // there are 4 cases // Left Left Case if (balance > 1 && key < node->left->key) return rightRotate(node); // Right Right Case if (balance < -1 && key > node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } void preOrder(struct Node *root) { if(root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } int main() { struct Node *root = NULL; int ch,value; while(1) { printf("\n1.insert"); printf("\n2.preorder"); printf("\n3.exit"); printf("\nenter your choice:"); scanf("%d",&ch); switch(ch) { case 1:printf("\nenter the value:"); scanf("%d",&value); root=insert(root,value); break; case 2:preOrder(root); break; case 3:return 0; } } return 0; }

---

Deletion In AVL Tree

---

The deletion of a node from an AVL tree is exactly the same as the deletion of a node from the BST. The sequence of steps to be followed in deleting a node from an AVL tree is as follows:

1. Initially, the AVL tree is searched to find the node to be deleted.
2. The procedure used to delete a node in an AVL tree is the same as deleting the node in the binary search tree.
3. After deletion of the node, check the balance factor of each node.
4. Rebalance the AVL tree if the tree is unbalanced. In this situation we need some rotations.

R0 And L0 Rotation: When we delete a node and that node is present at the right sub-tree. In this situation th parent node of left sub-tree whose balance factor is 0 is rotated in right direction. Similarly for L0 rotation, the deleted node is present at left sub-tree of root node. We will see the rotation in following Fig 1.

R1 And L1 Rotation: It is same as R0 or L0 rotation. Only the difference is that balance factor of parent node of left sub-tree or right sub-tree is +1 here.We will see the rotation in following Fig 2.

R(-1) And L(-1) Rotation: In this case balance factor of parent node is -1. we will see the rotation in following Fig 3.

---

Deletion In AVL Tree Using C

---

#include <stdio.h> #include <stdlib.h> struct Node { int key; struct Node *left; struct Node *right; int height; }; int max(int a, int b); int height(struct Node *N) { if (N == NULL) return 0; return N->height; } int max(int a, int b) { return (a > b)? a : b; } struct Node* newNode(int key) { struct Node* node = (struct Node*) malloc(sizeof(struct Node)); node->key = key; node->left = NULL; node->right = NULL; node->height = 1; // new node is initially added at leaf return(node); } struct Node *rightRotate(struct Node *y) { struct Node *x = y->left; struct Node *T2 = x->right; // Perform rotation x->right = y; y->left = T2; // Update heights y->height = max(height(y->left), height(y->right))+1; x->height = max(height(x->left), height(x->right))+1; // Return new root return x; } struct Node *leftRotate(struct Node *x) { struct Node *y = x->right; struct Node *T2 = y->left; // Perform rotation y->left = x; x->right = T2; // Update heights x->height = max(height(x->left), height(x->right))+1; y->height = max(height(y->left), height(y->right))+1; // Return new root return y; } int getBalance(struct Node *N) { if (N == NULL) return 0; return height(N->left) - height(N->right); } struct Node* insert(struct Node* node, int key) { /* 1. Perform the normal BST rotation */ if (node == NULL) return(newNode(key)); if (key < node->key) node->left = insert(node->left, key); else if (key > node->key) node->right = insert(node->right, key); else // Equal keys not allowed return node; /* 2. Update height of this ancestor node */ node->height = 1 + max(height(node->left), height(node->right)); /* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */ int balance = getBalance(node); // If this node becomes unbalanced, then there are 4 cases // Left Left Case if (balance > 1 && key < node->left->key) return rightRotate(node); // Right Right Case if (balance < -1 && key > node->right->key) return leftRotate(node); // Left Right Case if (balance > 1 && key > node->left->key) { node->left = leftRotate(node->left); return rightRotate(node); } // Right Left Case if (balance < -1 && key < node->right->key) { node->right = rightRotate(node->right); return leftRotate(node); } /* return the (unchanged) node pointer */ return node; } struct Node * minValueNode(struct Node* node) { struct Node* current = node; /* loop down to find the leftmost leaf */ while (current->left != NULL) current = current->left; return current; } struct Node* deleteNode(struct Node* root, int key) { // STEP 1: PERFORM STANDARD BST DELETE if (root == NULL) return root; // If the key to be deleted is smaller than the // root's key, then it lies in left subtree if ( key < root->key ) root->left = deleteNode(root->left, key); // If the key to be deleted is greater than the // root's key, then it lies in right subtree else if( key > root->key ) root->right = deleteNode(root->right, key); // if key is same as root's key, then This is // the node to be deleted else { // node with only one child or no child if( (root->left == NULL) || (root->right == NULL) ) { struct Node *temp = root->left ? root->left : root->right; // No child case if (temp == NULL) { temp = root; root = NULL; } else // One child case *root = *temp; // Copy the contents of // the non-empty child free(temp); } else { // node with two children: Get the inorder // successor (smallest in the right subtree) struct Node* temp = minValueNode(root->right); // Copy the inorder successor's data to this node root->key = temp->key; // Delete the inorder successor root->right = deleteNode(root->right, temp->key); } } // If the tree had only one node then return if (root == NULL) return root; // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE root->height = 1 + max(height(root->left), height(root->right)); // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to // check whether this node became unbalanced) int balance = getBalance(root); // If this node becomes unbalanced, then there are 4 cases // Left Left Case if (balance > 1 && getBalance(root->left) >= 0) return rightRotate(root); // Left Right Case if (balance > 1 && getBalance(root->left) < 0) { root->left = leftRotate(root->left); return rightRotate(root); } // Right Right Case if (balance < -1 && getBalance(root->right) <= 0) return leftRotate(root); // Right Left Case if (balance < -1 && getBalance(root->right) > 0) { root->right = rightRotate(root->right); return leftRotate(root); } return root; } void preOrder(struct Node *root) { if(root != NULL) { printf("%d ", root->key); preOrder(root->left); preOrder(root->right); } } int main() { struct Node *root = NULL; int ch,value; while(1) { printf("\n1.insert"); printf("\n2.preorder"); printf("\n3.delete"); printf("\n4.exit"); printf("\nenter your choice:"); scanf("%d",&ch); switch(ch) { case 1:printf("\nenter the value:"); scanf("%d",&value); root=insert(root,value); break; case 2:preOrder(root); break; case 3:printf("\n enter value for deletion:"); scanf("%d",&value); root=deleteNode(root,value); break; case 4:return 0; } } return 0; }

Happy Exploring!