数据结构 - 图文解析AVL树_对3,6,5,1,2,4,从一颗空树开始,通过连续插入它的元素来构造一棵avl树

什么是平衡二叉树

平衡树(Balance Tree，BT) 指的是，任意节点的子树的高度差都小于等于1

第二个树根节点左子树高度为3，右子树高度1，高度差为2，不平衡

二叉平衡搜索树（AVL树）：自平衡的二叉排序树

上面的树，先变成二叉排序树

现在插入数据3，结点6左子树与右子树高度差大于2，不平衡，如果是AVL树会自动平衡（右旋）

---

为什么需要平衡

二叉排序树：任意结点，左节点不大于当前结点，右结点不小于当前结点的树

当数列为[1,2,3,4,5,6]等极端情况，二叉排序树就退化成了链表

其操作的时间复杂度将退化成线性的，即O(n)，这不符合我们的需求

---

如何自平衡

平衡因子

平衡因子(bf)：结点的左子树的深度减去右子树的深度

对应这些结点的平衡因子：

当存在平衡因子大于等于2，该树不平衡

四种不平衡情况

不平衡有四种情况：

1. 插入左子树的左子树

插入结点1后，结点8,13的平衡因子都为2

2. 插入左子树的右子树

3. 插入右子树的左子树

4. 插入右子树的右子树

上面四种情况本质上是两种情况，[1,4]，[2,3]是对称的，但代码需要考虑到

自旋

既然AVL树是自平衡的二叉排序树，如何实现自平衡？
自旋平衡因子=>2或<=-2的结点

步骤：

1. 插入接点90后，树不平衡，计算平衡因子
2. 从插入结点90开始回溯，找到第一个失衡结点（66） - 如果回溯到根节点都没有失衡结点，该树是平衡树
3. 平衡因子为-2，说明左子树比右子树高度小2，左旋该树
4. 相应修改结点13、60、80间的线

选择哪个结点自旋？ 从插入结点往上回溯，第一个失衡结点就是要旋转的结点

单旋转与双旋转

1. 单旋转

如插入右子树的右子树这种情况（插入结点90），旋转一次就可以平衡，称为左旋

对应的左子树的左子树，旋转一次，称为右旋

2. 双旋转

当不平衡状况出现2,3 - 左子树的右子树、右子树的左子树，单次旋转无法平衡

插入根结点为14的树的右子树的左子树（插入结点18），先右旋子树20，再左旋树14

相应的：根结点为14的树，插入左子树的右子树，先左旋子树9再右旋树14

---

删除结点

前面是插入结点后AVL树通过旋转自平衡，当删除结点时，也会引发不平衡

删除结点有3种情况：

1. 删除叶子结点

删除结点8后，结点13的平衡因子为-2，不平衡

2. 删除有一棵子树的结点

3. 删除有左右子树的结点

这里设置的是删除有左右子树的结点，选择右子树中最小值顶替

构成AVL树后AVL已经是平衡树，删除结点导致树不平衡，我们只需要往父结点找失衡结点，找到后按照上面的旋转方法平衡即可

（删除双子树结点，应当从删除结点的位置开始找失衡结点）

---

Java实现

只需在二叉排序树的基础上完成左旋、右旋（双旋转都是实现两次左旋、右旋）
二叉排序树的内容，下面的代码基于我的二叉排序树

