Java高阶数据结构之AVL树

---

提示：以下是本篇文章正文内容，Java系列学习将会持续更新

数据结构动态模型：https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

一、AVL树的概念

 二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

 解决方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树具有以下性质：

• 它的左右子树都是AVL树
• 左右子树高度之差(简称平衡因子)的绝对值不超过1
• 平衡因子 = 右树高度 - 左树高度

回到目录…

二、插入

AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
2. 调整节点的平衡因子

回到目录…

三、旋转

 如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。

 参考视频：B站UP主 - 林语石 AVL树的平衡调整 ，小姐姐人美声甜，关键讲得非常好、通俗易懂！

平衡调整的准则：

1. 找距离插入节点最近的不平衡子树 (|平衡因子| > 1)
2. 以不平衡节点作为根进行旋转
3. 仅旋转不平衡节点到插入节点方向上的3个节点，其余节点插入到适当位置

4种不平衡情况 ——> 对应的调整方案：
4. LL型 ——> R
5. RR型 ——> L
6. LR型 ——> LR
7. RL型 ——> RL

3-1 LL型 (右单旋)

中为支，高右旋。

例如：

回到目录…

3-2 RR型 (左单旋)

中为支，高左旋。

例如：

回到目录…

3-3 LR型 (左右双旋)

下二整体先左旋，而后变成LL型，高点右旋变平衡。

情况一：

情况二：

回到目录…

3-4 RL型 (右左双旋)

下二整体先右旋，而后变成RR型，高点左旋变平衡。

情况一：

情况二：

回到目录…

四、删除

AVL树的删除过程可以分为：

1. 找到需要删除的节点
2. 按照搜索树的删除规则删除节点—— Hibbard Deletion
3. 更新平衡因子，如果出现了不平衡，进行旋转——单旋 / 双旋

回到目录…

五、性能分析

 AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度O(logN)。

 但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多。更差的是在删除时，有可能一直要让旋转持续到根的位置。

 因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树。但一个结构经常修改，就不太适合。

回到目录…

六、完整代码

public class AVLTree {
    private class TreeNode {
        int val;
        // 平衡因子 = 右子树高度 - 左子树的高度
        int bf;
        TreeNode left;
        TreeNode right;
        TreeNode parent;

        TreeNode(int val) {
            this.val = val;
        }
    }

    private TreeNode root;

    /**
     * 插入操作
     *   1. 先把数据插入二叉树中
     *   2. 根据平衡因子对树进行平衡调整
     * @return 无法插入重复元素
     */
    public boolean insert(int val) {
        TreeNode node = new TreeNode(val);
        if(root == null) {
            root = node;
            return true;
        }

        TreeNode parent = null;
        TreeNode cur = root;
        while(cur != null) {
            if(val == cur.val){
                return false;
            }else if(val < cur.val) {
                parent = cur;
                cur = parent.left;
            }else{
                parent = cur;
                cur = parent.right;
            }
        }
        // 此时cur=null，插入 val
        if(val < parent.val) {
            parent.left = node;
        }else {
            parent.right = node;
        }
        node.parent = parent;
        cur = node;

        /**
         * 自底向上调节平衡因子
         *   因为 bf = rightH - leftH, 所以当某个子树插入一个节点不引起左右子树高度变化时，就不需要继续向上调整平衡因子了
         *   也就是，当某个子树节点从 (-1 / 1) -> 0 的时候
         */
        while(parent != null) {
            // 一直向上调节
            if(cur == parent.left) {
                // cur 是 parent 的左孩子
                parent.bf --;
            }else {
                parent.bf ++;
            }

            if(parent.bf == 0) {
                // 已经平衡了
                break;
            }else if(parent.bf == -1 || parent.bf == 1) {
                // 继续向上
                cur = parent;
                parent = cur.parent;
            }else {
                // parent.bf = -2/2, 该子树不平衡了，应该旋转, 有以下4种情况：
                if(parent.bf == -2 && cur.bf == -1) {
                    // LL型，右单旋
                    rotateR(parent);
                }else if(parent.bf == 2 && cur.bf == 1) {
                    // RR型，左单旋
                    rotateL(parent);
                }else if(parent.bf == -2 && cur.bf == 1) {
                    // LR型，左右双旋
                    rotateLR(parent);
                }else {
                    // parent.bf == 2 && cur.bf == -1
                    // RL型，右左双旋
                    rotateRL(parent);
                }
                // 旋转完就一定平衡了
                break;
            }
        }
        return true;
    }
    // 左单旋
    private void rotateL(TreeNode p) {
        // p 的母节点
        TreeNode pp = p.parent;
        // p 的右孩子
        TreeNode subR = p.right;
        // subR 的左孩子，可能不存在
        TreeNode subRL = subR.left;

        // subR 提上去
        if(pp == null) {
            this.root = subR;
        }else if(pp.left == p) {
            pp.left = subR;
        }else {
            // pp.right == parent
            pp.right = subR;
        }
        subR.parent = pp;
        // p 作为 subR 的左孩子
        subR.left = p;
        p.parent = subR;
        // p 与 subRL 连接
        p.right = subRL;
        if(subRL != null) {
            subRL.parent = p;
        }

        // 经过旋转最终只会改变 parent 和 subR 的平衡因子
        // 而且无论 subRL 是否存在，最终都是 0
        subR.bf = 0;
        p.bf = 0;
    }
    // 右单旋
    private void rotateR(TreeNode p) {
        // p 的父节点
        TreeNode pp = p.parent;
        // p 的左孩子
        TreeNode subL = p.left;
        // subL 的右孩子，可能不存在
        TreeNode subLR = subL.right;

        if(pp == null) {
            this.root = subL;
        }else if(pp.left == p) {
            pp.left = subL;
        }else {
            pp.right = subL;
        }
        subL.parent = pp;
        subL.right = p;
        p.parent = subL;
        p.left = subLR;
        if(subLR != null) {
            subLR.parent = p;
        }
        // 经过旋转最终只会改变 parent 和 subL 的平衡因子
        // 而且无论 subLR 是否存在，最终都是 0
        subL.bf = 0;
        p.bf = 0;
    }
    // 左右双旋
    private void rotateLR(TreeNode p) {
        TreeNode subL = p.left;
        TreeNode subLR = subL.right;
        int bf = subLR.bf; // 可能为 0、1、-1

        rotateL(subL);
        rotateR(p);

        subLR.bf = 0;
        if(bf == 1) {
            p.bf = 0;
            subL.bf = -1;
        }else if(bf == -1) {
            subL.bf = 0;
            p.bf = 1;
        }
        // 当 bf == 0 时，就不需要再手动改平衡因子了
    }
    // 右左双旋
    private void rotateRL(TreeNode p) {
        TreeNode subR = p.right;
        TreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateR(subR);
        rotateL(p);

        subRL.bf = 0;
        if(bf == -1) {
            p.bf = 0;
            subR.bf = 1;
        }else if(bf == 1) {
            subR.bf = 0;
            p.bf = -1;
        }
    }

    /**
     * 查找操作
     */
    public boolean contains(int val) {
        return contains(root, val);
    }
    // 在当前树中查找元素
    private boolean contains(TreeNode root, int val) {
        if(root == null) {
            return false;
        }
        if(val == root.val) {
            return true;
        }else if(val < root.val) {
            return contains(root.left, val);
        }else {
            return contains(root.right, val);
        }
    }

    /**
     * 删除操作
     * Hibbard Deletion: 拿前驱 / 后继 来代替
     */
    public boolean delete(int val) {
        if(root == null) {
            return false;
        }
        // ......
        return true;
    }

    /** 打印二叉树, 中序遍历的结果 **/
    @Override
    public String toString() {
        List<Integer> list = new ArrayList<>();
        inOrder(list, root);
        return list.toString() + "\n" + "是否平衡: " + isBalance(this.root);
    }
    // 中序遍历
    private void inOrder(List<Integer> list, TreeNode root) {
        if(root == null){
            return;
        }
        inOrder(list, root.left);
        list.add(root.val);
        inOrder(list, root.right);
    }

    /**
     * 检验二叉树是否平衡
     *   每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
     *   节点的平衡因子是否计算正确
     */
    private boolean isBalance(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftH = height(root.left);
        int rightH = height(root.right);
        if(rightH - leftH != root.bf) {
            System.err.println("平衡因子异常！");
            return false;
        }
        return Math.abs(root.bf) < 2 && isBalance(root.left) && isBalance(root.right);
    }
    // 计算二叉树的高度
    private int height(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return 1 + Math.max(height(root.left), height(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
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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267

回到目录…

---

总结:
提示：这里对文章进行总结：
以上就是今天的学习内容，本文是Java高阶数据结构的学习，如何自己实现一棵AVL树，以及插入节点后的平衡调整：左单旋、右单旋、左右双旋、右左双旋。之后的学习内容将持续更新！！！