AVL树

定义

一棵AVL树可以是空树，
也可以是具有下列性质的二叉搜索树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。(右子树高度-左子树高度)

结点的平衡因子：给每个结点附加一个数字，给出该结点右子树的高度减去做技术的高度所得的高度差，这个数字即为结点的平衡因子。

如果一棵二叉搜索树的高度是平衡的，它就成为AVL树，如果它有n个节点，其高度可保持在O(以2为底的logn)

平衡化旋转
① 如果在一棵平衡的二叉搜索树欧中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。
② 平衡化旋转有两类：
单旋转（左旋和右旋）
双旋转（左平衡和右平衡）

每插入一个新结点时，AVL树中相关的平衡状态会发生改变，因此，在插入一个新结点后，需要从插入的位置沿向根的路径回溯，检查各节点的平衡因子。
如果在某一节点发现高度不平衡，停止回溯
从发生不平衡的结点起，沿刚才回溯的路径直接下两层的结点
如果这三个结点处于一条直线上，则采用单旋进行平衡化。单旋转可按其方向分为左单旋转和右单旋转，其中一个是另一个的镜像，其方向与不平衡的形状有关。
如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为先左后右和先右后左两类。

左单旋转

  // 左单旋转
    private void RotateLeft(AVLNode ptr){
        AVLNode newRoot = ptr.rightChild; // 1
        newRoot.parent = ptr.parent;  // 4 维护newroot的双亲
        zz
        if (newRoot.leftChild!=null) { 维护newroot的左孩子的双亲
            newRoot.leftChild.parent = ptr; // 5
        }
        newRoot.leftChild = ptr; // 3
        AVLNode pa = ptr.parent;
        if (pa==null){ // 判断ptr的双亲是否为空，有可能ptr以前是根节点。也有可能不是。
            root = newRoot;
        }else{
            if (pa.leftChild==null){
                pa.leftChild = newRoot;
            }else{
                pa.rightChild = newRoot;
            }
        }
        ptr.parent = newRoot; //维护ptr的双亲。
    }

右单旋转

// 右单旋转
    private void RotateRight(AVLNode ptr){
        AVLNode newroot = ptr.leftChild; //1
        newroot.parent = ptr.parent; // 4 维护newroot的双亲
        ptr.leftChild = newroot.rightChild; // 2
        if (newroot.rightChild!=null){   // 5 维护newroot右孩子的双亲
            newroot.rightChild.parent = ptr;
        }
        newroot.rightChild = ptr; // 3
        AVLNode pa =ptr.parent;// 4
        if (ptr.parent==null){
            root = newroot;
        }else{
            if (pa.leftChild==ptr){
                pa.leftChild = newroot;
            }
            if (pa.rightChild==ptr){
                pa.rightChild =newroot;
            }
        }
        ptr.parent = newroot; //6 维护ptr的双亲
    }

双旋转

若某一个节点的平衡因子发生改变，沿着回溯路径向下两层，以最后一层的节点为旋转点，进行先左单旋后右单旋。 或者进行先右单后左单旋。
现有一棵AVL树，每个节点都平衡因子的绝对值 都没有超过2，所以该AVL树是平衡的。

先左后右双旋转

现在我们可以往 1 2 3这三个位置插入节点。
情况一：
若我们向1位置插入节点。此时就变成了:

此时，我们插入的情况可能有两种，一种是a位置插入，一种是在b位置插入。此时 节点B的平衡因子变为-1，节点A的平衡因子变为-2.AVL树不平衡，需要旋转。
我们从新插入的节点开始，向上回溯至不平衡节点的位置，找到A结点，于是按照旋转规则，找到刚才回溯路径的包括A节点在内的3个节点。即A B C 我们开始进行旋转。所以，如果我们在1处插入节点，（无论是插到a还是b上）那我们需要旋转的条件就是，当B的平衡因子变为-1时，就需要进行单旋转。在进行完单旋转后，我们还需要将B的平衡因子重新赋值。
即进行单旋转后，B的右孩子指向A，A的左孩子指向B

