平衡二叉树AVL

左右子树高度差的绝对值不超过1
当插入或删除导致不平衡时，调整最小不平衡数，即以插入路径上离插入结点最近的平衡因子大于1的结点作为根的子树

平衡二叉树LL与RR.PNG
平衡二叉树LR.PNG
平衡二叉树RL.PNG
注意：LR与RL时，新结点究竟是插在C的左子树上还是右子树上是不影响旋转过程的。
查找效率
含有n个结点的平衡二叉树的最大深度为O(log(2)n)，平均查找长度为O(log(2)n)
向上取整(log(2)(n+1))
高度为h的AVL树中，最少结点树为S(h)=S(h-1)+S(h-2)+1
S(0)=1 S(1)=2

typedef struct{
    Comparable element;
    AVLNode *left;
    AVLNode *right;
    int height;   //以该结点为根的子树的高度，空树为-1.单节点为0
}

int GetH(AVLNode *t) const
{
    return t==NULL?-1:t->height;
}

void insert(const Comparable &x, AVLNode *&t)
{
    if(t==NULL)
        t=new AVLNode(x, NULL, NULL);
    else if(x<t->element){
        insert(x, t->left);
        if(GetH(t->left)-GetH(t->right)==2)
            if(x<t->left->element)
                rotateWithLeftChild(t);    //LL
            else
                doubleWithLeftChild(t);    //LR
    }
    else if(x>t->element){
        insert(x, t->left);
        if(GetH(t->left)-GetH(t->right)==2)
            if(x>t->right->element)
                rotateWithRightChild(t);    //RR
            else
                doubleWithRightChild(t);    //RL
    }
    t->height=max(GetH(t->left), GetH(t->right))+1;
}

//LL
void rotateWithLeftChild(AVLNode *&k2)
{
    AVLNode *k1=k2->left;
    k2->left=k1->right;
    k1->right=k2;
    k2->height=max(GetH(k2->left), GetH(k2->right))+1;
    k1->height=max(GetH(k1->left), GetH(k1->right))+1;
    k2=k1;   //指向新根以更新父节点的孩子指针
}

//RR
void rotateWithRightChild(AVLNode *&k1)
{
    AVLNode* k2=k1->right;
    k1->right=k2->left;
    k2->left=k1;
    k2->height=max(GetH(k2->left), GetH(k2->right))+1;
    k1->height=max(GetH(k1->left), GetH(k1->right))+1;
    k1=k2;
}

//LR
void doubleWithLeftChild(AVLNode *&k3)
{
    rotateWithRightChild(k3->left);
    rotateWithLeftChild(k3);
}