AVL构建
树的旋转
- 左旋
- 右旋
节点插入
节点删除
AVL的缺点

普通的二叉查找树（BST）虽然已经实现了对于节点的快速查找，但是如果树的拓扑结构没有设计正确，例如讲一个有序序列存入BST中，就会使BST的二分查找能力损失，也就是常说的失去了平衡。为了保证BST的查找能力，在BST形成过程中进行平衡调整，就形成了平衡二叉查找树，简称平衡二叉树（AVL-tree）。

AVL具备以下性质：

从任何一个节点出发，左子树和右子树的深度差的绝对值不超过1。这个深度差被称作平衡因子。
任何一个节点的左子树和右子树都是平衡二叉树。

通过AVL所实现的拓扑结构，就保证了树的二分查找能力，AVL在查找、插入和删除时的复杂度均为平衡二叉树 - 图1 。

AVL构建

要构建一棵AVL树，我们依旧可以使用前面定义的节点类，但是为了能够适应AVL树的一些额外属性和操作，我们还是需要将这个节点类扩展一下。

public class AVLNode extends BSTNode {
    private Integer depth;
    public AVLNode(Integer value) {
        super(value);
        this.depth = 0;
    }
    public Integer getDepth() {
        return this.depth;
    }
    public Integer setDepth(Integer depth) {
        this.depth = depth;
    }
    public void increaseDepth() {
        this.depth++;
    }
    public void decreaseDepth() {
        this.depth--;
    }
}

实例中的AVL树节点类增加了一个用于保存节点深度的属性，这个深度属性可以用来比较得出是否平衡的结论。

树的旋转

向一个AVL中插入或者删除一个节点，会导致AVL的不平衡。例如以下示例。
AVL插入节点.svg
左侧的AVL在插入一个新的节点5之后，就变得不平衡了。节点50的左子树的高度为4，右子树的高度为2，AVL已经失去了平衡。在这种失衡的情况下，AVL是通过旋转最小失衡子树来重新获取平衡的。那么这里就引入了一个新的名词：最小失衡子树。

最小失衡子树是指从新插入的节点向根查找，第一个平衡因子的绝对值超过1的节点即为最小失衡子树的根节点。一棵失衡的AVL树中，是可能会同时存在多棵失衡子树的，但是要使AVL树恢复平衡，只需要调整最小的失衡子树即可。

对失衡子树的调整是通过旋转来完成的，旋转子树的目的是降低树的高度。子树的旋转有两个方向：左旋和右旋，使用哪个方向是由子树的高度决定的。如果节点的右子树高度比较高，那么就采用左旋，降低右子树高度；反之，使用右旋可以降低左子树高度。

左旋

最小失衡子树的左旋可以遵循以下步骤处理：

子树根节点（ori）的右孩子（rc）替代根节点成为新的根节点。
右孩子（rc）的左子树变为原根节点（ori）的右子树。
原根节点（ori）变为右孩子（rc）的左子树。

具体操作实现可以参考以下例程。

public class AVLTree {
    public void rotateLeft(AVLNode root) {
        root.getRightChild().ifPresent(rightChild -> {
            root.getParent().ifPresent(parent -> {
                if (root.isLeftChild()) {
                    parent.attachLeftChild(rightChild);
                } else {
                    parent.attachRightChild(rightChild);
                }
            });
            rightChild.getLeftChild().ifPresent(root::attachRightChild);
            rightChild.attachLeftChild(root);
        });
    }
}

右旋

最小失衡子树的右旋非左旋正好相反，可以遵循以下步骤：

子树根节点（ori）的左孩子（lc）替代根节点成为新的根节点。
左孩子（lc）的右子树变为原根节点（ori）的左子树。
原根节点（ori）变为左孩子（lc）的右子树。

具体操作实现可以参考以下例程。

public class AVLTree {
    public void rotateRight(AVLNode root) {
        root.getLeftChild().ifPresent(leftChild -> {
            root.getParent().ifPresent(parent -> {
                if (root.isLeftChild()) {
                    parent.attachLeftChild(leftChild);
                } else {
                    parent.attachRightChild(leftChild);
                }
            });
            leftChild.getRightChild().ifPresent(root::attachLeftChild);
            leftChild.attachRightChild(root);
        });
    }
}

节点插入

向AVL中的某一个节点k的左右子树上插入一个新节点n，会有以下四种情况可以破坏原有AVL的平衡性：

