AVL树

带有平衡条件的二叉树，通常要求每颗树的左右子树深度差<=1

可以将破坏平衡的插入操作分为四种，最后通过旋转恢复平衡

破坏平衡的插入方式	描述	恢复平衡旋转方式
LL	在左儿子的左子树进行插入	右旋转
RR	在右儿子的右子树进行插入	左旋转
LR	在左儿子的右子树进行插入	先左旋转后右旋转
RL	在右儿子的左子树进行插入	先右旋转后左旋转

AVL树的实现

AVL树的节点声明

struct AvlNode ;
typedef struct AvlNode *Poisition ;
typedef struct AvlNode *AvlTree ;

AvlTree MakeEmpty(AvlTree T) ;
Position Find(ElementType X, AvlTree T) ;
Position FindMin(AvlTree T) ;
Position FinMax(AvlTree T) ;
AvlTree Insert(ElementType X, AvlTree T) ;
AvlTree Delete(ElementType X, AvlTree T) ;
ElementType Retrieve(Poisition P) ;

struct AvlNode
{
    ElementType Element ;
    AvlTree Left ;
    AvlTree Right ;
    int Height ;
}

计算AVL节点高度函数

int Height(Position P)
{
    if(P == NULL)
        return -1 ;
    else
        P->Height ;
}

向AVL树插入节点的函数

AvlTree Insert(ElementType X, AvlTree T)
{
    if(T == NULL)
    {
        T = malloc(sizeof(struct AvlTree)) ;
        if(T == NULL)
            Error("内存不足") ；
        T->Element = X ;
        T->Height = 0 ;
        T-Left = T->Right = NULL ;
    }
    else if(X < T->Element)
    {
        T->Left = Insert(X,L->Left,)
        if(Height(T->Left) - Height(T->Right)) == 2//如果平衡被破坏了，则执行旋转
            if(X < T->Left->Element) //LL
                T = SingleRotateWithLeft(T) ;
            else //LR
                T = DoubleRotateWightLeft(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) // RR
                T = SingleRotateWithRight(T) ;
            else //RL
                T = DoubleRotateWithRight(T) ;
    }
}

在左儿子上的单旋转

右旋

Position SingleRotateLeft(Position K2) //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) + ;
    
    return K1 ;
}

在左儿子上的双旋转

先左旋后后旋

Position DoubleRotateRight(Position K2)
{
    K3->Left = SinglRotateRight(K3->Left) ;
    
    retrun SinglRotateLeft(K3) ;
}

伸展树

目的：加快访问效率

基本想法：当一个节点被访问后，经过一系列的AVL树的旋转到达根节点

伸展树的实现

类型声明

struct SplayTree ;
typedef struct SplayTree *Position ;
typedef struct SplayTree *SplayTree ;

Position FindMin(SplayTree T) ;
Position FinMax(SplayTree T) ;
Position Find(SpalyTree T, ElementType X) ;
Position Insert(SpalyTree T, ElementType X) ;
Position Delete(SpalyTree T, ElementType X) ;
Position Splay(SpalyTree T, ElementType X) ;

Find函数

Position Find(SplayTree T, ElementType X)
{
        if(T == NULL)
            return NULL ;
        else if(X < T->Left->Element)
            return Find(T->Left,X) ;
        else if(X > T->Right->Element)
            return Find(T-Right,X) ;
        
        return T ;
}

Splay函数

把对应节点旋转至根节点，分在左子树和右子树两种情况；

SplayTree Splay(SplayTree T,ElementType X)
{
    SplayTree N ,K1,R,L;
    N->Left = N->Right = NULL ;
    
    if(T == NULL)
        return NULL ;
    while(true)
    {
        if(X < T->Element)
        {
            if(T->Left == NULL)
                break ;
            if(X < T->Left->Element)
            {
                K1 = T->Left ;
                T->Left = K1->Right ;
                K1->Right = T ;
                if(T->Right == NULL)
                    break ;
            }
            R->Left = T ;
            R = T ;
            T = T->Left ;
        }
        
        else if(X > Element)
        {
            if(T->Right == NULL)
                return NULL ;
            if(X > T-Right->Element)
            {
                K1 = T->Right;
                T->Right = K1->Left;
                K1->left = T;
                T = K1;
                if (T->Right == NULL) 
                    break;
            }
            L->Right = T ;
            L = T ;
            T = T->Right ;
        }
        else
        {
            break ;
        }
    }
    L->Right = T->Left;           
    R->Left = T->Right;
    T->Left = N->Right;
    Tree->Right = N->Left;
    
    return T ;
}

Delete函数

SplayTree Delete(SplayTree T, ElementType X)
{
    SplayTree S ;
    if(T == NULL)
        return NULL ;
    if(Find(T,X) == NULL)
        return T ;
    T = Splay(T, X);
 
    if (T->Left != NULL)
    {
         S = Splay(T->Left, X);
         S->Right = T->Right;
    }
    else
        S = T->Right ;
        
        free(T);
 
    return X;
}

总结

二叉树、AVL树、伸展树都是一种特殊的树，都是为了更好更快的执行某种操作。