AVL 平衡二叉树（LL,RR,LR,RT）

demo

平衡因子：某节点的左右子树的高度差

特点：

1. 每个节点的平衡因子只可能是1，0，-1（绝对值<=1,如果超过1，称之为失衡）
2. 每个节点的左右子树高度差不超过1
3. 搜索添加删除的时间复杂度为 O(logn)

LL （left - left）： 右旋转

在根节点的左边的左边失衡

            p
        q       p1
    n       q1
n1      n2

进行右旋转之后

p.left = q.right;
q.right = p;
q = root;//让 q 称为根节点

                q
        n               p
    n1      n2      q1      p1

RR (right - right) : 左旋转

在根节点的右边的右边失衡

                    p
                p1      q
                    q1      n
                        n1      n2

进行左旋转之后

                q
        p               n
    p1      q1      n1      n2
                

p.right = q.left;
q.left = p;
q = root;

LR（left-right）: 双旋

也就是在分界点的左子树的右子树超出了，所以为L,R

                                    p
                q                               m
        n           w                       m1
    n1      n1  w1      r
                            r1

先进行左旋转,q,w进行

                                p
                w                           m
            q       r                   m1
        n       w1      r1
    n1      n2
    

在进行右旋转,p 进行右旋转

                        w
            q                       p
        n       w1          r               m
    n1      n2                  r1      m1

RL（right - left）：双旋转

也就是在根节点的右子树的左子树超出，原理同上

删除节点

删除节点也会导致上面的四种情况，但是有一种极端情况，比如删除了一个叶子节点，然后进行旋转之后，整个子树的高度就减少了·，那么可能会导致整个树失衡，那么就需要对整个树进行平衡调整，最坏情况下需要 O(logn)次调整

总结

添加 ：可能会导致所有的祖先节点都失衡，但是只要让高度最低的那个节点平衡，那么整棵树就会平衡，只需要O(1)

删除 ： 会导致父节点或者祖父节点失衡，然后让父节点恢复平衡，但是可能恢复平衡后高度会降低，所以会导致所有的祖先节点都失去平衡，最坏情况下需要 O(logn) 次调整

时间复杂度：

搜索需要 O(logn)

添加需要 O(logn)，旋转需要 O(1)

删除：O(logn)，旋转最多需要 O(logn)