羊村懒王

这个屌丝很懒，什么也没留下！

热门标签

平衡二叉树详解通俗易懂

作者：羊村懒王 | 2024-04-30 05:19:48

踩

平衡二叉树

平衡二叉树（AVL）

阅读之前请先了解二叉搜索树

Golang 交流群关注公众号邓嘉文Jarvan

平衡二叉树定义：任意节点的子树的高度差都小于等于 1

1. 为什么使用「平衡二叉树」

二叉树能提高查询的效率 O(logn)，但是当你插入 {1,2,3,4,5,6} 这种数据的时候，你的二叉树就像一个「链表」一样，搜索效率变为 O(n)

于是在 1962 年，一个姓 AV 的大佬（G. M. Adelson-Velsky）和一个姓 L 的大佬（ Evgenii Landis）提出「平衡二叉树」（AVL）。

于是插入 {1,2,3,4,5,6} 这种数据结果如下图所示：

2. 判断「平衡二叉树」

判断「平衡二叉树」的 2 个条件：

1. 是「二叉排序树」
2. 任何一个节点的左子树或者右子树都是「平衡二叉树」（左右高度差小于等于 1）

（1）下图不是「平衡二叉树」因为它不是「二叉排序树」违反第 1 条件

（2）下图不是「平衡二叉树」因为有节点子树高度差大于 1 违法第 2 条件

（3）下图是「平衡二叉树」因为符合 1、2 条件

3. 相关概念

3.1 平衡因子 BF

定义：左子树和右子树高度差

计算：左子树高度 - 右子树高度的值

别名：简称 BF（Balance Factor 而不是 Boy Friend）

一般来说 BF 的绝对值大于 1，,平衡树二叉树就失衡，需要「旋转」纠正

3.2 最小不平衡子树

距离插入节点最近的，并且 BF 的绝对值大于 1 的节点为根节点的子树。

「旋转」纠正只需要纠正「最小不平衡子树」即可

例子如下图所示：

4. 二种旋转方式

2 种「旋转」方式：

左旋
- 旧根节点为新根节点的左子树
- 新根节点的左子树（如果存在）为旧根节点的右子树
右旋：
- 旧根节点为新根节点的右子树
- 新根节点的右子树（如果存在）为旧根节点的左子树

4 种「旋转」纠正类型：

LL 型：插入左孩子的左子树，右旋
RR 型：插入右孩子的右子树，左旋
LR 型：插入左孩子的右子树，先左旋，再右旋
RL 型：插入右孩子的左子树，先右旋，再左旋

4.1 LL 型失衡「右旋」

第三个节点「1」插入的时候，BF(3) = 2，BF(2) = 1 LL 型失衡，右旋，根节点顺时针旋转

（1）最小不平衡子树「右旋」

右旋

旧根节点（节点 3）为新根节点（节点 2）的右子树
新根节点的 右子树（如果存在）为旧根节点的左子树

LL右旋转 (2)

4.2 RR 型失衡「左旋」

第三个节点「3」插入的时候，BF(1)=-2 BF(2)=-1，RR 型失衡，左旋，根节点逆时针旋转

（1）最小不平衡子树左旋

左旋

旧根节点（节点 1）为新根节点（节点 2）的左子树
新根节点的左子树（如果存在）为旧根节点的右子树

LL右旋转 (2)

4.3 LR 型

第三个节点「3」插入的时候，BF(3)=2 BF(1)=-1 LR 型失衡，先「左旋」再「右旋」

（1）最小不平衡子树左子树 {2,1} 先左旋

左旋

旧根节点（节点 1）为新根节点（节点 2）的左子树
新根节点的左子树（如果存在）为旧根节点的右子树

LR_L

（2）最小不平衡子树 {3,2,1} 再右旋

右旋

旧根节点（节点 3）为新根节点（节点 2）的右子树
新根节点的 右子树（如果存在）为旧根节点的左子树

4.4 RL 型

第三个节点「1」插入的时候，BF(1)=-2 BF(3)=1 RL 型失衡，先「右旋」再「左旋」

（1）最小不平衡子树根节点右子树{3,2}先右旋

右旋

旧根节点（节点 3）为新根节点（节点 2）的右子树
新根节点的 右子树（如果存在）为旧根节点的左子树

（2）最小不平衡子树 {1,2,3} 再左旋（L）

左旋

旧根节点（节点 1）为新根节点（节点 2）的左子树
新根节点的左子树（如果存在）为旧根节点的右子树

5. 实例

接下来我们以 {3,2,1,4,5,6,7,10,9,8} 为实例练习刚刚的 4 种插入方式

（1）依次插入 3、2、1 插入第三个点 1 的时候 BF(3)=2 BF(2)=1，LL 型失衡。

对最小不平衡树 {3,2,1}进行「右旋」

右旋：

旧根节点（节点 3）为新根节点（节点 2）的右子树
新根节点（节点 2）的右子树（这里没有右子树）为旧根节点的左子树

（2）依次插入 4 ，5 插入 5 点的时候 BF(3) = -2 BF(4)=-1，RR 型失衡

对最小不平衡树 {3,4,5} 进行「左旋」

左旋：

旧根节点（节点 3）为新根节点（节点 4）的左子树
新根节点（节点 4）的左子树（这里没有左子树）为旧根节点的右子树

（3）插入 4 ，5 插入 5 点的时候 BF(2)=-2 BF(4)=-1 ，RR 型失衡 对最小不平衡树进行「左旋」

左旋：

旧根节点（节点 2）为新根节点（节点 4）的左子树
新根节点（节点 4）的 左子树（节点 3）为旧根节点的右子树

新根节点（节点 4）的左子树（节点 3）为旧根节点的右子树

（4）插入 7 节点的时候 BF(5)=-2, BF(6)=-1 ，RR 型失衡，对最小不平衡树进行「左旋」

左旋：

旧根节点（节点 5）为新根节点（节点 6）的左子树
新根节点的左子树（这里没有）为旧根节点的右子树

（5）依次插入 10 ，9 。插入 9 点的时候 BF(10) = 1，BF(7) = -2 ，RL 型失衡，对先「右旋」再「左旋」

右子树先「右旋」

最小不平衡子树的右子树 {10,9} 先右旋：

旧根节点（节点 10）为新根节点（节点 9）的右子树
新根节点（节点 9）的右子树（这里没有右子树）为旧根节点的左子树

最小不平衡子树再左旋：

旧根节点（节点 7）为新根节点（节点 9）的左子树
新根节点（节点 9）的左子树（这里没有左子树）为旧根节点的右子树

（6）最后插入节点 8 ，BF(6)=-2 BF(9)=1，RL 型失衡，先「右旋」再「左旋」

最小不平衡子树的右子树 {9,7,10,8} 先「右旋」

右旋：

旧根节点（节点 9 {9,10}）为新根节点（节点 7）的右子树
新根节点（节点 7）的右子树（这里是 节点 8）为旧根节点（节点 9）的左子树

最小不平衡子树 {6,5,7,9,8,10} 再「左旋」

左旋：

旧根节点（节点 6 {6,5} ）为新根节点（节点 7）的左子树
新根节点的左子树（这里没有）为旧根节点的右子树

左旋结束

程序结束

6.代码实现

6.1 定义节点

public class AVLNode {
    /** 数据 **/
    public int data;
    /** 相对高度 **/
    public int height;
    /** 父节点 **/
    public AVLNode parent;
    /** 左子树 **/
    public AVLNode left;
    /** 右子树 **/
    public AVLNode right;
    public AVLNode(int data) {
        this.data = data;
        this.height = 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

6.2 计算高度

节点高度等于左子树和右子树最大高度 + 1

/** 通过子树高度 计算高度 **/
private int calcHeight(AVLNode root) {
    if (root.left == null && root.right == null) {
        return 1;
    }
    else if (root.right == null) {
        return root.left.height + 1;
    } else if (root.left == null) {
        return root.right.height + 1;
    }else {
        return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

6.3 计算 BF

BF（平衡因子）的值为：左子树高度 - 右子树高度

private int calcBF(AVLNode root) {
    if (root == null){
        return 0;
    }
    else if (root.left == null && root.right == null) {
        return 0;
    }
    else if (root.right == null) {
        return root.left.height ;
    } else if (root.left == null) {
        return - root.right.height;
    }else {
        return root.left.height - root.right.height;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

6.4 旋转

2 种「旋转」方式：

左旋
- 旧根节点为新根节点的左子树
- 新根节点的左子树（如果存在）为旧根节点的右子树
右旋：
- 旧根节点为新根节点的右子树
- 新根节点的右子树（如果存在）为旧根节点的左子树

重点理解：旋转之后通过需要刷新高度

高度变化只有： oldRoot 和 newRoot

但是它们子树的高度是不变的（这很关键）

我们可以通过它们 子树的高度计算他们的高度

使用不变的因数计算变化的因素是一个很好的思维

public AVLNode leftRotate(AVLNode root) {
    AVLNode oldRoot = root;
    AVLNode newRoot = root.right;
    AVLNode parent = root.parent;
    //1.newRoot 替换 oldRoot 位置
    if (null != parent ) {
        if (oldRoot.parent.data > oldRoot.data) {
            parent.left = newRoot;
        }else  {
            parent.right = newRoot;
        }
    }
    newRoot.parent = parent;
    //2.重新组装 oldRoot (将 newRoot 的左子树 给 oldRoot 的右子树)
    oldRoot.right = newRoot.left;
    if (newRoot.left != null) {
        newRoot.left.parent = oldRoot;
    }
    //3. oldRoot 为 newRoot 的左子树
    newRoot.left = oldRoot;
    oldRoot.parent = newRoot;
    //刷新高度
    oldRoot.height = calcHeight(oldRoot);
    newRoot.height = calcHeight(newRoot);
    return newRoot;
}


public AVLNode rightRotate(AVLNode root) {
    AVLNode oldRoot = root;
    AVLNode newRoot = root.left;
    AVLNode parent = root.parent;
    //1.newRoot 替换 oldRoot 位置
    if (null != parent ) {
        if (oldRoot.parent.data > oldRoot.data) {
            parent.left = newRoot;
        }else {
            parent.right = newRoot;
        }
    }
    newRoot.parent = parent;
    //2.重新组装 oldRoot (将 newRoot 的右子树 给 oldRoot 的左子树)
    oldRoot.left = newRoot.right;
    if (newRoot.right != null) {
        newRoot.right.parent = oldRoot;
    }
    //3. oldRoot 为 newRoot 的左子树
    newRoot.right = oldRoot;
    oldRoot.parent = newRoot;
    //刷新高度
    oldRoot.height = calcHeight(oldRoot);
    newRoot.height = calcHeight(newRoot);
    return newRoot;
}
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

6.5 插入（总代码）

插入操作

递归插入新节点
刷新高度
旋转并再次刷新高度

public class ALVTree {
    AVLNode root;
    public void insert(int data) {
        if (null == this.root) {
            this.root = new AVLNode(data);
            return;
        }
        this.root = insert(this.root, data);
    }
    public AVLNode insert(AVLNode root, int data) {
        //插入左子树
        if (data < root.data) {
            if (null == root.left) {
                root.left = new AVLNode(data);
                root.left.parent = root;
            }else {
                insert(root.left,data);
            }
        }
        //插入右子树
        else if (data > root.data) {
            if (null == root.right) {
                root.right = new AVLNode(data);
                root.right.parent = root;
            } else {
                insert(root.right,data);
            }
        }
        //刷新高度
        root.height = calcHeight(root);
        //旋转
        //1. LL 型 右旋转
        if (calcBF(root) == 2){
            //2. LR 型 先左旋转
            if (calcBF(root.left) == -1) {
                root.left = leftRotate(root.left);
            }
            root = rightRotate(root);
        }
        //3. RR型 左旋转
        if (calcBF(root) == -2){
            //4. RL 型 先右旋转
            if (calcBF(root.right)== 1) {
                root.right = rightRotate(root.right);
            }
            root = leftRotate(root);
        }

        return root;
    }
    public AVLNode leftRotate(AVLNode root) {
        AVLNode oldRoot = root;
        AVLNode newRoot = root.right;
        AVLNode parent = root.parent;
        //1.newRoot 替换 oldRoot 位置
        if (null != parent ) {
            if (oldRoot.parent.data > oldRoot.data) {
                parent.left = newRoot;
            }else  {
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2.重新组装 oldRoot (将 newRoot 的左子树 给 oldRoot 的右子树)
        oldRoot.right = newRoot.left;
        if (newRoot.left != null) {
            newRoot.left.parent = oldRoot;
        }
        //3. oldRoot 为 newRoot 的左子树
        newRoot.left = oldRoot;
        oldRoot.parent = newRoot;
        //刷新高度
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }


    public AVLNode rightRotate(AVLNode root) {
        AVLNode oldRoot = root;
        AVLNode newRoot = root.left;
        AVLNode parent = root.parent;
        //1.newRoot 替换 oldRoot 位置
        if (null != parent ) {
            if (oldRoot.parent.data > oldRoot.data) {
                parent.left = newRoot;
            }else {
                parent.right = newRoot;
            }
        }
        newRoot.parent = parent;
        //2.重新组装 oldRoot (将 newRoot 的右子树 给 oldRoot 的左子树)
        oldRoot.left = newRoot.right;
        if (newRoot.right != null) {
            newRoot.right.parent = oldRoot;
        }
        //3. oldRoot 为 newRoot 的左子树
        newRoot.right = oldRoot;
        oldRoot.parent = newRoot;
        //刷新高度
        oldRoot.height = calcHeight(oldRoot);
        newRoot.height = calcHeight(newRoot);
        return newRoot;
    }
    /** 通过子树高度 计算高度 **/
    private int calcHeight(AVLNode root) {
        if (root.left == null && root.right == null) {
            return 1;
        }
        else if (root.right == null) {
            return root.left.height + 1;
        } else if (root.left == null) {
            return root.right.height + 1;
        }else {
            return root.left.height > root.right.height ? root.left.height + 1 : root.right.height + 1;
        }
    }
    private int calcBF(AVLNode root) {
        if (root == null){
            return 0;
        }
        else if (root.left == null && root.right == null) {
            return 0;
        }
        else if (root.right == null) {
            return root.left.height ;
        } else if (root.left == null) {
            return - root.right.height;
        }else {
            return root.left.height - root.right.height;
        }
    }
}
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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

测试

public static void main(String[] args) {
    ALVTree tree = new ALVTree();
    tree.insert(3);
    tree.insert(2);
    tree.insert(1);
    tree.insert(4);
    tree.insert(5);
    tree.insert(6);
    tree.insert(7);
    tree.insert(10);
    tree.insert(9);
    tree.insert(8);
    //遍历输出
    innerTraverse(tree.root);
}
private static void innerTraverse(AVLNode root) {
    if (root == null) {
        return;
    }
    innerTraverse(root.left);
    System.out.println(root.data + " height:"+root.height);
    innerTraverse(root.right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

输出

1 height:1
2 height:2
3 height:1
4 height:4
5 height:1
6 height:2
7 height:3
8 height:1
9 height:2
10 height:1
1
2
3
4
5
6
7
8
9
10

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/羊村懒王/article/detail/511600

平衡二叉树详解 通俗易懂