[Data Structure] The rotation and insertion of the AVL tree

By Data Structure

AVL tree

Left single rotation

Code implementation

void _RotateL(Node* parent) {Node* subR=parent->_right; Node* subRL=subR->_left; Node* ppNode=parent- >_parent; subR->_left=parent; parent->_right=subRL; if(subRL) subRL->_parent=parent; if(ppNode==NULL) {_root=subR; subR->_parent=NULL;} else if (ppNode->_left==parent) {ppNode->_left=subR; subR->_parent=ppNode;} else//(ppNode->_right==parent) {ppNode->_right=subR; subR->_parent= PPNode;} Subr -> _ bf = pent -> _ bf = 0;}  
 right single-handed  
 
 
 
Implementation
 
 
void _RotateR(Node* parent) {Node* subL=parent->_left; Node* subLR=subL->_right; Node* ppNode=parent->_parent; subL->_right=parent; parent- >_left=subLR; if(subLR) subLR->_parent=parent; if(ppNode==NULL) {_root=subL; subL->_parent==NULL;} else if(ppNode->_left==parent) {subL ->_parent=ppNode; ppNode->_left=subL;} else if (ppNode->_right==parent) {subL->_parent=ppNode; ppNode->_right=subL;} subL->_bf=parent->_bf =0;	}




左右旋


 


Implementation


 


void _RotateLR(Node* parent) {Node* subL=parent->_left; Node* subLR=subL->_right ; int bf=subLR->_bf; _RotateL(parent->_left); _RotateR(parent); if (bf==0) {subL->_bf=subLR->_bf=parent->_bf=0;} else if (bf==-1) {parent->_bf=1; su bLR->_bf=subL->_bf=0;		}		else		{			subL->_bf=-1;			subLR->_bf=parent->_bf=0;		}			}




Right and left rotation


 


Implementation




void _RotateRL(Node* parent) {Node* subR=parent->_right; Node* subRL=subR->_left; int bf=subRL->_bf; _RotateR(parent->_right); _RotateRL(parent); if(bf==0) {subR->_bf=parent->_bf=0;} else if(bf==-1) {parent->_bf=subR->_bf=0; subRL- >_bf=1;} else {parent->_bf=-1; subR->_bf=subRL->_bf=0;} }


 Two special test cases


 < p>< br> 


 


Part of the code to solve these two special use cases (implemented in the insert function)




 else {if(parent->_bf == 2) {if(cur->_bf == 1) {_RotateL(parent);} else if(cur->_bf==-2) {_RotateRL(parent);}} else if(parent->_bf==-2) {if(cur->_bf == -1) {_RotateR(parent);} else if(cur->_bf==2) {_RotateLR(parent);} }


 Insert function




 bool Insert(const K& key,const V& value) {Node* newNode=new Node(key,value) ; if(_root==NULL) {_root=newNode; return true;} Node* parent=NULL; Node* cur=_root; while(cur) {if(cur->_key>key) {parent=cur; cur= cur->_left;} else if(cur->_key_right;} else return false;} cur=new Node(key,value); cur->_parent=parent ; if(parent->_key>key) parent ->_left=cur; else if(parent->_key_right=cur; while (parent) {if(parent->_left==cur) {--parent->_bf;} else if( parent->_right==cur) {++parent->_bf;} if(parent->_bf==0) {return true;} if(abs(parent->_bf)==1) {cur=parent; parent=parent->_parent;} else {if(parent->_bf == 2) {if(cur->_bf == 1) {_RotateL(parent);} else if(cur->_bf==-2) {_RotateRL(parent);}} else if(parent->_bf==-2) {if(cur->_bf == -1) {_RotateR(parent);} else if(cur->_bf==2) {_RotateLR(parent);}} else return true;}} return true;}


 All code


AVLtree.h




#includeusing namespace std;templatestruct AVLtreeNode{ AVLtreeNode * _left; AVLtreeNode* _right; AVLtreeNode* _parent; K _key; V _value; i nt _bf; AVLtreeNode(const K& key,const V& value) :_left(NULL) ,_right(NULL) ,_parent(NULL) ,_key(key) ,_value(value) ,_bf(0) ());templateclass AVLtree{ typedef AVLtreeNode Node;public: AVLtree() :_root(NULL) {} ~AVLtree() {} bool Insert(const K& key,const V& value) {Node* newNode =new Node(key,value); if(_root==NULL) {_root=newNode; return true;} Node* parent=NULL; Node* cur=_root; while(cur) {if(cur->_key>key ) {parent=cur; cur=cur->_left;} else if(cur->_key_right;} else return false;} cur=new Node(key,value ); cur->_parent=parent; if(parent->_key>key) parent->_left=cur; else if(parent->_key_right=cur; while (parent) {if(parent ->_left==cur) {--parent->_bf;} else if(parent->_right==cur) {++parent->_bf;} if(parent->_bf==0) {return true; } if(abs(parent->_bf)==1) {c ur=parent; parent=parent->_parent;} else {if(parent->_bf == 2) {if(cur->_bf == 1) {_RotateL(parent);} else if(cur->_bf= =-2) {_RotateRL(parent);}} else if(parent->_bf==-2) {if(cur->_bf == -1) {_RotateR(parent);} else if(cur->_bf ==2) {_RotateLR(parent);}} else return true;}} return true;} void Inorder() {_Inorder(_root); cout<_left); cout<<" KEY: "<_key<<" VALUE: "<_value<<" BF: "<_bf<_right);} int _Height(Node* root) {if(root==NULL) return 0; int left=_Height(root->_left)+1; int right=_Height(root->_right)+ 1; return left>right? Left:right;} bool _IsBalance(Node* parent) { if(parent==NULL) return true; int bf=_Height(parent->_right)-_Height(parent->_left); if(parent->_bf!=bf) {cout<<"Not a balanced tree"<< parent->_key<_left); return _IsBalance(parent->_right);} bool _IsBalanceOP(Node* root,int height) {if (root==NULL) { height=0; return true;} int leftHeight=0; if(_IsBalanceOP(root->_left,leftHeight)==false) return false; int rightHeigt=0; if(_IsBalanceOP(root->_right,rightHeigt)==false ) return false; return true;} void _RotateL(Node* parent) {Node* subR=parent->_right; Node* subRL=subR->_left; Node* ppNode=parent->_parent; subR->_left=parent; parent->_right=subRL; if(subRL) subRL->_parent=parent; if(ppNode==NULL) {_root=subR; subR->_parent=NULL;} else if(ppNode->_left==parent) { ppNode->_left=subR; subR->_parent=ppNode;} else//(ppNode->_right==parent) {ppNode->_right=subR; subR->_parent=ppNode;} subR->_bf=parent- >_bf=0;} void _RotateR(Node* pa rent) {Node* subL=parent->_left; Node* subLR=subL->_right; Node* ppNode=parent->_parent; subL->_right=parent; parent->_left=subLR; if(subLR) subLR- >_parent=parent; if(ppNode==NULL) {_root=subL; subL->_parent==NULL;} else if(ppNode->_left==parent) {subL->_parent=ppNode; ppNode->_left= subL;} else if (ppNode->_right==parent) {subL->_parent=ppNode; ppNode->_right=subL;} subL->_bf=parent->_bf=0;} void _RotateLR(Node* parent) {Node* subL=parent->_left; Node* subLR=subL->_right; int bf=subLR->_bf; _RotateL(parent->_left); _RotateR(parent); if (bf==0) {subL- >_bf=subLR->_bf=parent->_bf=0;} else if (bf==-1) {parent->_bf=1; subLR->_bf=subL->_bf=0;} else {subL- >_bf=-1; subLR->_bf=parent->_bf=0;}} void _RotateRL(Node* parent) {Node* subR=parent->_right; Node* subRL=subR->_left; int bf=subRL ->_bf; _RotateR(parent->_right); _RotateRL(parent); if(bf==0) {subR->_bf=parent->_bf=0;} else if(bf==-1) {parent- >_b f=subR->_bf=0; subRL->_bf=1;} else {parent->_bf=-1; subR->_bf=subRL->_bf=0;} }private: Node* _root;};void TestAVLtree1(){ AVLtree At; At.Insert(0,1); At.Insert(1,1); At.Insert(2,1); At.Insert(3,1); At. Insert(4,1); At.Insert(5,1); At.Insert(6,1); At.Insert(7,1); At.Insert(8,1); At.Insert(9,1 ); At.Insert(10,1); At.Insert(11,1); At.Inorder(); cout< At; At.Insert(4,1); At.Insert(2,1); At.Insert(6,1); At.Insert(1,1); At.Insert(3,1); At.Insert (5,1); At.Insert(15,1); At.Insert(7,1); At.Insert(16,1); At.Inorder(); cout< At; At.Insert(16,1); At.Insert(3,1); At.Insert(7,1); At.Insert(11,1) ; At.Insert(9,1); At.Insert(26,1); At.Insert(18,1); At.Insert(14,1); At.Insert(15,1); At.Inorder( ); cout<

 main.cpp 




#i nclude "AVLtree.h"#include int main(){ TestAVLtree1(); TestAVLtree2(); TestAVLtree3(); system("pause"); return 0;}
, , , ,

Leave a Comment

Your email address will not be published.