1. Chain storage of AVL tree
typedef int ElementType; typedef struct AVLNode *Position; typedef Position AVLTree; struct AVLNode{ ElementType Data;//node data AVLTree Left;//Point to the left subtree AVLTree Right;//point to the right subtree int Height;//tree height };
2. Rotate
-
left monorotation
AVLTree SingleLeftRotation(AVLTree A) { //A must have a left child node B //return the new root node B printf("Left single rotation\\ "); AVLTree B=A->Left ; A->Left =B->Right; B->Right=A; //update tree height A->Height =Max(GetHeight(A->Left ),GetHeight(A->Right )) + 1; B->Height =Max(GetHeight(B->Left ),A->Height ) + 1; return B; }
-
Right monorotation
AVLTree SingleRightRotation(AVLTree A) { //A must have a right child node B //return the new root node A printf("Right single rotation\\ "); AVLTree B=A->Right ; A->Right=B->Left ; B->Left =A; //update tree height A->Height =Max(GetHeight(A->Left ),GetHeight(A->Right )) + 1; B->Height =Max(A->Height ,GetHeight(B->Right )) + 1; }
-
Left and right double rotation
AVLTree DoubleLeftRightRotation(AVLTree A) { //A must have a left child node B, B must have a right child node C //return the new root node C printf("left and right single rotation\\ "); //Put B and C to the right and return to C A->Left =SingleRightRotation(A->Left ); //Make left single rotation of A and C, return C return SingleLeftRotation(A); }
-
right left double rotation
AVLTree DoubleRightLeftRotation(AVLTree A) { //A must have a right child node B, B must have a left child node C //return the new root node C printf("Right left single rotation\\ "); //Make left single rotation of B and C, return C A->Right=SingleLeftRotation(A->Right ); //Put A and C to the right and return to C return SingleRightRotation(A); }
3. Insert
AVLTree Insert(AVLTree T,ElementType X) { if(!T){ // insert empty tree T=(AVLTree)malloc(sizeof(struct AVLNode)); T->Data =X; T->Left =T->Right =NULL; T->Height =1; }//The tree is not empty, choose to insert the left subtree or the right subtree else if(X<T->Data ){//Insert left subtree T->Left =Insert(T->Left ,X); //Unbalanced, need left rotation if(GetHeight(T->Left )-GetHeight(T->Right )==2)//unbalanced condition if(X<T->Left->Data ) //on the left T=SingleLeftRotation(T);//Left single rotation else //on the right T=DoubleLeftRightRotation(T); //left and right double rotation } else if(X>T->Data ){//Insert the right subtree T->Right=Insert(T->Right ,X); //unbalanced if(GetHeight(T->Right )-GetHeight(T->Left )==2) if(X>T->Right->Data )//on the right T=SingleRightRotation(T);//right single rotation else //on the left T=DoubleRightLeftRotation(T);//Right and left double rotation } //else X==T->Data does not need to be inserted //update tree height T->Height =Max(GetHeight(T->Left ),GetHeight(T->Right )) + 1; //Select the maximum height of the left and right subtrees and add the root height return T; }
4. Complete code
//balanced binary tree AVL //The non-recursive algorithm of the insertion operation of the AVL tree is poorly readable, and is usually implemented using a recursive algorithm #include#include #include /*-------------Linked storage of AVL tree --------------------*/ typedef int ElementType; typedef struct AVLNode *Position; typedef Position AVLTree; struct AVLNode{ ElementType Data;//node data AVLTree Left;//Point to the left subtree AVLTree Right;//point to the right subtree int Height;//tree height }; /*-------------The end of the chained storage of the AVL tree-------------------*/ // tree height int GetHeight(AVLTree T) { int LH,RH,MaxH; if(T){ LH=GetHeight(T->Left ); RH=GetHeight(T->Right ); MaxH=LH>RH?LH:RH; return (MaxH + 1);//return tree height } return 0;//Empty tree height is 1 } //preorder traversal void PreorderTraversal(AVLTree T) { if(T){ printf("%d ",T->Data ); Preorder Traversal(T->Left ); PreorderTraversal(T->Right ); } } //maximum value int Max(int a,int b) { //Return the larger value of a and b return a>b?a:b; } /*-------------Rotate--------------------*/ // left single rotation AVLTree SingleLeftRotation (AVLTree A) { //A must have a left child node B //return the new root node B printf("Left single rotation\\ "); AVLTree B=A->Left ; A->Left =B->Right; B->Right=A; //update tree height A->Height =Max(GetHeight(A->Left ),GetHeight(A->Right )) + 1; B->Height =Max(GetHeight(B->Left ),A->Height ) + 1; return B; } // right single spin AVLTree SingleRightRotation (AVLTree A) { //A must have a right child node B //return the new root node A printf("Right single rotation\\ "); AVLTree B=A->Right ; A->Right=B->Left ; B->Left =A; //update tree height A->Height =Max(GetHeight(A->Left ),GetHeight(A->Right )) + 1; B->Height =Max(A->Height ,GetHeight(B->Right )) + 1; } // left and right double rotation AVLTree DoubleLeftRightRotation (AVLTree A) { //A must have a left child node B, B must have a right child node C //return the new root node C printf("left and right single rotation\\ "); //Put B and C to the right and return to C A->Left =SingleRightRotation(A->Left ); //Make left single rotation of A and C, return C return SingleLeftRotation(A); } // right and left double rotation AVLTree DoubleRightLeftRotation (AVLTree A) { //A must have a right child node B, B must have a left child node C //return the new root node C printf("Right left single rotation\\ "); //Make left single rotation of B and C, return C A->Right=SingleLeftRotation(A->Right ); //Put A and C to the right and return to C return SingleRightRotation(A); } /*-------------end of rotation--------------------*/ /*-------------insert function --------------------*/ AVLTree Insert(AVLTree T,ElementType X) { if(!T){ // insert empty tree T=(AVLTree)malloc(sizeof(struct AVLNode)); T->Data =X; T->Left =T->Right =NULL; T->Height =1; }//The tree is not empty, choose to insert the left subtree or the right subtree else if(X<T->Data ){//Insert left subtree T->Left =Insert(T->Left ,X); //Unbalanced, need left rotation if(GetHeight(T->Left )-GetHeight(T->Right )==2)//unbalanced condition if(X<T->Left->Data ) //on the left T=SingleLeftRotation(T);//Left single rotation else //on the right T=DoubleLeftRightRotation(T); //left and right double rotation } else if(X>T->Data ){//Insert the right subtree T->Right=Insert(T->Right ,X); //unbalanced if(GetHeight(T->Right )-GetHeight(T->Left )==2) if(X>T->Right->Data )//on the right T=SingleRightRotation(T);//right single rotation else //on the left T=DoubleRightLeftRotation(T);//Right and left double rotation } //else X==T->Data does not need to be inserted //update tree height T->Height =Max(GetHeight(T->Left ),GetHeight(T->Right )) + 1; //Select the maximum height of the left and right subtrees and add the root height return T; } /*-------------insert end--------------------*/ // output void PrintResult(AVLTree T) { int h=GetHeight(T); printf("Tree height is: %d\\ ",h); printf("Preorder traversal:"); Preorder Traversal(T); printf("\\ "); } int main() { AVLTree T=NULL,Head=NULL;; ElementType X; printf("Please enter the root node:"); scanf("%d", &X); T=Insert(T,X); Head=T; int i; printf("Please enter 5 child nodes:"); for(i=0;i<5;i ++ ){ scanf("%d", &X); T=Insert(T,X); } PrintResult(T); return 0; }
run: