数据结构基础11———非线性数据结构之自平衡二叉树之AVL树

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

AVL树本质上还是一棵二叉搜索树，它的特点是：
1.本身首先是一棵二叉搜索树

2.带有平衡条件：每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1
_{粗略的说一棵AVL树高度最多为1.44log(N + 2) - 1.328}

3.它的左右子树都是AVL树

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log2N） ，搜索时间复杂度O(log2N )

也就是说，AVL树，本质上是带了平衡功能的二叉查找树（二叉排序树，二叉搜索树）

如下图：节点中的数代表节点的值，左右两侧的数代表左右子树的高度。a, b是AVL树，c,d不是，因为c/d不满足AVL的平衡条件。

场景：
二叉树退化成一条链表。回想上一章在计算时间复杂度时有一种极端情况，所有的节点都在一边上，导致二叉查找树直接退化成了一个线性链表结构。

所以问题来了：如何优化二叉查找树防止过度退化呢？
我们可以看到：防止二叉查找树退化本质上就是平衡左右子树的高度，也就是让左右子树的高度差趋近于0.或者说如何保证 二叉查找树的拓扑结构始终保持树高度与节点数量的最佳比例？（平衡因子:某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。如果某一结点的平衡因子绝对值大于1则说明此树不是平衡二叉树。为了方便计算每一结点的平衡因子我们可以为每个节点赋予height这一属性，表示此节点的高度。)

而通过某种方式平衡左右子树高度的数据结构结构就叫做平衡二叉树。而AVL树是其一种较为经典的实现（最严格，但是实际应用其实并不多。大部分常见还是红黑树更简便实用）

AVL实现平衡的操作——旋转
因为只有插入删除会导致不平衡，这里我们先假定懒惰删除（只标记不真的删除）。在插入时我们需要更新通向根节点路径上的所有节点的平衡信息，插入后可能会破坏AVL树的平衡结构，这个时候我们需要将树重新恢复平衡，这样的一个操作就被称之为“旋转”
沿着这个路径我们可以找到一个不满足AVL平衡的节点（最深的节点）。这里我们将需要平衡的节点称之为x，由于任意节点最多只有两个子节点，因此要出现不平衡就需要x的左右子树高度差至少为2.
因此不平衡的情况只会有以下4种：

1.在x左儿子的左子树进行一次插入
2.在x左儿子的右子树进行一次插入
3.在x右儿子的左子树进行一次插入
4.在x右儿子的右子树进行一次插入

情形1-4和2-3都关于节点x镜像对称，所以理论上只有两种情况当然从代码角度来说还是是4种。
如果有想象力的话可以想象树上每根线是绳子，吊着小球重物拿着节点抖两下自由滑动。。。
单旋转：轴为相应子节点。左旋或右旋
双旋转：先左旋再右旋或先右旋再左旋转两次
左左,右右单旋转
左右,右左双旋转

AVL树的旋转类型有4种， 分别是LL(left-left)旋转、LR(left-right)旋转、RR(right-right)旋转和RL(right-left)旋转。

为方便理解在何时执行哪一种旋转，设x代表刚插入AVL树中的结点，设A为离x最近且平衡因子更改为2的绝对值的祖先。可以归纳为下面4种处理情况：

LL旋转

设left为A的左子树，要执行LL旋转，将A的左指针指向left的右子结点，left的右指针指向A，将原来指向A的指针指向left。

旋转过后，将A和left的平衡因子都改为0。所有其他结点的平衡因子没有发生变化。

LR旋转

设left是A的左子结点，并设A的子孙结点grandchild为left的右子结点。

要执行LR旋转，将left的右子结点指向grandchild的左子结点，grandchild的左子结点指向left，A的左子结点指向grandchild的右子结点，再将grandchild的右子结点指向A，最后将原来指向A的指针指向grandchild。

执行LR旋转之后，调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子值。

如果grandchild结点的原始平衡因子为+1，就将A的平衡因子设为-1，将left的平衡因子设为0。

如果grandchild结点的原始平衡因子为0，就将A和left的平衡因子都设置为0。

如果grandchild结点的原始平衡因子为-1，就将A的平衡因子设置为0，将left的平衡因子设置为+1。

在所有的情况下，grandchild的新平衡因子都是0。所有其他结点的平衡因子都没有改变。

RR旋转

当x位于A的左子树的右子树上时，执行RR旋转。

