【数据结构与算法】平衡二叉树之AVL树的介绍和程序实现_c++ avl树 替罪羊树

1. 二叉排序树的问题

将一个数列{1, 2, 3, 4, 5, 6}，创建一颗二叉排序树，如下所示

可以看到存在如下问题：

• 左子树全部为空，更像一个单链表
• 因为需要依次比较，而且每次还需要比较左子树，查询速度比单链表还慢

2. 平衡二叉树的介绍

平衡二叉树(平衡二叉搜索树、Self-balancing binary search tree、AVL树)可以保证较高的查询效率。

特点：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也是一棵平衡二叉树，即子树递归下去也是平衡二叉树

如下的第1个和第2个是平衡二叉树，第3个不是平衡二叉树

平衡二叉树的常用实现方法有红黑树、AVL树、替罪羊树、Treap树、伸展树等

2. AVL树之左旋转

在二叉排序树添加节点后，如果右子树比左子树的高度差大于1，则需要进行左旋转

例如对于数列{4, 3, 6, 5, 7}创建的二叉排序树，当添加值为8的节点时，右子树比左子树的高度差大于1，如下所示

所以需要进行左旋转，步骤如下：

1. 创建一个新的节点newNode, newNode的值等于当前节点的值。这里的当前节点为root节点
2. 将newNode的左子节点设置为当前节点的左子节点，即newNode.left = left
3. 将newNode的右子节点设置为当前节点的右子节点的左子节点，即newNode.right = right.left
4. 将当前节点的值换成右子节点的值，即value = right.value
5. 将当前节点的右子节点设置为当前节点的右子节点的右子节点，即right = right.right
6. 将当前节点的左子节点设置为newNode，即left = newNode

左旋转完成后的结果如下：

左旋转需求：将数列{4, 3, 6, 5, 7, 8}，创建出一颗平衡二叉树

3. AVL树之右旋转

在二叉排序树添加节点后，如果左子树比右子树的高度差大于1，则需要进行右旋转

例如对于数列{10, 12, 8, 9, 7}创建的二叉排序树，当添加值为6的节点时，左子树比右子树的高度差大于1，如下所示

所以需要进行右旋转，步骤如下：

1. 创建一个新的节点newNode, newNode的值等于当前节点的值。这里的当前节点为root节点
2. 将newNode的右子节点设置为当前节点的右子节点，即newNode.right = right
3. 将newNode的左子节点设置为当前节点的左子节点的右子节点，即newNode.left = left.right
4. 将当前节点的值换成左子节点的值，即value = left.value
5. 将当前节点的左子节点设置为当前节点的左子节点的左子节点，即left = left.left
6. 将当前节点的右子节点设置为newNode，即right = newNode

右旋转完成后的结果如下：

右旋转需求：将数列{10, 12, 8, 9, 7, 6}，创建出一颗平衡二叉树

4. AVL树之双旋转

某些情况下，单旋转并不能转换成平衡二叉树。比如数列{10, 11, 7, 6, 8, 9}和{2,1, 6, 5, 7, 3}

例如将数列{10, 11, 7, 6, 8, 9}创建的二叉排序树，进行右旋转，得到的结果如下：

右旋转问题的解决办法：
如果当前节点的左子节点的右子树高度，大于当前节点的左子节点的左子树的高度，需要先对当前节点的左子树进行左旋转，再对当前节点进行右旋转

同理，左旋转问题的解决办法：
如果当前节点的右子节点的左子树高度，大于当前节点的右子节点的右子树的高度，需要先对当前节点的右子树进行右旋转，再对当前节点进行左旋转

5. AVL树之左旋转、右旋转、双旋转程序实现

程序如下：

public class AVLTreeDemo {