通过图得，我们B的平衡因子置为0。A的平衡因子为0.

情况二：
当我们是新插入的节点是在B节点的右孩子插入，即在E的左孩子处插入，即我们图中2位置。

此时，B的平衡因子变为1，E的平衡因子又变为-1。（这里要注意，如果在E的右孩子插入，则E的平衡因子变为1，所以这里又要分情况讨论。）

我们先看E的平衡因子为-1的情况：
从新插入的节点D处开始向上查找 不平衡的节点，找到了A，于是按照遍历规则，A及其下两层的节点 开始旋转。由于 ABE 不在一条直线上，所以需要进行双旋转。
我们先以E为旋转点，EB进行左单旋转。

此时 B的平衡因子为0，再以E为旋转点，对EA进行右单旋。
此时 E的平衡因为0，A的平衡因子为1

情况三：
当我们新插入的节点，在B的右孩子插入，即在E的右孩子处插入时，即我们3号位置时：
我们通过回溯 查找到A节点的平衡因子为-2，不平衡，于是 找到ABE 不在一条直线上，使用双旋转。

我们以E为旋转点，对EB进行左单旋转。

再以E为旋转点，EA进行右旋转。

此时A的平衡因子为 0 E的平衡因子为0 B的平衡因子为-1。

具体代码实现：

   // 左平衡
    private void LeftBalance(AVLNode ptr){
        AVLNode leftSub = ptr.leftChild;
        AVLNode rightSub = null;
        switch(leftSub.balance){
            case 0:
                System.out.println("left balance");
                break;
            case -1:
                ptr.balance = 0;
                leftSub.balance = 0;
                RotateRight(ptr);
                break;
            case 1:
                rightSub = leftSub.rightChild;
                switch(rightSub.balance){
                    case -1:
                        ptr.balance = 1;
                        leftSub.balance = 0;
                    case 1:
                        ptr.balance = 0;
                        leftSub.balance = -1;
                    case 0:
                        // 特殊情况
                        ptr.balance = 0;
                        leftSub.balance = 0;
                }
                rightSub.balance = 0;
                RotateLeft(leftSub);
                RotateRight(ptr);
                break;
        }
    }

先右后左双旋转

是先左后右旋转的镜像。

AVL树的插入

  //插入
    public boolean insert(int val){
        AVLNode p = new AVLNode(val);
        adjust(p);
        return true;
    }
    // ptr指向插入的节点
    private void adjust(AVLNode ptr){
        AVLNode pa = ptr.parent;
        boolean high = true;
        // 若pa==null，说明pa指向根节点。
        while(high&&pa!=null){
            if (pa.leftChild == ptr){
                // 说明 ptr插入到pa的左边
                // 看左边的平衡因子
                switch(pa.balance){
                    case 0:
                        pa.balance = -1;
                        break;
                    case 1:
                        pa.balance = 0;
                        high = false;
                        break;
                        //pa.balance为-1时，说明原来左高右低
                    // 此时ptr插入的也是左边，导致左边不平衡，我们就要调用左平衡
                    case -1:
                        LeftBalance(pa);
                        high = false;
                        break;
                }
            }else{
                // 新添加的节点，在右边插入
                switch (pa.balance){
                    case 0:
                        pa.balance = 1;
                        break;
                    //pa.balance如果为-1，说明pa所指的这棵AVL 左高右低
                    // 此时ptr插入的是右边,刚好使AVL树平衡
                    case -1:
                        pa.balance = 0;
                        high = false;
                        break;
                        //pa.balance如果是1，说明原本pa所指的这棵AVL树 为 右高左低
                    // 此时 ptr插入右边，导致pa所指的AVL树 右高左低，所以调用右平衡
                    case 1:
                        rightBalance(pa);
                        high = false;
                        break;
                }
            }
            ptr = pa;
            pa = ptr.parent;
        }
    }