在节点k的左子树根节点的左子树上插入节点n（简称LL插入）。要重新达到平衡需要执行右旋操作。
在节点k的右子树根节点的右子树上插入节点n（简称RR插入）。要重新达到平衡需要执行左旋操作。
在节点k的左子树根节点的右子树上插入节点n（简称LR插入）。要重新达到平衡需要先执行左旋操作，再执行右旋操作。
在节点k的右子树根节点的左子树上插入节点n（简称RL插入）。要重新达到平衡需要先执行右旋操作，再执行左旋操作。

由于新节点都是作为叶子节点插入，所以在完成节点插入以后，需要完成一项工作，就是更新所有父代节点的深度值。这个更新不需要遍历整棵树，只需要遍历新节点的所有父代路径即可。以下是深度值更新的示例。

public class AVLTree {
    public void updateDepth(AVLNode node) {
        if (node.isLeaf()) {
            node.setDepth(0);
        } else {
            Integer leftChildDepth = node.getLeftChild().get(AVLNode::getDepth).orElse(0);
            Integer rightChildDepth = node.getRightChild().get(AVLNode::getDepth).orElse(0);
            node.setDepth(IntStream
                              .of(leftChildDepth, rightChildDepth)
                              .map(d -> d + 1)
                              .max()
                              .orElse(0));
        }
        node.getParent().ifPresent(this::upateDepth);
    }
}

虽然在节点插入后的重新平衡有四种情况，但是总结起来，只是一个不断遍历新插入节点的父级路径，使其父级路径重新平衡的过程。而在这个过程中，针对每一个节点，可以判断其左右子树的深度值，如果左侧的深度大于右侧的深度，那么就采用右旋进行平衡；反之采用左旋进行平衡。

以下是一个处理新插入节点并实现再平衡的示例。

public class AVLTree {
    public void insert(Integer value) {
        // 这个pointer十分有用，可以用来对树进行遍历和操作
        AVLNode pointer = this.root;
        ANLNode newNode = new AVLNode(value);
        // 首先完成节点的插入
        while (!pointer.isLeaf()) {
            if (pointer.compareTo(newNode) > 0) {
                pointer = pointer.getRightChild().get();
                continue;
            }
            if (pointer.compareTo(newNode) < 0) {
                pointer = pointer.getLeftChild().get();
                continue;
            }
            if (pointer.compareTo(newNode) == 0) {
                throw new RepeatValueException();
            }
        }
        if (newNode.compareTo(pointer) < 0) {
            pointer.attachLeftChild(newNode);
        } else {
            pointer.attachRightChild(newNode);
        }
        this.updateDepth(newNode);
        // 然后开始对新节点的父级路径进行再平衡
        pointer = newNode;
        while (pointer.getParent().isPresent()) {
            Integer leftChildDepth = pointer.getLeftChild().map(AVLNode::getDepth).orElse(0);
            Integer rightChildDepth = pointer.getRightChild().map(AVLNode::getDepth).orElse(0);
            if (Math.abs(leftChildDepth - rightChildDepth) > 1) {
                if (leftChildDepth > rightChildDepth) {
                    this.rightRotate(pointer);
                } else {
                    this.leftRotate(pointer);
                }
                this.updateDepth(pointer);
                pointer = newNode;
            } else {
                pointer = pointer.getParent().get();
            }
        }
    }
}

实例代码中虽然不仅对仅需要再平衡的最小失衡子树进行了平衡，而且也同时扫描了新插入节点的所有父级路径。这样做的目的主要是把需要两次旋转的操作化简到了一个循环中。由于每次仅会扫描一条路径，所以增加的复杂度有限。

节点删除

AVL中的节点删除与BST中的节点删除操作是相同的，只是AVL在完成删除操作以后需要修正所有的不平衡节点。一般都会分为以下四种情况来处理。

被删除节点是叶子节点。
被删除节点只有左子树。
被删除节点只有右子树。
被删除节点既有左子树又有右子树。

在完成节点的删除以后，可以选择被删除节点的左右子树中深度较大的那一支，来更新整条路径上的节点深度，并进行再平衡操作。

AVL的缺点

AVL在大量查找操作的情况下效率会更高，但是对于增删操作，AVL会进行大量的再平衡操作，这样就大大降低了AVL的性能。所以在查找操作远大于增删操作次数的时候，使用AVL会得到更高的效率。如果在树中的增删操作比较多，那么可以选择增删性能更高的红黑树。