系统学习图像算法Day.14——数据结构学习——C代码实现AVL树（带有平衡条件的二叉搜索树）

た入场券 2023-08-17 15:29 20阅读 0赞

首先要了解什么叫做**AVL树（带有平衡条件的二叉搜索树）**  
：一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树

主要了解内容：  
结构体：

struct AvlNode
    { 
          ElementType Element;
          AvlTree Left;
          AvlTree Right;
       int Height;       //Height 表示以该节点为根的子树的高度
    };

单旋转

static Position SingleRotateWithLeft( Position K2 )
    { 
        Position K1;
     K1 = K2 ->Left;
     K2 ->Left = K1 ->Right;
     K1 ->Right = K2;
     K2 ->Height = Max ( Height(K2->Left), Height(K2->Right) ) +1;
     K1 ->Height = Max ( Height(K1->Left), K2->Height ) +1;
     return K1;
    }
    static Position SingleRotateWithRight( Position K2 )
    { 
    //同理，不难写出
    }

双旋转

static Position DoubleRotateWithLeft( Position K3 )
    { 
     K3->Left = SingleRotateWithRight( K3->Left );
     return SingleRotateWithLeft(K3);
    }
    static Position DoubleRotateWithRight( Position K3 )
    { 
    //同理
    }

插入操作

AvlTree Insert ( ElementType X, AvlTree T )
    { 
        if(T == NULL)
     { 
           T = (AvlTree)malloc( sizeof( AvlTree ) );
        if( T==NULL )
         printf("out of space");
        else
        { 
        T->Element = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
        }
     }
     else
     if(X<T->Element)
     { 
        T->Left = Insert(X,T->Left);
        if(Height(T->Left) - Height(T->Right) == 2)
         if(X < T->Left->Element)
          T = SingleRotateWithLeft(T);
         else
          T = doubleRotateWithLeft(T);
     }
     else
     if(X>T->Element)
     { 
        T->Right = Insert(X,T->Right);
        if(Height(T->Right) - Height(T->Left) == 2)
         if(X < T->Right->Element)
          T = SingleRotateWithRight(T);
         else
          T = doubleRotateWithRight(T);
     }
     T->Height = Max( Height(T->Left), Height(T->Right) ) + 1;
     return T;
    }

这节内容应该着重学习 AVL树的特点  
以及插入数据后为了保持平衡所采用的旋转的思想。