为什么需要平衡二叉树？

首先我们思考一个问题，为什么要学习平衡二叉树（AVL），是二叉排序树（BST）不香嘛？

哎，确实，确实不香。

二叉排序树存在一个致命缺点，如下图所示这种情况：

image-20200425084803240

emmmm，这确实也是一个二叉排序树，但是乍一看，害，这不整一条链表过来装树嘛！

在这种情况下，二叉排序树退化成一条链表

链表的特点是什么？（给你三秒种反应）

3

2

1

对了！增删快、查找慢，这与我们建立二叉排序树的初衷相悖

为此，我们引入了今天的主角，平衡二叉树（Self-balancing binary search tree）！

基本介绍

  • 平衡二叉树也叫平衡二叉搜索树，又被称为AVL树，可以保证查询效率较高
  • 具有以下特点：
    • 是一颗空树或左右两个子树的高度差的绝对值不超过1
    • 左右两个子树都是一颗平衡二叉树

平衡二叉树的实现方法：红黑树（HashMap、TreeMap底层都有用到）、AVL、替罪羊树、Treap、伸展树

应用实例

每当 平衡二叉树满足：
$$
|rightHeight() - leftHeight()| > 1
$$
时，不再是一颗平衡二叉树，需要进行旋转操作使其恢复平衡。

左旋(降低右子树的高度)：

给定数列 {4，3，6，5，7，8}，创建出对应的二叉平衡树image-20200425093659703

注意到当插入 8 时，不满足平衡二叉树的条件，此时需要对二叉树进行左旋，才能使其恢复平衡

image-20200425093714198

具体流程：

1
2
3
4
5
6
7
8
9
10
11
12
13
//当前节点：0004
//1. 以根节点的值为值创建新节点
Node newNode = new Node(4)；
//2. 将新节点的左子树设置为当前节点的左子树
newNode.left = this.left;
//3. 把新结点的右子树设为当前节点的右子树的左子树
newNode.right = this.right.left;
//4. 把当前节点的值换为右子节点的值
this.value = right.value;
//5. 把当前节点的右子树设置成右子树的右子树
this.right = this.right.right;
//6. 当前节点的左子树设置为新节点
this.left = newNode;

右旋(降低左子树的高度)：

给定数列 {10，12，8，9，7，6} 创建对应平衡二叉树image-20200425095021888

当插入节点 6 时，不满足平衡二叉树的条件，此时需要对二叉树进行右旋，才能使其恢复平衡

image-20200425095126703

具体实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
//当前节点：0008
//1. 创建一个以根节点为值的新节点
Node newNode = new Node(10)；
//2. 将新节点的右子树设置为当前节点的右子树
newNode.right = this.right;
//3. 新节点的左子树设置为当前节点左子树的右子树
newNode.left = this.left.right;
//4. 将当前节点的值换为左子节点的值
this.value = right.value;
//5. 将当前节点的左子树设置为左子树的左子树
this.left = this.left.left;
//6. 将当前节点的右子树设置为新节点
this.right = newNode;

总结一下左旋和右旋的实现：

  1. 创建新节点
  2. 设置新节点的左右子树
  3. 设置当前节点的左右子树

双旋转

前面的两个实例都可以通过一次旋转将非平衡二叉树转化为平衡二叉树，但是在一些情况下，单旋转不能完成平衡二叉树的转换，比如数列 {10，11，7，6，8，9}、{2，1，6，5，7，3}

问题分析：

  1. 当符合右旋条件时
  2. 如果当前节点的左子树的右子树高于当前节点的右子树
  3. 应当先对当前节点的左子树进行左旋
  4. 再对当前节点进行右旋
image-20200425102817626

代码实现

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
//Node：

public int leftHeight() {
    if (this.left == null) {
        return 0;
    }
    return this.left.height();
}

public int rightHeight() {
    if (this.right == null) {
        return 0;
    }
    return this.right.height();
}

//使用递归的方法返回当前节点的高度
public int height() {
    return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
}

//左旋：参考“具体流程”
public void leftRotate() {
    Node newNode = new Node(this.value);
    newNode.left = this.left;
    newNode.right = this.right.left;
    this.value = this.right.value;
    this.right = this.right.right;
    this.left = newNode;
}

//右旋：参考“具体流程”
public void rightRotate() {
    Node newNode = new Node(this.value);
    newNode.right = this.right;
    newNode.left = this.left.right;
    this.value = this.right.value;
    this.left = this.left.left;
    this.right = newNode;
}

public void add(Node node) {
    //先判断加入的节点是否为空
    if (node == null) {
        return;
    }
    //当加入节点的值小于当前节点的值时，考虑左子节点
    if (node.value < this.value) {
        if (this.left == null) {
            this.left = node;
        } else {
            this.left.add(node);
        }
    } else { //当加入节点的值大于当前节点的值时，考虑右子节点
        if (this.right == null) {
            this.right = node;
        } else {
            this.right.add(node);
        }
    }

    //判断是否需要进行左旋
    if (rightHeight() - leftHeight() > 1) {
        //判断是否需要双旋转
        if (right != null && right.leftHeight() - right.rightHeight() > 1) {
            right.rightRotate();
            leftRotate();
        } else {
            leftRotate();
        }
        return;
    }

    //判断是否需要右旋
    if (leftHeight() - rightHeight() > 1) {
        //判断是否需要双旋转
        if (left != null && left.rightHeight() - left.leftHeight() > 1) {
            left.leftRotate();
            rightRotate();
        } else {
            rightRotate();
        }
    }
}


参考

尚硅谷：https://www.bilibili.com/video/BV1E4411H73v