AVLInsert(k,R)Insert(k,R)N<-Find(k,R)Rebalance(N)Rebalancingif|N.Left.Height-N.Right.Height|<=1Rebalance(N)p<-N.ParentifN.Left.Height>N.Right.Height+1:RebalanceRight(N)ifN.Right.Height>N.Left.Height+1:RebalanceLeft(N)AdjustHeight(N)ifP!=null:Rebalance(N)AdjustHeight(N)N.Height<-1+max(N.Left.Height+N.Right.Height)

////  AVLTree.h//  Data structures////  Created by Lalit Yadav on 06/09/20.//  Copyright © 2020 Lalit Yadav. All rights reserved.//#ifndef AVLTree_h#define AVLTree_h#include <iostream>usingnamespacestd;structNode{intdata;intheight;Node*parent;Node*left;Node*right;};typedefNode*Nodeptr;classAVLTree{Nodeptrroot;NodeptrMaximum(Nodeptrnode);intGetHeight(Nodeptrnode);voidAdjustHeight(Nodeptrnode);voidReplaceChild(Nodeptrparent,Nodeptrchild,Nodeptrnew_child);voidRotateLeft(Nodeptrnode);voidRotateRight(Nodeptrnode);voidRebalance(Nodeptrnode);voidRebalanceLeft(Nodeptrnode);voidRebalanceRight(Nodeptrnode);public:AVLTree():root(nullptr){}AVLTree(intkey);boolIsEmpty();NodeptrRoot();NodeptrFind(intkey);voidInsert(intkey);voidDelete(intkey);voidPrintInOrder(Nodeptrnode);voidPrintPreOrder(Nodeptrnode);};boolAVLTree::IsEmpty(){returnroot==nullptr;}NodeptrAVLTree::Root(){returnroot;}NodeptrAVLTree::Maximum(Nodeptrnode){if(node->right!=NULL){returnMaximum(node->right);}else{returnnode;}}intAVLTree::GetHeight(Nodeptrnode){if(node==nullptr)return0;returnnode->height;}NodeptrAVLTree::Find(intkey){if(IsEmpty()){returnnullptr;}autoparent=root;while(parent!=nullptr){if(key>parent->data&&parent->right!=nullptr)parent=parent->right;elseif(key<parent->data&&parent->left!=nullptr)parent=parent->left;elsereturnparent;}returnparent;}voidAVLTree::AdjustHeight(Nodeptrnode){node->height=1+max(GetHeight(node->left),GetHeight(node->right));}voidAVLTree::RotateLeft(Nodeptrnode){autopivot=node->right;// Update the parent of the nodepivot->parent=node->parent;node->parent=pivot;// Update the child of of the updated parentif(pivot->parent==nullptr)root=pivot;elseif(pivot->parent->left==node)pivot->parent->left=pivot;// Update the child link of the parentelsepivot->parent->right=pivot;node->right=pivot->left;if(pivot->left!=nullptr)pivot->left->parent=node;pivot->left=node;AdjustHeight(node);AdjustHeight(pivot);}voidAVLTree::RotateRight(Nodeptrnode){autopivot=node->left;pivot->parent=node->parent;node->parent=pivot;if(pivot->parent==nullptr)root=pivot;elseif(pivot->parent->left==node)pivot->parent->left=pivot;elsepivot->parent->right=pivot;node->left=pivot->right;if(pivot->right!=nullptr)pivot->right->parent=node;pivot->right=node;AdjustHeight(node);AdjustHeight(pivot);}voidAVLTree::RebalanceLeft(Nodeptrnode){autoright_child=node->right;if(right_child!=nullptr){if(GetHeight(right_child->left)>GetHeight(right_child->right))RotateRight(right_child);}RotateLeft(node);}voidAVLTree::RebalanceRight(Nodeptrnode){autoleft_child=node->left;if(left_child!=nullptr){if(GetHeight(left_child->right)>GetHeight(left_child->left))RotateLeft(left_child);}RotateRight(node);}voidAVLTree::Rebalance(Nodeptrnode){autoparent=node->parent;if(GetHeight(node->left)>GetHeight(node->right)+1)RebalanceRight(node);if(GetHeight(node->right)>GetHeight(node->left)+1)RebalanceLeft(node);AdjustHeight(node);if(parent!=nullptr){Rebalance(parent);}}voidAVLTree::Insert(intkey){autop=newNode;p->data=key;p->height=0;p->parent=nullptr;p->left=nullptr;p->right=nullptr;if(IsEmpty()){root=p;}else{autoparent=Find(key);p->height=1;if(key<parent->data)parent->left=p;elseparent->right=p;p->parent=parent;Rebalance(parent);}}voidAVLTree::Delete(intkey){autonode=Find(key);if(node==nullptr)return;if(node->right==nullptr&&node->left==nullptr){if(node->parent==nullptr){root=nullptr;}else{ReplaceChild(node->parent,node,nullptr);Rebalance(node->parent);}}elseif(node->left==nullptr){// Replace the node with it's right childif(node->parent==nullptr){root=node->right;node->right->parent=nullptr;Rebalance(node->right);}else{ReplaceChild(node->parent,node,node->right);node->right->parent=node->parent;Rebalance(node->parent);}}else{// Replace the node with the maximum key from it's left childautonew_node=Maximum(node->left);if(node->parent==nullptr){root=new_node;new_node->right=node->right;new_node->left=node->left;Rebalance(new_node);}else{autoparent_new_node=new_node->parent;ReplaceChild(node->parent,node,new_node);ReplaceChild(new_node->parent,new_node,nullptr);new_node->parent=node->parent;new_node->left=node->left;if(node->right!=nullptr){new_node->right=node->right;new_node->right->parent=new_node;}if(parent_new_node->parent==node){parent_new_node->parent=new_node;}Rebalance(parent_new_node);}}deletenode;}voidAVLTree::ReplaceChild(Nodeptrparent,Nodeptrchild,Nodeptrnew_child){if(parent->left==child){parent->left=new_child;}else{parent->right=new_child;}}voidAVLTree::PrintInOrder(Nodeptrnode){if(node==nullptr)return;PrintInOrder(node->left);cout<<node->data<<' ';PrintInOrder(node->right);}voidAVLTree::PrintPreOrder(Nodeptrnode){if(node==nullptr)return;cout<<node->data<<' ';PrintPreOrder(node->left);PrintPreOrder(node->right);}#endif/* AVLTree_h */