目录

AVL树(平衡二叉搜索树)

基本介绍

为什么需要平衡二叉树

首先,二叉平衡树是一种特殊的二叉查找树(也叫二叉排序树和二叉搜索树)。我们知道二叉查找树进行查找操作的时间复杂度为$O(h)$其中$h$为二叉树的高度,而对二叉树进行的添加节点和删除节点操作都类似于查找操作,他们的时间复杂度都为$O(h)$。

其次,对于一棵二叉树来说,如果节点为$n$,树高为$h$,那么有$log_2(n+1) <= h <= n$,满树的时候$h = log_2(n+1)$(当然,完全二叉树,或者还有一些不是完全二叉树的二叉树也可能满足这个条件),当二叉树退化成一个单链表时,$h = n$。简单来说就是树高$h$最大为$n$最小为$log_2(n+1)$。二叉查找树各种操作的时间复杂度都和树高有关,所以为了提高时间效率,我们希望构造的这棵二叉排序树的树高越小越好,这就引出了平衡二叉树。

平衡二叉树的定义

AVL树是是一种平衡二叉搜索树,此外还有红黑树等,一般讲平衡二叉搜索树就是AVL树。它要么是颗空树,要么左子树和右子树的深度之差绝对值不超过1 且左子树和右子树也是平衡二叉树。 平衡因子(Balance Factor):当前节点的左子树深度减去右子树的深度。根据平衡因子的定义可以推导出平衡二叉树上所有节点的平衡因子只可能为-1,0,1。只要二叉树上有一个节点的平衡因子的绝对值大于1,那么这颗平衡二叉树就失去了平衡。

最小非平衡子树

概念

一颗二叉排序树是否平衡就看它的平衡因子绝对值是否大于1,如果是那么这颗二叉排序树不平衡,,最小非平衡子树就是沿着刚插入的节点向上(向root)查找,最先找到的非平衡子树就是最小非平衡子树。 最小非平衡分成四种类型:LL,LR,RL, RR

如何判断类型

https://gitee.com/lienhui68/picStore/raw/master/null/WX20200629-151129@2x.png 第一个字母(L或R)描述的是unbalance(也就是根节点)的左右子树哪个更高,而第二个字母(L或R)描述的是unbalance的孩子(如果第一个是L则为左孩子,反之为右孩子)的左右子树哪个更高。 这样定义的好处: 根据最小非平衡子树的根节点判断类型适用于增加节点和删除节点,这样增加节点和删除节点之后平衡二叉树的调整工作可以统一处理。

另外删除节点有一种特殊情况需要考虑: 对于添加节点并不存在最小非平衡子树左右子树等高的情况,如下图:

因为刚刚插入的节点只能是7或者10,无论是哪个在插入之前这个树已经是不平衡的了,所以不存在最小非平衡二叉树左右子树等高的情况。但是这种情况在删除节点的时候可能会出现,如下图:

树本来是平衡的,但是删除14之后12就不平衡了,但这时8的左右子树高度相等。那么12这棵树也是最小非平衡二叉树,我们规定这种情况为LL型(LR也可以)。

总结一下最小非平衡二叉树的分类: LL型: 第一个L表示:unbalance的左子树比右子树高。第二个L表示unbalance的左孩子的左子树比右子树高,或者unbalance的左孩子的左右子树等高。

LR型: L表示:unbalance的左子树比右子树高。R表示unbalance的左孩子的右子树比左子树高。

RL型: R表示:unbalance的右子树比左子树高。L表示unbalance的右孩子的左子树比右子树高。

RR型: 第一个R表示:unbalance的右子树比左子树高。第二个R表示unbalance的右孩子的右子树比左子树高,或者unbalance的右孩子的左右子树等高。

最小非平衡子树如何调整

首先,我们要关注的是那3个带圈圈的节点! 第二,平衡的目的是降低左右子树的高度,但是要注意调整后的二叉树依然是排序的。也就是得保证平衡+排序。 第三,3个节点调整后的样式为:

根据二叉排序树的性质,这3个节点中左子节点最小,根居中,右子最大。

