In this post first we will understand what are AVL Trees and then we write a program to implement AVL Trees in C++.
What is AVL Tree:
An AVL treeis another balanced binary search tree. Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed. Like red-black trees, they are not perfectly balanced, but pairs of sub-trees differ in height by at most 1, maintaining an O(logn) search time. Addition and deletion operations also take O(logn) time.
Definition of an AVL tree:
An AVL tree is a binary search tree which has the following properties:
- The sub-trees of every node differ in height by at most one.
- Every sub-tree is an AVL tree.
Now we have got an idea of it, let’s write the source code to implement AVL Tree.
C++ program to implement AVL Tree:
// Program to implement AVL Trees #include<iostream> #include<cstdio> #include<sstream> #include<algorithm> #define pow2(n) (1 << (n)) using namespace std; // Node Declaration struct avl_node { int data; struct avl_node *left; struct avl_node *right; }*root; // Class Declaration class avlTree { public: int height(avl_node *); int diff(avl_node *); avl_node *rr_rotation(avl_node *); avl_node *ll_rotation(avl_node *); avl_node *lr_rotation(avl_node *); avl_node *rl_rotation(avl_node *); avl_node* balance(avl_node *); avl_node* insert(avl_node *, int ); void display(avl_node *, int); void inorder(avl_node *); void preorder(avl_node *); void postorder(avl_node *); avlTree() { root = NULL; } }; int main() { int choice, item; avlTree avl; while (1) { cout<<"\n---------------------"<<endl; cout<<"AVL Tree Implementation"<<endl; cout<<"\n---------------------"<<endl; cout<<"1.Insert Element into the tree"<<endl; cout<<"2.Display Balanced AVL Tree"<<endl; cout<<"3.InOrder traversal"<<endl; cout<<"4.PreOrder traversal"<<endl; cout<<"5.PostOrder traversal"<<endl; cout<<"6.Exit"<<endl; cout<<"Enter your Choice: "; cin>>choice; switch(choice) { case 1: cout<<"Enter value to be inserted: "; cin>>item; root = avl.insert(root, item); break; case 2: if (root == NULL) { cout<<"Tree is Empty"<<endl; continue; } cout<<"Balanced AVL Tree:"<<endl; avl.display(root, 1); break; case 3: cout<<"Inorder Traversal:"<<endl; avl.inorder(root); cout<<endl; break; case 4: cout<<"Preorder Traversal:"<<endl; avl.preorder(root); cout<<endl; break; case 5: cout<<"Postorder Traversal:"<<endl; avl.postorder(root); cout<<endl; break; case 6: exit(1); break; default: cout<<"Wrong Choice"<<endl; } } return 0; } // Height of AVL Tree int avlTree::height(avl_node *temp) { int h = 0; if (temp != NULL) { int l_height = height (temp->left); int r_height = height (temp->right); int max_height = max (l_height, r_height); h = max_height + 1; } return h; } // Height Difference int avlTree::diff(avl_node *temp) { int l_height = height (temp->left); int r_height = height (temp->right); int b_factor= l_height - r_height; return b_factor; } // Right- Right Rotation avl_node *avlTree::rr_rotation(avl_node *parent) { avl_node *temp; temp = parent->right; parent->right = temp->left; temp->left = parent; return temp; } // Left- Left Rotation avl_node *avlTree::ll_rotation(avl_node *parent) { avl_node *temp; temp = parent->left; parent->left = temp->right; temp->right = parent; return temp; } // Left - Right Rotation avl_node *avlTree::lr_rotation(avl_node *parent) { avl_node *temp; temp = parent->left; parent->left = rr_rotation (temp); return ll_rotation (parent); } // Right- Left Rotation avl_node *avlTree::rl_rotation(avl_node *parent) { avl_node *temp; temp = parent->right; parent->right = ll_rotation (temp); return rr_rotation (parent); } // Balancing AVL Tree avl_node *avlTree::balance(avl_node *temp) { int bal_factor = diff (temp); if (bal_factor > 1) { if (diff (temp->left) > 0) temp = ll_rotation (temp); else temp = lr_rotation (temp); } else if (bal_factor < -1) { if (diff (temp->right) > 0) temp = rl_rotation (temp); else temp = rr_rotation (temp); } return temp; } // Insert Element into the tree avl_node *avlTree::insert(avl_node *root, int value) { if (root == NULL) { root = new avl_node; root->data = value; root->left = NULL; root->right = NULL; return root; } else if (value < root->data) { root->left = insert(root->left, value); root = balance (root); } else if (value >= root->data) { root->right = insert(root->right, value); root = balance (root); } return root; } // Display AVL Tree void avlTree::display(avl_node *ptr, int level) { int i; if (ptr!=NULL) { display(ptr->right, level + 1); printf("n"); if (ptr == root) cout<<"Root -> "; for (i = 0; i < level && ptr != root; i++) cout<<" "; cout<<ptr->data; display(ptr->left, level + 1); } } // Inorder Traversal of AVL Tree void avlTree::inorder(avl_node *tree) { if (tree == NULL) return; inorder (tree->left); cout<<tree->data<<" "; inorder (tree->right); } // Preorder Traversal of AVL Tree void avlTree::preorder(avl_node *tree) { if (tree == NULL) return; cout<<tree->data<<" "; preorder (tree->left); preorder (tree->right); } // Postorder Traversal of AVL Tree void avlTree::postorder(avl_node *tree) { if (tree == NULL) return; postorder ( tree ->left ); postorder ( tree ->right ); cout<<tree->data<<" "; }
OUTPUT:
--------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Tree is Empty --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 8 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: Root -> 8 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 5 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: Root -> 8 5 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 8 Root -> 5 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 11 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 11 8 Root -> 5 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 15 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 Root -> 5 4 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 3 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 Root -> 5 4 3 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 6 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 6 Root -> 5 4 3 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 1 Enter value to be inserted: 2 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 6 Root -> 5 4 3 2 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 4 Preorder Traversal: 5 3 2 4 11 8 6 15 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 5 Postorder Traversal: 2 4 3 6 8 15 11 5 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 3 Inorder Traversal: 2 3 4 5 6 8 11 15 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 2 Balanced AVL Tree: 15 11 8 6 Root -> 5 4 3 2 --------------------- AVL Tree Implementation --------------------- 1.Insert Element into the tree 2.Display Balanced AVL Tree 3.InOrder traversal 4.PreOrder traversal 5.PostOrder traversal 6.Exit Enter your Choice: 6 ------------------
Comment below in case you want to discuss more about the C++ program to implement AVL Trees.
The height is recalculated recursively at each insertion, so it’s not O(log(N)) …