C++ Programming Code Examples C++ > Computer Graphics Code Examples C++ Program to Implement AVL Trees C++ 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; } }; /* Main Contains Menu */ 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<<" "; }