调整步骤

  1. 判断是哪种类型(LL、LR、RL、RR)

  2. 根据各类型分别处理 2.1. LL型

    https://gitee.com/lienhui68/picStore/raw/master/null/WX20200629-161028@2x.png

    说明:我们将删除节点后左右子树等高的情况考虑进去,也就是图中可能会出现绿色节点,添加节点时只会有白色节点

    2.1.1. 确定big、middle和small

    1
    2
    3
    
        big = unbalance;
        middle = unbalance.left;
        small = unbalance.left.left;
    

    2.1.2. middle的左右子树分配给big和small 对于LL型,middle的左子不用分配,调整前后middle的左子都是small,对于middle的右子要分配给big的左子,这样才能保证二叉排序

    1
    
       big.left = middle.right; // 因为middle.right肯定比middle大,比big小,所以讲middle.right挂到big的左节点上
    

    2.1.3. 将small和big分别作为middle的左右子树 对于LL型,调整前small已经是middle的左子了,small不用调整

    1
    
       middle.right=big;
    

    2.1.4. 将middle作为调整后的最小非平衡子树根节点,也就是将middle作为parent的孩子,这里要分3种情况 a. parent为空,那么middle作为整颗树的根节点,也就是root=middle b. parent不为空&&unbalance作为parent的左子,parent.left=middle c. parent不为空&&unbalance作为parent的右子,parent.right=middle

    2.2. LR型 https://gitee.com/lienhui68/picStore/raw/master/null/WX20200629-163709@2x.png

    2.2.1 确定big、middle和small

    1
    2
    3
    
        big = unbalance;
        small = unbalance.left;
        middle = unbalance.left.left;
    

    2.2.2 middle的左右子树分配给big和small 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子

    1
    2
    
        small.right = middle.left;
        big.left = middle.right;
    

    2.2.3. 将small和big分别作为middle的左右子树

    1
    2
    
        middle.left = small;
        middle.right = big;
    

    2.2.4. 将middle作为调整后的最小非平衡子树根节点,同步骤2.1.4 分3种情况处理

    2.3. RL型 https://gitee.com/lienhui68/picStore/raw/master/null/WX20200629-165108@2x.png

    2.3.1. 确定big、middle和small

    1
    2
    3
    
        big = unbalance.right;
        middle = unbalance.right.left;
        small = unbalance;
    

    2.3.2 middle的左右子树分配给big和small 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子

    1
    2
    
        small.right = middle.left;
        big.left = middle.right;
    

    2.3.3. 将small和big分别作为middle的左右子树

    1
    2
    
    middle.left = small;
    middle.right = big;
    

    2.3.4. 将middle作为调整后的最小非平衡子树根节点,同步骤2.1.4 分3种情况处理

    2.4. RR型 https://gitee.com/lienhui68/picStore/raw/master/null/WX20200629-165828@2x.png

    2.4.1. 确定big、middle和small

    1
    2
    3
    
        big = unbalance.right.right;
        middle = unbalance.right;
        small = unbalance;
    

    2.4.2. 将middle的左右子树分配给big和small 对于RR型middle的右子不用分配,调整前后middle的右子都是big。

    1
    
    small.right=middle.left;
    

    2.4.3 将small和big分别作为middle的左右子树 对于RR型来说调整前后big都是middle的右子,所以big不用调整。

    1
    
    middle.left=small;
    

    2.4.4 同上

调整部分代码实现

 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
/**
     * 最小非平衡子树调整
     *
     * @param unbalance
     * @param unbalanceType
     */
    private void adjust(Node unbalance, UNBALANCE_TYPE unbalanceType) {
        Node parent = getFather(unbalance.value);
        Node big, middle = null, small;
        switch (unbalanceType) {
            // 1. LL型最小非平衡子树
            case LL:
                // 1.1 确定big、middle和small
                big = unbalance;
                middle = unbalance.left;
                // 1.2 将middle的左右子树分配给big和small
                // 对于LL型,middle的左子不用分配,调整前后middle的左子都是small,对于middle的右子要分配给big的左子,这样才能保证二叉排序
                big.left = middle.right;
                // 1.3 将small和big分别作为middle的左右子节点
                middle.right = big;
                break;
            case LR:
                // 2.1 确定big、middle和small
                big = unbalance;
                middle = unbalance.left.right;
                small = unbalance.left;
                // 2.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RL:
                // 3.1 确定big、middle和small
                big = unbalance.right;
                middle = unbalance.right.left;
                small = unbalance;
                // 3.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RR:
                // 3.1 确定big、middle和small
                big = unbalance.right.right;
                middle = unbalance.right;
                small = unbalance;
                // 3.2 将middle的左右子树分配给big和small
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                middle.left = small;
                break;

        }

        // 将middle作为调整后的最小非平衡子树根节点,也就是将middle作为parent的孩子,这里要分3种情况
        // parent为null表示根节点也被调整,此时应将root指向middle
        if (parent == null) {
            root = middle;
            return;
        } else if (parent.left != null && parent.left.value == unbalance.value) {
            parent.left = middle;
        } else if (parent.right != null && parent.right.value == unbalance.value) {
            parent.right = middle;
        } else {
            throw new RuntimeException();
        }
    }

添加节点和删除

  1. 添加节点 按照二叉排序规则添加节点(参考二叉排序树增加节点),每添加一个节点都需要判断是否平衡,如果不平衡要找出最小非平衡子树,并对最小非平衡子树进行调整。

  2. 删除节点 2.1 删除节点,保证依然是一颗二叉排序树(参考二叉排序树删除节点) 2.2 平衡调整,保证是一颗平衡二叉树。

完整代码

  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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
package com.eh.ftd.dsa.ds;

/**
 * 平衡二叉树
 *
 * @author David Li
 * @create 2020/06/29 18:03
 */
public class BalancedBinaryTree {

    private Node root; // 根节点

    private class Node {
        int value; // 值
        Node left; // 左子节点
        Node right; // 右子节点

        public Node(int value) {
            this.value = value;
        }

        @Override
        public String toString() {
            return value + "";
        }
    }

    /**
     * 最小非平衡子树类型
     */
    private enum UNBALANCE_TYPE {
        LL, LR, RL, RR
    }

    /**
     * 节点的哪课子树高
     */
    private enum HIGHER {
        L, R, EQ
    }

    /**
     * 获得节点的父节点
     *
     * @param value
     * @return
     */
    private Node getFather(int value) {
        if (root == null) {
            return null;
        }
        Node cur = root, parent = null;
        while (cur != null) {
            if (value < cur.value) {
                parent = cur;
                cur = cur.left;
            } else if (value > cur.value) {
                parent = cur;
                cur = cur.right;
            } else {
                return parent;
            }
        }
        return null;
    }