1. 左旋

    /**
     * 左旋
     */
    private void leftRotate(){
        //创建一个新结点，为当前结点的值
        Node newNode = new Node(value);
        //把新的结点的左/右子树设置为当前结点的左子树
        newNode.left = left;
        newNode.right = right.left;
        //把当前结点的值替换成右子树的值
        value = right.value;
        //把当前结点的右子树设置为当前结点的右子树的右子树
        right = right.right;
        //把当前结点的左子树设置为新结点的
        left = newNode;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2. 右旋
   右旋就是左旋反过来
   

	/**
     * 右旋
     */
    private void rightRotate(){
        //创建一个新结点,值为当前结点的值
        Node newNode = new Node(value);

        //新结点的左/右子树
        newNode.right = right;
        newNode.left = left.right;

        //当前结点改为左子结点
        value = left.value;
        left = left.left;

        right = newNode;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

3. 完整代码

package com.company.tree.AVL;

/**
 * Author : zfk
 * Data : 10:49
 */
public class AVLTreeDemo {

    public static void main(String[] args) {
        int[] arr = {13,8,66,6,9,20,80,5,90};

        //创建AVLTree
        AVLTree avlTree = new AVLTree();

        //添加结点
        for (int i: arr){
            avlTree.add(new Node(i));
        }

        //中序遍历
        System.out.println("=== 中序遍历 ===");
        avlTree.infixOrder();
        System.out.println();
        System.out.println("=== 平衡处理 ===");
        System.out.println("树的高度："+ avlTree.getRoot().height());
        System.out.println("树的左子树的高度："+ avlTree.getRoot().leftHeight());
        System.out.println("树的右子树的高度："+ avlTree.getRoot().rightHeight());
        System.out.println("根节点为 ： "+ avlTree.getRoot());

        System.out.println("=== 删除结点 ===");
        avlTree.delNodeBalance(8);

        avlTree.infixOrder();
        System.out.println();
        System.out.println("=== 平衡处理 ===");
        System.out.println("树的高度："+ avlTree.getRoot().height());
        System.out.println("树的左子树的高度："+ avlTree.getRoot().leftHeight());
        System.out.println("树的右子树的高度："+ avlTree.getRoot().rightHeight());
        System.out.println("根节点为 ： "+ avlTree.getRoot());
        System.out.println("根节点左结点为 ： "+ avlTree.getRoot().left.value);

    }

}



//AVL树
class AVLTree{

    //根结点
    private Node root;

    public Node getRoot() {
        return root;
    }

    //添加结点的方法
    public void add(Node node){
        if (root == null){
            //空树,直接加入
            root = node;
        }
        else {
            //add方法递归加入
            root.add(node);
        }
    }
    //中序遍历
    public void infixOrder(){
        if (root != null){
            root.infixOrder();
        }
        else {
            System.out.println("=== 二叉排序树为空 ===");
        }
    }

    //从根节点查找要删除的结点
    public Node search(int value){
        if (root == null){
            return null;
        }
        else{
            return root.search(value);
        }
    }

    //从根节点查找父结点
    public Node searchParent(int value){
        if (root == null){
            return null;
        }
        else {
            return root.searchParent(value);
        }
    }

    /**
     * 删除右子树的最小结点并返回
     * @param node 传入的结点，当做一个二叉排序树的根节点
     * @return 返回以node为根结点的二叉排序树的最小结点
     */
    public Node delRightTreeMin(Node node){
        Node temp = node;
        //循环查找左子结点，找到最小值
        while (temp.left != null){
            temp = temp.left;
        }
        //temp指向最小结点,删除并返回
        delNode(temp.value);
        return temp;
    }

    /**
     * 删除结点：如果要删除的结点有一棵子树
     * @param parent 要删除结点的父结点
     * @param targetNode 要删除的结点
     * @param value 要删除的结点的值
     */
    public void delNodeOneTree(Node parent,Node targetNode,int value){
        //如果要删除的结点只有左子树
        if (targetNode.left != null){
            if (parent != null) {
                //如果targetNode是parent的左子结点
                if (parent.left.value == value) {
                    parent.left = targetNode.left;
                } else {
                    //targetNode是parent的右子结点
                    parent.right = targetNode.left;
                }
            }else {
                //如果要删除的结点是根节点
                root = targetNode.left;
            }
        }
        //要删除的结点只有右子树
        else {
            if (parent != null) {
                if (parent.left.value == value) {
                    parent.left = targetNode.right;
                } else {
                    //targetNode是parent右子结点
                    parent.right = targetNode.right;
                }
            }
            else {
                //删除的是根节点
                root = targetNode.right;
            }
        }
    }

    /**
     * 删除结点：如果要删除的结点有左右子树
     * @param parent 要删除结点的父结点
     * @param targetNode 要删除的结点
     */
    public Node delNodeTwoTree(Node parent,Node targetNode){
        //得到右子树的最小值
        Node min = delRightTreeMin(targetNode.right);
        //将最小结点替换删除的结点,达成删除结点的效果
        min.left = targetNode.left;
        min.right = targetNode.right;
        if (parent != null) {
            if (parent.left == targetNode) {
                parent.left = min;
            } else {
                parent.right = min;
            }
        }

        return min;
    }

    /**
     * 删除结点：如果要删除的结点为叶子结点
     * @param parent 要删除结点的父结点
     * @param value 要删除的结点的值
     */
    public void delLeafNode(Node parent,int value){
        //判断targetNode 是 父结点的左、右子结点
        if (parent.left != null && parent.left.value == value){
            //删除的结点是父结点的左子结点
            parent.left = null;
        }
        else if (parent.right != null && parent.right.value == value){
            //删除的结点是父结点的右子结点
            parent.right = null;
        }
    }



    //删除结点
    private Node delNode(int value){
        if (root == null){
            return null;
        }
        //查找要删除的结点
        Node targetNode = search(value);
        //判断是否找到
        if (targetNode == null){
            return null;
        }

        //如果发现当前这棵二叉树只有一个结点,删除的就是根结点
        if (root.left == null && root.right == null){
            root = null;
            return null;
        }

        //找父结点
        Node parent = searchParent(value);

        //如果要删除的结点是叶子结点
        if (targetNode.left == null && targetNode.right == null){
            delLeafNode(parent,value);
            return parent;
        }
        //如果删除的结点有左右子树
        else if (targetNode.left != null && targetNode.right != null){
            Node node = delNodeTwoTree(parent, targetNode);
            return node;
        }
        //删除只有一棵子树的结点
        else {
            delNodeOneTree(parent,targetNode,value);
            return parent;
        }

    }

    //删除结点并平衡
    public void delNodeBalance(int value) {
        Node node = delNode(value);
        balance(node);
    }

    /**
     * 删除结点后，需要回溯父结点，计算平衡因子,并平衡
     */
    private void balance(Node node){
        
        while (node != null){
            node.judge();
            node = searchParent(node.value);
        }

    }

}

//树结点
class Node{
    int value;
    //左右子结点
    Node left;
    Node right;

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

    //返回左子树的高度
    public int leftHeight(){
        if (left == null){
            return 0;
        }
        else {
            return left.height();
        }
    }

    //返回右子树的高度
    public int rightHeight(){
        if (right == null){
            return 0;
        }
        else {
            return right.height();
        }
    }

    //当前结点的高度：该结点 为 根节点 的树的高度
    public int height(){
        //递归左子树、右子树，取最大值
        return Math.max(left == null ? 0 : left.height(),right == null ? 0 : right.height()) + 1 ;
    }


    /**
     * 左旋
     */
    private void leftRotate(){
        //创建一个新结点，为当前结点的值
        Node newNode = new Node(value);
        //把新的结点的左/右子树设置为当前结点的左子树
        newNode.left = left;
        newNode.right = right.left;
        //把当前结点的值替换成右子树的值
        value = right.value;
        //把当前结点的右子树设置为当前结点的右子树的右子树
        right = right.right;
        //把当前结点的左子树设置为新结点的
        left = newNode;
    }

    /**
     * 右旋
     */
    private void rightRotate(){
        //创建一个新结点,值为当前结点的值
        Node newNode = new Node(value);

        //新结点的左/右子树
        newNode.right = right;
        newNode.left = left.right;

        //当前结点改为左子结点
        value = left.value;
        left = left.left;

        right = newNode;
    }

    /**
     * 查找结点
     * @param value 查找结点的值
     * @return 要查找的结点，没找到返回null
     */
    public Node search(int value){
        if (value == this.value){
            //找到就是该结点
            return this;
        }
        else if (value < this.value){
            //查找的值小于当前结点，向左子树递归查找
            //如果存在左子结点
            if (this.left != null) {
                return this.left.search(value);
            }
            else {
                //不存在左子结点，说明查找不到
                return null;
            }
        }
        else {
            //查找的值大于当前的值,向右子树递归查找
            //如果存在右子结点
            if (this.right != null){
                return this.right.search(value);
            }
            else{
                //不存在右子结点，说明查找不到
                return null;
            }
        }
    }

    /**
     * 查找结点的父结点
     * @param value 要查找结点的值
     * @return 返回要查找的结点的父结点，没有就返回null
     */
    public Node searchParent(int value){
        //当前结点就是要删除的结点的父结点，就返回
        if ((this.left != null && this.left.value == value) ||
                (this.right != null && this.right.value == value) ){
            return this;
        }
        else {
            //如果查找的值小于当前结点
            if (value < this.value && this.left != null){
                //向左子树递归查找
                return this.left.searchParent(value);
            }
            //如果查找的值大于等于当前结点
            else if (value >= this.value && this.right != null){
                //向右子树递归查找
                return this.right.searchParent(value);
            }else {
                //都不满足，就找不到父结点
                return null;
            }
        }

    }


    //按照二叉树排序树添加结点
    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);
            }
        }

        //当添加完一个结点，需要判断平衡
        judge();
    }

    /**
     * 判断平衡
     */
    public void judge(){

        //右子树高度 - 左子树高度 > 1 , 左旋
        if (rightHeight() - leftHeight() > 1) {
            //如果是不平衡情况是 ： 插入右子树的左子树
            if (right != null && right.leftHeight() > right.rightHeight()) {
                //先对当前结点的右子树进行右旋
                right.rightRotate();
                //再对当前结点进行左旋
                leftRotate();
            } else {
                leftRotate();
            }
            //直接退出即可
            return;
        }
        //左子树高度 - 右子树高度 > 1 , 右旋
        if (leftHeight() - rightHeight() > 1){
            //如果是不平衡情况是 ： 插入左子树的右子树
            if (left != null && left.rightHeight() > left.leftHeight()) {
                //先对当前结点的左子树 - 》 左旋
                left.leftRotate();
                //再对当前结点进行右旋
                rightRotate();
            }
            else {
                //直接右旋
                rightRotate();
            }
        }
    }



    //中序遍历
    public void infixOrder(){
        if (this.left != null){
            this.left.infixOrder();
        }

        System.out.print(this);

        if (this.right != null){
            this.right.infixOrder();
        }
    }

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

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
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479

结果：

删除结点：