RR旋转与LL旋转是对称的关系。

设A的右子结点为Right。要执行RR旋转，将A的右指针指向right的左子结点，right的左指针指向A，原来指向A的指针修改为指向right。

完成旋转以后，将A和left的平衡因子都修改为0。所有其他结点的平衡因子都没有改变。

RL旋转

当x位于A的右子树的左子树上时，执行RL旋转。

RL旋转与LR旋转是对称的关系。

设A的右子结点为right，right的左子结点为grandchild。要执行RL旋转，将right结点的左子结点指向grandchild的右子结点，将grandchild的右子结点指向right，将A的右子结点指向grandchild的左子结点，将grandchild的左子结点指向A，最后将原来指向A的指针指向grandchild。

执行RL旋转以后，调整结点的平衡因子取决于旋转前grandchild结点的原平衡因子。这里也有三种情况需要考虑：

如果grandchild的原始平衡因子值为+1，将A的平衡因子更新为0，right的更新为-1；

如果grandchild的原始平衡因子值为 0，将A和right的平衡因子都更新为0；

如果grandchild的原始平衡因子值为-1，将A的平衡因子更新为+1，right的更新为0；

在所有情况中，都将grandchild的新平衡因子设置为0。所有其他结点的平衡因子不发生改变。

删除后平衡
AVL树和二叉查找树的删除操作情况一致，都分为三种情况，只不过AVL树在删除节点后需要重新检查平衡性并修正，同时，删除操作与插入操作后的平衡修正区别在于，插入操作后只需要对插入栈中的弹出的第一个非平衡节点进行修正，而删除操作需要修正栈中的所有非平衡节点。

三种情况如下：假设被删除节点为N

1.N为叶子节点：直接删除

2.被N只有一个儿子：将父亲节点的相应儿子引用直接指向N的儿子

3.N有两个儿子：找到N的右子树中最小的节点N_R_MIN，该节点一定无左儿子；我们将N_R_MIN的值赋给N节点，然后删除N_R_MIN即可。（此时删除N_R_MIN节点属于前两种情况）

删除操作的大致步骤如下：

以前两种情况为基础尝试删除节点，并将访问节点入栈。
如果尝试删除成功，则依次检查栈顶节点的平衡状态，遇到非平衡节点，即进行旋转平衡，直到栈空。
如果尝试删除失败，证明是第三种情况。这时先找到被删除节点的右子树最小节点并删除它，将访问节点继续入栈。
再依次检查栈顶节点的平衡状态和修正直到栈空。
对于删除操作造成的非平衡状态的修正，可以这样理解：对左或者右子树的删除操作相当于对右或者左子树的插入操作，然后再对应上插入的四种情况选择相应的旋转就好了。

AVL树的实现：

public class AVLBalanceTree<T extends Comparable<T>> {

    private TreeNode<T> root;

    public AVLBalanceTree() {
    }

    private class TreeNode<E> {
        T element;
        int height;
        TreeNode<T> left;
        TreeNode<T> right;

        TreeNode(T e) {
            element = e;
        }

        boolean isBalanced() {
            int leftHeight = left == null ? -1 : left.height;
            int rightHeight = right == null ? -1 : right.height;
            return Math.abs(leftHeight - rightHeight) <= 1 ? true : false;
        }

        public String toString() {
            return "Element:" + element + " Height:" + height + " Balanced:" + isBalanced();
        }
    }

    private int calHeight(TreeNode<T> node) {
        if (node == null) {
            return -1;
        }
        int leftHeight = node.left == null ? -1 : node.left.height;
        int rightHeight = node.right == null ? -1 : node.right.height;
        return Math.max(leftHeight, rightHeight) + 1;
    }

    // 非递归算法部分
    public void insertNonRecursive(T e) {
        LinkedList<TreeNode<T>> trace = new LinkedList<>();
        insertNonRecursive0(e, trace);
        reBalanceAfterInsert(trace, e);
    }