    /**
     * 判断哪边子树高
     *
     * @param node
     * @return
     */
    private HIGHER getHigher(Node node) {
        if (node == null) {
            throw new RuntimeException();
        }
        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);
        if (leftDepth == rightDepth) {
            return HIGHER.EQ;
        } else if (leftDepth > rightDepth) {
            return HIGHER.L;
        } else {
            return HIGHER.R;
        }
    }

    /**
     * 获取节点的高度
     *
     * @param node
     * @return
     */
    private int getDepth(Node node) {
        if (node == null) {
            return 0;
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        return Math.max(getDepth(node.left), getDepth(node.right)) + 1;
    }

    /**
     * 获取最小非平衡子树 unbalance 的树类型
     *
     * @param unbalance
     * @return
     */
    private UNBALANCE_TYPE getUnbalanceType(Node unbalance) {
        if (unbalance.left == null && unbalance.right == null) {
            throw new RuntimeException();
        }
        HIGHER childHigher = getHigher(unbalance);
        if (HIGHER.L == childHigher) {
            HIGHER grandChildHigher = getHigher(unbalance.left);
            if (HIGHER.R == grandChildHigher) {
                return UNBALANCE_TYPE.LR;
            } else {
                // 删除节点后可能会出现unbalance的左子节点的左右子树高度一样,这种情况也归类到LL型
                return UNBALANCE_TYPE.LL;
            }
        } else if (HIGHER.R == childHigher) {
            HIGHER grandChildHigher = getHigher(unbalance.right);
            if (HIGHER.L == grandChildHigher) {
                return UNBALANCE_TYPE.RL;
            } else {
                // 删除节点后可能会出现unbalance的右子节点的左右子树高度一样,这种情况也归类到RR型
                return UNBALANCE_TYPE.RR;
            }
        } else {
            // 比较unbalance哪边高不会出现一样高的情况
            throw new RuntimeException();
        }
    }

    /**
     * 最小非平衡子树调整
     *
     * @param unbalance
     * @param unbalanceType
     */
    private void adjust(Node unbalance, UNBALANCE_TYPE unbalanceType) {
        Node parent = getFather(unbalance.value);
        Node big, middle = null, small;
        switch (unbalanceType) {
            // 1. LL型最小非平衡子树
            case LL:
                // 1.1 确定big、middle和small
                big = unbalance;
                middle = unbalance.left;
                // 1.2 将middle的左右子树分配给big和small
                // 对于LL型,middle的左子不用分配,调整前后middle的左子都是small,对于middle的右子要分配给big的左子,这样才能保证二叉排序
                big.left = middle.right;
                // 1.3 将small和big分别作为middle的左右子节点
                middle.right = big;
                break;
            case LR:
                // 2.1 确定big、middle和small
                big = unbalance;
                middle = unbalance.left.right;
                small = unbalance.left;
                // 2.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RL:
                // 3.1 确定big、middle和small
                big = unbalance.right;
                middle = unbalance.right.left;
                small = unbalance;
                // 3.2 将middle的左右子树分配给big和small
                // 分配原则是将middle的左子分配给small的右子,将middle的右子分配给big的左子
                big.left = middle.right;
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                middle.left = small;
                middle.right = big;
                break;
            case RR:
                // 3.1 确定big、middle和small
                big = unbalance.right.right;
                middle = unbalance.right;
                small = unbalance;
                // 3.2 将middle的左右子树分配给big和small
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                small.right = middle.left;
                // 2.3 将small和big分别作为middle的左右子树
                // 对于RR型middle的右子不用分配,调整前后middle的右子都是big。
                middle.left = small;
                break;

        }

        // 将middle作为调整后的最小非平衡子树根节点,也就是将middle作为parent的孩子,这里要分3种情况
        // parent为null表示根节点也被调整,此时应将root指向middle
        if (parent == null) {
            root = middle;
            return;
        } else if (parent.left != null && parent.left.value == unbalance.value) {
            parent.left = middle;
        } else if (parent.right != null && parent.right.value == unbalance.value) {
            parent.right = middle;
        } else {
            throw new RuntimeException();
        }
    }

    /**
     * 处理平衡性问题
     *
     * @param root
     * @param value 添加或删除的值
     */
    private void dealBalance(Node root, int value) {
        if (root == null) {
            return;
        }
        Node cur = root, unbalance = null;
        while (cur != null && cur.value != value) { //cur.value != value 在添加节点的时候可以少些判断,删除节点会一直循环到cur为空
            if (!isBalanced(cur)) {
                unbalance = cur;
                // 继续遍历, 因为是找最小非平衡子树
            }
            if (value < cur.value) {
                cur = cur.left;
            } else if (value > cur.value) {
                cur = cur.right;
            }
        }
        if (unbalance == null) {
            // 说明没有平衡性问题
            return;
        }
        // 调整最小非平衡子树
        adjust(unbalance, getUnbalanceType(unbalance));
    }

    /**
     * 判断当前节点左右高度是否相等
     *
     * @param node
     * @return
     */
    private boolean isBalanced(Node node) {
        int leftDepth = getDepth(node.left);
        int rightDepth = getDepth(node.right);
        if (Math.abs(leftDepth - rightDepth) > 1) {
            return false;
        }
        return true;
    }

    public void inOrderList(Node node) {
        if (node != null) {
            inOrderList(node.left);
            System.out.print(node + " ");
            inOrderList(node.right);
        }
    }

    /**
     * 添加节点
     *
     * @param value
     */
    public void add(int value) {
        // 和二叉排序树一样, 区别是最后需要处理平衡性问题平衡性
        Node node = new Node(value);
        if (root == null) {
            root = node;
            return;
        }
        Node cur = root;
        while (true) {
            // 如果值比当前节点小
            if (value < cur.value) {
                // 如果当前节点左节点为空,将左节点指向新节点
                if (cur.left == null) {
                    cur.left = node;
                    break;
                } else { // 继续跟当前节点的左节点比较
                    cur = cur.left;
                }
            }
            if (value > cur.value) {
                if (cur.right == null) {
                    cur.right = node;
                    break;
                } else {
                    cur = cur.right;
                }
            }
            if (value == cur.value) {
                // 如果和已有节点值相同,直接报冲突,不处理这种情况
                throw new RuntimeException("已有相同的值,请勿重复插入!");
            }
        }
        // 处理平衡性问题
        dealBalance(root, value);
    }

    /**
     * 删除节点
     *
     * @param value
     * @return
     */
    public boolean delete(int value) {
        if (root == null) {
            return false;
        }
        // 1. 找到目标节点(并且保存父节点的引用,用于删除)
        Node parent = null, cur = root;
        while (cur != null && value != cur.value) {
            parent = cur;
            if (value < cur.value) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        // 没找到直接返回
        if (cur == null) {
            return false;
        }
        // 父节点为空表示找到的节点就是根节点,也要分3种情况考虑
        if (parent == null) {
            // 1. 如果父节点是叶子节点
            if (cur.left == null && cur.right == null) {
                root = null;
            } else if (cur.left == null && cur.right != null) { // 2.1 如果只有1颗是右子树
                root = cur.right;
            } else if (cur.right == null && cur.left != null) { // 2.2 如果只有1颗是左子树
                root = cur.left;
            } else {
                // 3. 有两棵子树情况
                deleteLeftMaxNode(cur);
            }
            return true;

        }
        // 有父节点有子节点, 分三种情况处理
        // 1. cur是叶子节点
        if (cur.left == null && cur.right == null) {
            // 判断cur是父节点的左子节点还是右子节点
            if (cur.value == parent.left.value) {
                parent.left = null;
            } else {
                parent.right = null;
            }
            return true;
        }
        // 2. cur是只有一颗子树的节点
        // 2.1 只有右子树
        if (cur.left == null && cur.right != null) {
            // 2.1.1 是父节点的左子节点
            if (cur.value == parent.left.value) {
                parent.left = cur.right;
            } else {
                // 2.1.2 是父节点的右子节点
                parent.right = cur.right;
            }
            return true;
        }
        // 2.2 只有左子树
        if (cur.left != null && cur.right == null) {
            // 2.2.1 是父节点的右子节点
            if (cur.value == parent.right.value) {
                parent.right = cur.left;
            } else {
                // 2.2.2 是父节点的左子节点
                parent.left = cur.left;
            }
            return true;
        }
        // 3. 只剩下有两颗子树的情况
        // 找到要删除的值所在节点,记为cur, 找到cur左子树的最大值节点删除,cur置置为刚才删除的节点值;
        // 或者找到cur右子树的最小值节点删除,cur值置置为刚才删除的节点值,这里我们找左节点最大值节点
        deleteLeftMaxNode(cur);

        // 处理平衡性问题
        dealBalance(root, value);
        return true;
    }

    private int deleteLeftMaxNode(Node cur) {
        Node leftMaxNode = cur.left;
        try {
            while (leftMaxNode.right != null) {
                leftMaxNode = leftMaxNode.right;
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
        int leftMaxValue = leftMaxNode.value;
        // 删除该节点
        delete(leftMaxValue);
        // 将cur的值置为leftMaxValue
        cur.value = leftMaxValue;
        return leftMaxValue;
    }

    public static void main(String[] args) {
        BalancedBinaryTree balancedBinaryTree = new BalancedBinaryTree();
        for (int i = 0; i < 10000; i++) {
            balancedBinaryTree.add(i);
        }
        System.out.println("当前共有: " + balancedBinaryTree.getDepth(balancedBinaryTree.root) + " 层");
        for (int i = 20; i < 10000; i++) {
            balancedBinaryTree.delete(i);
        }
        System.out.println("当前共有: " + balancedBinaryTree.getDepth(balancedBinaryTree.root) + " 层");
        System.out.println("数列:");
        balancedBinaryTree.inOrderList(balancedBinaryTree.root);
        System.out.println();
//        binarySortTree.inOrderList(binarySortTree.root);
//        Node node = binarySortTree.search(15);
//        System.out.println(node);
//        node = binarySortTree.search(10);
//        System.out.println(node);
//        for (int i = 0; i < 14; i++) {
//            System.out.print("删除节点:" + i + ", ");
//            boolean res = balancedBinaryTree.delete(i);
//            if (!res) {
//                System.out.println("不存在该节点!");
//            } else {
//                System.out.print("成功删除,剩余节点: ");
//                balancedBinaryTree.inOrderList(balancedBinaryTree.root);
//                System.out.println();
//            }
//        }
    }

}

运行结果 https://gitee.com/lienhui68/picStore/raw/master/null/20200629211842.png

参考

二叉平衡树的创建 二叉平衡树之删除节点操作