    public static void main(String[] args) {

        // 左旋转测试数组
        int[] leftRotateArray = {4, 3, 6, 5, 7, 8};
        // 右旋转测试数组
        int[] rightRotateArray = {10, 12, 8, 9, 7, 6};
        // 双旋转测试数组(先右旋转，再左旋转)
        int[] bothRotateArray1 = {2, 1, 6, 5, 7, 3};
        // 双旋转测试数组(先左旋转，再右旋转)
        int[] bothRotateArray2 = {10, 11, 7, 6, 8, 9};

        // >>>>>>>>>>>>>>>>>>>>>>>旋转测试>>>>>>>>>>>>>>>>>>>>>>>>>>
        // 不同的旋转测试，就换成不同的数组
        int[] rotateArray = bothRotateArray2;
        // 创建AVLTree对象
        AVLTree rotateAvlTree = new AVLTree();
        // 添加节点
        for (int i = 0; i < rotateArray.length; i++) {
            rotateAvlTree.add(new Node(rotateArray[i]));
        }

        // 中序遍历
        System.out.println("旋转后进行中序遍历：");
        rotateAvlTree.infixOrder();

        System.out.println("旋转后树的高度 = " + rotateAvlTree.root.height());
        System.out.println("旋转后root的左子树高度 = " + rotateAvlTree.root.leftNodeHeight());
        System.out.println("旋转后root的右子树高度 = " + rotateAvlTree.root.rightNodeHeight());
        System.out.println("当前的root节点 = " + rotateAvlTree.root);
    }
}


// 创建Node节点
class Node {
    int value;
    Node left;
    Node right;

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

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

    // 计算以当前节点为root节点的树的高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    // 计算当前节点的左子树的高度
    public int leftNodeHeight() {
        if (left == null) {
            return 0;
        } else {
            return left.height();
        }

    }

    // 计算当前节点的右子树的高度
    public int rightNodeHeight() {
        if (right == null) {
            return 0;
        } else {
            return right.height();
        }
    }

    // 左旋转实现
    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;
    }


    // 添加节点的方法
    public void add(Node node) {
        if (node == null) {
            return;
        } else {

            // 如果node的值，比当前节点的值小，则向左处理
            if (node.value < this.value) {
                if (this.left == null) {
                    this.left = node;
                } else {
                    // 向左递归添加节点
                    this.left.add(node);
                }
                // 如果node的值，大于等于当前节点的值，则向右处理
            } else {
                if (this.right == null) {
                    this.right = node;
                } else {
                    // 向右递归添加节点
                    this.right.add(node);
                }

            }

            // 当添加完一个节点后，如果(右子树的高度-左子树的高度) > 1, 进行左旋转
            if ((rightNodeHeight() - leftNodeHeight()) > 1) {
                // 如果当前节点的右子节点的左子树高度，大于当前节点的右子节点的右子树的高度
                // 需要先对当前节点的右子树进行右旋转，再对当前节点进行左旋转
                if (right != null && right.leftNodeHeight() > right.rightNodeHeight()) {
                    right.rightRotate();
                    leftRotate();
                } else {
                    leftRotate();
                }
                // 当添加完一个节点后，如果(左子树的高度-右子树的高度) > 1, 进行右旋转
            } else if ((leftNodeHeight() - rightNodeHeight()) > 1) {
                // 如果当前节点的左子节点的右子树高度，大于当前节点的左子节点的左子树的高度
                // 需要先对当前节点的左子树进行左旋转，再对当前节点进行右旋转
                if (left != null && left.rightNodeHeight() > left.leftNodeHeight()) {
                    left.leftRotate();
                    rightRotate();
                } else {
                    rightRotate();
                }
            }
        }
    }

    // 中序遍历实现
    public void infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

    // 查找要删除的结点
    public Node searchDeleteNode(int value) {
        if (value == this.value) {
            return this;
            // 如果值，比当前节点的值小，则向左处理
        } else if (value < this.value) {
            if (this.left == null) {
                return null;
            } else {
                return this.left.searchDeleteNode(value);
            }
            // 如果值，大于等于当前节点的值，则向右处理
        } else {
            if (this.right == null) {
                return null;
            } else {
                return this.right.searchDeleteNode(value);
            }
        }
    }


    // 查找要删除节点的父节点
    public Node searchDeleteParentNode(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.searchDeleteParentNode(value);
                // 再递归向右子节点进行查找
            } else if (value >= this.value && this.right != null) {
                return this.right.searchDeleteParentNode(value); //向右子树递归查找
            } else {
                // 如果不能向左右子节点递归，则返回null
                return null;
            }
        }

    }

}

