Insert operation of balanced binary tree (AVL tree)

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

  1. 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;
 }
 
  1. 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;
 } 
  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);
 } 
  1. 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: