AVL Tree

AVL Tree is a self balancing binary tree that changes when a new node is inserted. This makes it faster to search for a specific node.

INSERTION

There are 4 cases for tree balancing if a new node is inserted:

Case 1 : the deepest node is located at the left sub tree of the left child of T.
Case 2 : the deepest node is located at the right sub tree of the right child of T.
Case 3 : the deepest node is located at the right sub tree of the left child of T.
Case 4 : the deepest node is located at the left sub tree of the right child of T.

there are 2 types of rotations in tree balancing, single rotation and double rotation. the following is all the possible rotation variant:

LL rotation: the new node is inserted in the left sub-tree of the left sub-tree of the critical node

RR rotation: the new node is inserted in the right sub-tree of the right sub-tree of the critical node.

LR rotation: the new node is inserted in the right sub-tree of the left sub-tree of the critical node

RL rotation: the new node is inserted in the left sub-tree of the right sub-tree of the critical node

the following are the algorithm for performing an insertion on an AVL Tree:

1) Perform the normal BST insertion.

2) The current node must be one of the ancestors of the newly inserted node. Update the height of the current node.

3) Get the balance factor (left subtree height – right subtree height) of the current node.

4) If balance factor is greater than 1, then the current node is unbalanced and we are either in Left Left case or left Right case. To check whether it is left left case or not, compare the newly inserted key with the key in left subtree root.

5) If balance factor is less than -1, then the current node is unbalanced and we are either in Right Right case or Right-Left case. To check whether it is Right Right case or not, compare the newly inserted key with the key in right subtree root.

DELETION

the following are all the possible rotation variants of delete operation:

Case 1 : y is left child of z and x is left child of y (Left Left Case)
Case 2 : y is left child of z and x is right child of y (Left Right Case)
Case 3 : y is right child of z and x is right child of y (Right Right Case)
Case 4 : y is right child of z and x is left child of y (Right Left Case)

the following are the algorithm for performing a delete operation on an AVL Tree:

1) Perform the normal BST deletion.

2) The current node must be one of the ancestors of the deleted node. Update the height of the current node.

3) Get the balance factor (left subtree height – right subtree height) of the current node.

4) If balance factor is greater than 1, then the current node is unbalanced and we are either in Left Left case or Left Right case. To check whether it is Left Left case or Left Right case, get the balance factor of left subtree. If balance factor of the left subtree is greater than or equal to 0, then it is Left Left case, else Left Right case.

5) If balance factor is less than -1, then the current node is unbalanced and we are either in Right Right case or Right Left case. To check whether it is Right Right case or Right Left case, get the balance factor of right subtree. If the balance factor of the right subtree is smaller than or equal to 0, then it is Right Right case, else Right Left case.

actual code reference for insertion operation (quoted from https://www.geeksforgeeks.org/avl-tree-set-1-insertion/):

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; }