// 创建AVL树
class AVLTree {
    public Node root;

    // 添加节点的方法
    public void add(Node node) {
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    // 中序遍历实现
    public void infixOrder() {
        if (root != null) {
            root.infixOrder();
        } else {
            System.out.println("AVL树为空，不能遍历");
        }
    }

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

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


    // 传入右子树，删除该子树的最小值节点，然后返回最小值节点的值
    public int delRightTreeMinNode(Node node) {
        Node target = node;
        // 循环查找左子节点，就会找到最小值
        while (target.left != null) {
            target = target.left;
        }
        // 这时target就是最小值节点
        deleteNode(target.value);

        return target.value;
    }


    // 删除节点实现
    public void deleteNode(int value) {
        if (root == null) {
            return;
        } else {
            // 找到要删除的节点targetNode
            Node targetNode = searchDeleteNode(value);
            // 如果没有找到要删除的节点
            if (targetNode == null) {
                return;
            } else {
                // 如果找到节点，且AVL树只有root这一个节点，则直接删除root节点
                if (root.left == null && root.right == null) {
                    root = null;
                    return;
                } else {
                    // 找到targetNode的父节点parentNode
                    Node parentNode = searchDeleteParentNode(value);
                    // 第一种情况：删除叶子节点
                    if (targetNode.left == null && targetNode.right == null) {
                        // 如果targetNode是parentNode的左子节点，则parentNode.left = null
                        if (parentNode.left != null && parentNode.left.value == value) {
                            parentNode.left = null;
                            // 如果targetNode是parentNode的右子节点，则parentNode.right = null
                        } else if (parentNode.right != null && parentNode.right.value == value) {
                            parentNode.right = null;
                        }
                        // 第二种情况：删除有两颗子树的节点
                        // 如果删除的是root节点，parentNode为null也不影响
                    } else if (targetNode.left != null && targetNode.right != null) {
                        int minVal = delRightTreeMinNode(targetNode.right);
                        targetNode.value = minVal;
                        // 第三种情况：删除只有一颗子树的节点
                    } else {
                        // 如果targetNode的子树是左子节点
                        if (targetNode.left != null) {
                            if (parentNode != null) {
                                // 如果targetNode是parentNode的左子节点
                                if (parentNode.left.value == value) {
                                    parentNode.left = targetNode.left;
                                } else {
                                    // 如果targetNode是parentNode的右子节点
                                    parentNode.right = targetNode.left;
                                }
                                // 如果要删除的是root节点，且root节点只有左子树
                            } else {
                                root = targetNode.left;
                            }
                            // 如果targetNode的子树是右子节点
                        } else {
                            if (parentNode != null) {
                                // 如果targetNode是parentNode的左子节点
                                if (parentNode.left.value == value) {
                                    parentNode.left = targetNode.right;
                                } else {
                                    // 如果targetNode是parentNode的右子节点
                                    parentNode.right = targetNode.right;
                                }
                            } else {
                                // 如果要删除的是root节点，且root节点只有右子树
                                root = targetNode.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
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

运行程序，结果如下：

旋转后进行中序遍历：
Node [value = 6]
Node [value = 7]
Node [value = 8]
Node [value = 9]
Node [value = 10]
Node [value = 11]
旋转后树的高度 = 3
旋转后root的左子树高度 = 2
旋转后root的右子树高度 = 2
当前的root节点 = Node [value = 8]
1
2
3
4
5
6
7
8
9
10
11