    private void reBalanceAfterInsert(LinkedList<TreeNode<T>> trace, T e) {
        TreeNode<T> unBalanceNode = null;
        TreeNode<T> unBalNodeParent = null;
        TreeNode<T> n = null;
        while ((n = trace.peek()) != null && unBalanceNode == null) {
            n = trace.pop();
            n.height = calHeight(n);
            if (!n.isBalanced()) {
                unBalanceNode = n;
            }
        }
        if (trace.peek() != null) {
            unBalNodeParent = trace.pop();
        }
        // 平衡状态 返回
        if (unBalanceNode == null) {
            return;
        }
        // 确定插入方式
        int compareInt = unBalanceNode.element.compareTo(e);
        if (compareInt > 0) {
            if (calHeight(unBalanceNode.left.left) - calHeight(unBalanceNode.left.right) > 0) {
                rotateRight(unBalanceNode, unBalNodeParent);
            } else {
                // 先左旋时，视原非平衡节点的左儿子为非平衡节点
                rotateLeft(unBalanceNode.left, unBalanceNode);
                rotateRight(unBalanceNode, unBalNodeParent);
            }
        } else if (compareInt < 0) {
            if (calHeight(unBalanceNode.right.left) - calHeight(unBalanceNode.right.right) < 0) {
                rotateLeft(unBalanceNode, unBalNodeParent);
            } else {
                rotateRight(unBalanceNode.right, unBalanceNode);
                rotateLeft(unBalanceNode, unBalNodeParent);
            }
        }
        // 旋转完毕，旋转子树的高度信息已经更新过了，继续更新非平衡节点以上的高度信息
        while ((n = trace.peek()) != null) {
            n = trace.pop();
            n.height = calHeight(n);
        }
    }

    private void rotateRight(TreeNode<T> unBalanceNode, TreeNode<T> unBalNodeParent) {
        TreeNode<T> newRoot = unBalanceNode.left;
        TreeNode<T> ubParent = unBalNodeParent;
        // 周知树其余部分
        if (ubParent != null) {
            if (ubParent.left != null && ubParent.left.equals(unBalanceNode)) {
                ubParent.left = newRoot;
            } else {
                ubParent.right = newRoot;
            }
        } else {
            this.root = newRoot;
        }
        // 儿子移交
        if (newRoot.right != null) {
            unBalanceNode.left = newRoot.right;
        } else {
            unBalanceNode.left = null;
        }
        // 新根上任，左儿子无需处理
        newRoot.right = unBalanceNode;

        // 更新三个节点的高度信息
        unBalanceNode.height = calHeight(unBalanceNode);
        newRoot.height = calHeight(newRoot);
        if (ubParent != null) {
            ubParent.height = calHeight(ubParent);
        }
    }

    private void rotateLeft(TreeNode<T> unBalanceNode, TreeNode<T> unBalNodeParent) {
        TreeNode<T> newRoot = unBalanceNode.right;
        TreeNode<T> ubParent = unBalNodeParent;

        if (ubParent != null) {
            if (ubParent.left != null && ubParent.left.equals(unBalanceNode)) {
                ubParent.left = newRoot;
            } else {
                ubParent.right = newRoot;
            }
        } else {
            this.root = newRoot;
        }

        if (newRoot.left != null) {
            unBalanceNode.right = newRoot.left;
        } else {
            unBalanceNode.right = null;
        }

        newRoot.left = unBalanceNode;

        unBalanceNode.height = calHeight(unBalanceNode);
        newRoot.height = calHeight(newRoot);
        if (ubParent != null) {
            ubParent.height = calHeight(ubParent);
        }
    }

    private void insertNonRecursive0(T e, LinkedList<TreeNode<T>> trace) {
        TreeNode<T> node = new TreeNode<>(e);
        if (root == null) {
            root = node;
            root.height = 0;
            return;
        }
        TreeNode<T> current = root;
        trace.push(current);
        int compareInt = 0;
        while (true) {
            compareInt = current.element.compareTo(e);
            if (compareInt > 0) {
                if (current.left == null) {
                    current.left = node;
                    trace.push(node);
                    return;
                }
                current = current.left;
                trace.push(current);
            } else if (compareInt < 0) {
                if (current.right == null) {
                    current.right = node;
                    trace.push(node);
                    return;
                }
                current = current.right;
                trace.push(current);
            } else {
                // 相等 不插入
                return;
            }

        }
    }

    public void removeNonRecursive(T e) {
        LinkedList<TreeNode<T>> trace = new LinkedList<>();
        TreeNode<T> current = root;
        trace.push(current);
        // 尝试删除，该节点没有儿子或者只有一个儿子
        if (tryRemove(e, trace, current)) {
            // 更新节点高度信息，修正平衡状态
            // 此时栈顶为被删除节点的父节点或者空栈
            if (trace.isEmpty()) {
                return;
            }
            // 弹出栈，更新高度信息并检查平衡
            reBalanceAfterRemove(trace, e);
        } else {
            // 尝试失败，该节点有两个儿子，此时栈顶元素即为将要删除的节点A
            current = trace.peek();
            // 找到A的右子树中最小的节点B，该节点没有左儿子
            TreeNode<T> rMin = findMin(current.right);
            // 此时删除目标变为最小的右儿子B
            tryRemove(rMin.element, trace, current);
            reBalanceAfterRemove(trace, rMin.element);
            // 删除完成，将B的值替换到原来要删除的节点A上
            current.element = rMin.element;
        }
    }

    private void reBalanceAfterRemove(LinkedList<TreeNode<T>> trace, T e) {
        while (true) {
            TreeNode<T> n = null;
            TreeNode<T> unBalanceNode = null;
            TreeNode<T> unBalNodeParent = null;
            while ((n = trace.peek()) != null && unBalanceNode == null) {
                n = trace.pop();
                n.height = calHeight(n);
                if (!n.isBalanced()) {
                    unBalanceNode = n;
                }
            }

            // 平衡态
            if (unBalanceNode == null) {
                return;
            }

            unBalNodeParent = trace.peek();

            int compareInt = unBalanceNode.element.compareTo(e);

            // 被删除节点是不平衡节点的左儿子，则右子树高于左子树
            if (compareInt > 0) {
                // 如果不平衡节点的右儿子的左子树高于右子树，则需要先右后左双旋转（相当于右左插入）
                if (calHeight(unBalanceNode.right.left) - calHeight(unBalanceNode.right.right) > 0) {
                    rotateRight(unBalanceNode.right, unBalanceNode);
                    rotateLeft(unBalanceNode, unBalNodeParent);
                } else {
                    // 相等和小于的情况 都可以通过左旋平衡
                    rotateLeft(unBalanceNode, unBalNodeParent);
                }
            } else {
                // 相当于左右插入
                if (calHeight(unBalanceNode.left.left) - calHeight(unBalanceNode.left.right) < 0) {
                    rotateLeft(unBalanceNode.left, unBalanceNode);
                    rotateRight(unBalanceNode, unBalNodeParent);
                } else {
                    // 相等和大于的情况 都可以通过右旋平衡
                    rotateRight(unBalanceNode, unBalNodeParent);
                }
            }

            for (TreeNode<T> n1 : trace) {
                n1.height = calHeight(n1);
            }
        }
    }

    private boolean tryRemove(T e, LinkedList<TreeNode<T>> trace, TreeNode<T> current) {
        while (true) {
            int compareInt = current.element.compareTo(e);
            if (compareInt > 0) {
                if (current.left == null) {
                    // 没有找到节点 直接返回
                    return true;
                }
                current = current.left;
                trace.push(current);
            } else if (compareInt < 0) {
                if (current.right == null) {
                    // 没有找到节点
                    return true;
                }
                current = current.right;
                trace.push(current);
            } else {
                // 找到元素，情况一：该节点为叶子节点
                if (current.left == null && current.right == null) {
                    // 弹出被删除节点
                    trace.pop();
                    if (current == root) {
                        root = null;
                        return true;
                    }
                    TreeNode<T> parent = trace.peek();
                    // 查询父节点
                    if (parent.left == current) {
                        parent.left = null;
                        return true;
                    } else {
                        parent.right = null;
                        return true;
                    }
                }
                // 找到元素，情况二：该节点只有一个儿子

                if (current.left == null) {
                    trace.pop();// 弹出被删除节点
                    TreeNode<T> son = current.right;
                    if (current == root) {
                        root = son;
                        return true;
                    }
                    TreeNode<T> parent = trace.peek();
                    if (parent.left == current) {
                        parent.left = son;
                        return true;
                    } else {
                        parent.right = son;
                        return true;
                    }
                }

                if (current.right == null) {
                    trace.pop();// 弹出被删除节点
                    TreeNode<T> son = current.left;
                    if (current == root) {
                        root = son;
                        return true;
                    }
                    TreeNode<T> parent = trace.peek();
                    if (parent.left == current) {
                        parent.left = son;
                        return true;
                    } else {
                        parent.right = son;
                        return true;
                    }
                }
                // 找到节点，情况三：但是节点有两个儿子，返回false
                return false;
            }
        }

    }
}