AVL Tree is a Balanced Binary Search Tree. What does balance means?
It means that, we try to minimize the number of traversals, during search, insertion or deletion or any other operations on a binary search tree.
We achieve this by trying to minimize the height differences between the left sub-tree and right-sub tree.
The number of differences should not be more than ‘1’. If it is more than one, then we try to redistribute the nodes, between the left-subtree and right-subtree.
This redistribution is the same as rehashing in hash-maps, where we rehash the entries to reduce the collisions.
If there are extra nodes on the left sub-tree then we move one node to the right-sub-tree, that is, we do right rotations.
If there is extra nodes on the right-sub-tree then we move one node to the left-sub-tree, that is, we do left rotations.
You can watch me coding AVL Tree on Youtube.
Although I have put my code in this blog, but you can read my entire code at github, for better experience.
I am going to explain main methods and functions over here.
I have a function which calculates the balance-factor of child-tree, ie. left or right sub-tree of a node.
It calculates the height of left and right sub-tree and subtracts them, the range of the values are from -2 to 2, i.e [-2, 2]
int balanceFactorOfAVLNode(struct AVLNode * const root){
return root ? heightOfAVLNode(root->left) - heightOfAVLNode(root->right) : 0;
}
I have another function to update the height of nodes, after rotation.
Because, once the nodes have been moved around in the tree, their height needs to be updated for future calculations.
int updateHeight(struct AVLNode * const root){
if(root){
root->height = 1 + max(heightOfAVLNode(root->left), heightOfAVLNode(root->right));
return root->height;
}
return 0;
}
Code to Rotate Right in an AVL Tree.
struct AVLNode *rotateRight(struct AVLNode * const root){
if(root) {
struct AVLNode * const leftChild = root->left;
struct AVLNode * const rightOfLeftChild = leftChild->right;
leftChild->right = root;
root->left = rightOfLeftChild;
updateHeight(root);
updateHeight(leftChild);
return leftChild;
}
return root;
}
Code To Rotate Left In an AVL Tree
struct AVLNode *rotateLeft(struct AVLNode * const root){
if(root) {
struct AVLNode *rightChild = root->right;
struct AVLNode *leftOfRightChild = rightChild->left;
rightChild->left = root;
root->right = leftOfRightChild;
//Update Sequence is important
updateHeight(root);
updateHeight(rightChild);
return rightChild;
}
return root;
}
If you compare the left and right rotations source code, you will find that they are the same code only the left-child has been used in place of right-child.
Code to insert a node, and call updateHeight after that.
In the insertion code below, we first add a node. Then we update the height of root node.
Then we calculate the differences in the height of it’s sub-trees.
If the height differences is less than “-1” or greater than “1”. Meaning, if left subtree has two nodes extra then, we need to move one node to the right tree.
If right tree has two extra nodes then we need to move one node to the left tree.
struct AVLNode *insert(struct AVLNode *root, int const data){
if(root){
//if value is already there in the tree, then no need to perform insert operation
if(root->data != data){
if(data < root->data) {
root->left = insert(root->left, data);
} else if(data > root->data) {
root->right = insert(root->right, data);
}
updateHeight(root);
int const rootBalanceFactor = balanceFactorOfAVLNode(root);
if(rootBalanceFactor > 1) {
if(data > root->left->data) root->left = rotateLeft(root->left);
root = rotateRight(root);
} else if (rootBalanceFactor < -1) {
if(data < root->right->data) root->right = rotateRight(root->right);
root = rotateLeft(root);
}
}
return root;
}
return newAVLNode(data);
}
In the deletion code below, we delete the node first. Then rest of the process is the same as mentioned in insertion code.
struct AVLNode *deleteAVLNode(struct AVLNode * root, int const data){
if(root){
if(data < root->data){
root->left = deleteAVLNode(root->left, data);
}else if(data > root->data){
root->right = deleteAVLNode(root->right, data);
} else {
//Leaf Node
if(!(root->left || root->right)){
free(root);
return NULL;
} else if(root->left == NULL ^ root->right == NULL){
struct AVLNode * temp = orElse(root->right, root->left);
free(root);
root = temp;
} else{
struct AVLNode * temp = root->left;
//find the maximum value in the left subtree
while(temp->right) temp = temp->right;
root->data = temp->data;
root->left = deleteAVLNode(root->left, temp->data);
}
}
updateHeight(root);
int balanceFactorOfRoot = balanceFactorOfAVLNode(root);
if(1 < balanceFactorOfRoot) {
//if right subtree has an extra node then , right rotation will not balance the number of nodes
//because that extra node is present in the right of the left node
if(balanceFactorOfAVLNode(root->left) < 0) { root->left = rotateLeft(root->left); }
root = rotateRight(root);
} else if(balanceFactorOfRoot < -1) {
//If the left subtree of the right node is heavy then the extra node needs to be moved to
//the right subtree
if(balanceFactorOfAVLNode(root->right) > 0) { root->right = rotateRight(root->right); }
root = rotateLeft(root);
}
}
return root;
}
Here I am putting all the code.
Interfaces for null and nonNull functions.
#include "AVL.h" bool null(void * const anyObject); bool notNull(void * const anyObject);
Interfaces for AVL functions
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
struct AVLNode{
struct AVLNode *left;
struct AVLNode *right;
int data;
int height;
};
//Memory operation
extern struct AVLNode *newAVLNode(int const data);
//data modification
extern struct AVLNode *insert(struct AVLNode *root, int const);
extern struct AVLNode *deleteAVLNode(struct AVLNode *root, int const);
extern void freeAllMemoryInAVLTree(struct AVLNode * const);
//tree balancing
extern struct AVLNode *rotateLeft(struct AVLNode * const);
extern struct AVLNode *rotateRight(struct AVLNode *const);
//read node property
extern int updateHeight(struct AVLNode * const);
extern int balanceFactorOfAVLNode(struct AVLNode * const);
extern int heightOfAVLNode(struct AVLNode * const);
//utility function
extern int max(int const, int const);
//Log and debug
extern void printAVLTree(struct AVLNode * const);
extern void printAVLNode(struct AVLNode * const);
Implementations for AVL operations.
#include "AVL.h"
static size_t sizeOfAVLNode = sizeof(struct AVLNode *);
void freeAllMemoryInAVLTree(struct AVLNode * const root){
if(root){
freeAllMemoryInAVLTree(root->left);
freeAllMemoryInAVLTree(root->right);
free(root);
}
}
struct AVLNode *newAVLNode(int const data){
struct AVLNode *newNode = (struct AVLNode *) malloc(sizeOfAVLNode);
newNode->data = data;
newNode->height = 1;
newNode->left = newNode->right = NULL;
return newNode;
}
void printAVLNode(struct AVLNode *const root){
if(root) printf( "{"
" DATA : %d,"
" Height : %d,"
" Balance Factor : %d"
" }\n",
root->data,
root->height,
balanceFactorOfAVLNode(root));
}
static void printAVLTreeWithIndentation(struct AVLNode * const root, char const seperator, char const repeater){
if(root) {
printAVLTreeWithIndentation(root->left, seperator, repeater + 2);
for(int i = 0; i < repeater; ++i) { printf("%c", seperator); }
printf(">"); printAVLNode(root);
printAVLTreeWithIndentation(root->right, seperator, repeater + 2);
}
}
void printAVLTree(struct AVLNode * const root){
printf("\n");
printAVLTreeWithIndentation(root, '-', 0);
}
inline int heightOfAVLNode(struct AVLNode * const root){
return root ? root->height : 0;
}
inline int max(int const numberOne, int const numberTwo){
return (numberOne > numberTwo) ? numberOne : numberTwo;
}
int updateHeight(struct AVLNode * const root){
if(root){
root->height = 1 + max(heightOfAVLNode(root->left), heightOfAVLNode(root->right));
return root->height;
}
return 0;
}
int balanceFactorOfAVLNode(struct AVLNode * const root){
return root ? heightOfAVLNode(root->left) - heightOfAVLNode(root->right) : 0;
}
struct AVLNode *rotateRight(struct AVLNode * const root){
if(root) {
struct AVLNode * const leftChild = root->left;
struct AVLNode * const rightOfLeftChild = leftChild->right;
leftChild->right = root;
root->left = rightOfLeftChild;
updateHeight(root);
updateHeight(leftChild);
return leftChild;
}
return root;
}
struct AVLNode *rotateLeft(struct AVLNode * const root){
if(root) {
struct AVLNode *rightChild = root->right;
struct AVLNode *leftOfRightChild = rightChild->left;
rightChild->left = root;
root->right = leftOfRightChild;
//Update Sequence is important
updateHeight(root);
updateHeight(rightChild);
return rightChild;
}
return root;
}
struct AVLNode *insert(struct AVLNode *root, int const data){
if(root){
//if value is already there in the tree, then no need to perfrom insert operation
if(root->data != data){
if(data < root->data) {
root->left = insert(root->left, data);
} else if(data > root->data) {
root->right = insert(root->right, data);
}
updateHeight(root);
int const rootBalanceFactor = balanceFactorOfAVLNode(root);
if(rootBalanceFactor > 1) {
if(data > root->left->data) root->left = rotateLeft(root->left);
root = rotateRight(root);
} else if (rootBalanceFactor < -1) {
if(data < root->right->data) root->right = rotateRight(root->right);
root = rotateLeft(root);
}
}
return root;
}
return newAVLNode(data);
}
static struct AVLNode * orElse(struct AVLNode * firstChoice, struct AVLNode * secondChoice){
return firstChoice ? firstChoice : secondChoice;
}
struct AVLNode *deleteAVLNode(struct AVLNode * root, int const data){
if(root){
if(data < root->data){
root->left = deleteAVLNode(root->left, data);
}else if(data > root->data){
root->right = deleteAVLNode(root->right, data);
} else {
//Leaf Node
if(!(root->left || root->right)){
free(root);
return NULL;
} else if(root->left == NULL ^ root->right == NULL){
struct AVLNode * temp = orElse(root->right, root->left);
free(root);
root = temp;
} else{
struct AVLNode * temp = root->left;
//find the maximum value in the left subtree
while(temp->right) temp = temp->right;
root->data = temp->data;
root->left = deleteAVLNode(root->left, temp->data);
}
}
updateHeight(root);
int balanceFactorOfRoot = balanceFactorOfAVLNode(root);
if(1 < balanceFactorOfRoot) {
//if right subtree has an extra node then , right rotation will not balance the number of nodes
//because that extra node is present in the right of the left node
if(balanceFactorOfAVLNode(root->left) < 0) { root->left = rotateLeft(root->left); }
root = rotateRight(root);
} else if(balanceFactorOfRoot < -1) {
//If the left subtree of the right node is heavy then the extra node needs to be moved to
//the right subtree
if(balanceFactorOfAVLNode(root->right) > 0) { root->right = rotateRight(root->right); }
root = rotateLeft(root);
}
}
return root;
}
int main(){
struct AVLNode *head = newAVLNode(35);
printAVLTree(head);
head = insert(head, 37);
printAVLTree(head);
head = insert(head, 38);
printAVLTree(head);
head = insert(head, 39);
printAVLTree(head);
head = insert(head, 21);
printAVLTree(head);
head = insert(head, 37);
printAVLTree(head);
head = insert(head, 3);
printAVLTree(head);
head = insert(head, 29);
printAVLTree(head);
head = insert(head, 2);
printAVLTree(head);
head = deleteAVLNode(head, 29);
printAVLTree(head);
freeAllMemoryInAVLTree(head);
return 0;
}