自平衡二叉树

发布时间：2021-04-13 12:09
最后更新：2021-04-13 12:09
所属分类：
架构知识 算法设计

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

自平衡二叉树的英文缩写是采用其两位发明者的名字，所以与其直译英文Self-balanced Binary Search Tree不同。

AVL具备以下性质：

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

通过AVL所实现的拓扑结构，就保证了树的二分查找能力，AVL在查找、插入和删除时的复杂度均为$O(logN)$。

AVL树构建

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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树插入节点导致不平衡
AVL树插入节点导致不平衡

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

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

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

左旋

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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);
    });
}

右旋

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

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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的平衡性：

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

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);
}

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

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

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在完成删除操作以后需要修正所有的不平衡节点。一般都会分为以下四种情况来处理。

  1. 被删除节点是叶子节点。
  2. 被删除节点只有左子树。
  3. 被删除节点只有右子树。
  4. 被删除节点既有左子树又有右子树。

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

AVL树的缺点

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

系列文章

  1. 二叉树基础
  2. 二叉查找树
  3. 自平衡二叉树
索引标签
架构知识
算法设计
树形结构
数据结构
二叉树
平衡二叉树
Java