平衡二叉树【Java实现】_java 实现平衡二叉树

一、二叉排序树存在的问题

二叉排序树相关内容：二叉排序树【Java实现】

假定存在一个序列{ 1, 2, 3, 4, 5, 6, 7}，创建一棵二叉排序树如下：
1

此时，该二叉排序树更类似于一根单链表，无法发挥二叉排序树的优势
且每次需要比较左子树，查询速度比单链表还慢
1
2

二、平衡二叉树

1. 概念

平衡二叉树也叫平衡二叉搜索树（Self-balancing Binary Search Tree），又被称为 AVL 树，可以保证查询效率很高
平衡二叉树的特点：
它是一棵空树或者它的左右两棵子树的高度差的绝对值不超过1，且其左右两棵子树都是一棵平衡二叉树

概念图示：

2. 左旋转

在构建一棵平衡二叉树的过程中，插入某一个节点后，出现了 右子树高度 - 左子树高度 > 1 时，则需要将该树进行左旋转，来降低右子树的高度，使其仍满足平衡二叉树

思路:

1.创建一个新节点，值等于当前节点的值
2.将新节点的左子树置为当前节点的左子树
3.将新节点的右子树置为当前节点右子节点的左子树
4.将当前节点的值置为当前节点的右子节点的值
5.将当前节点的右子树置为当前节点右子节点的右子树
6.将当前节点的左子节点置为新节点
1
2
3
4
5
6

思路图示：

2. 右旋转

在构建一棵平衡二叉树的过程中，插入某一个节点后，出现了 左子树高度 - 右子树高度 > 1 时，则需要将该树进行右旋转，来降低左子树的高度，使其仍满足平衡二叉树

思路:

1.创建一个新节点，值等于当前节点的值
2.将新节点的右子树置为当前节点的右子树
3.将新节点的左子树置为当前节点左子节点的右子树
4.将当前节点的值置为当前节点的左子节点的值
5.将当前节点的左子树置为当前节点左子节点的左子树
6.将当前节点的右子节点置为新节点
1
2
3
4
5
6

思路图示：

3. 双旋转

在某些情况下，单旋转无法将非平衡二叉树转成平衡二叉树（如下图），此时就需要进行双旋转

思路：

当进行右旋转时：
	如果当前节点的左子节点的右子树的高度大于其左子节点的左子树的高度
	则先对该节点的左子节点进行左旋转
	再对该节点进行右旋转
当进行左旋转时：
	如果当前节点的右子节点的左子树的高度大于其右子节点的右子树的高度
	则先对该节点的右子节点进行右旋转
	再对该节点进行左旋转
1
2
3
4
5
6
7
8

思路图示：

4. 代码实现

代码如下：

public class AVLTreeDemo {
    public static void main(String[] args) {
        int[] arr = {10, 11, 7, 6, 8, 9};
        AVLTree avlTree = new AVLTree();
        for (int value : arr) {
            avlTree.add(value);
        }
        avlTree.midOrder();
        System.out.println("当前二叉树的高度：");
        System.out.println(avlTree.getRoot().height());
        System.out.println("当前二叉树左子树的高度：");
        System.out.println(avlTree.getRoot().leftHeight());
        System.out.println("当前二叉树右子树的高度：");
        System.out.println(avlTree.getRoot().rightHeight());
    }
}

class AVLTree {
    static class Node {

        private int value;
        private Node left;
        private Node right;

        public Node() {
        }

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

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

        /**
         * 添加节点（以平衡二叉树形式）
         * 平衡二叉树的前提是满足二叉排序树
         * 每添加一个节点都要判断是否仍符合平衡二叉树
         *
         * @param value 待添加的数据
         */
        public void add(int value) {
            //如果待添加数据小于当前节点的值
            if (value < this.value) {
                //如果左子节点为空，则将其添加为左子节点
                if (this.left == null) {
                    this.left = new Node(value);
                    return;
                }
                //否则向左递归寻找位置添加
                this.left.add(value);
                //如果待添加数据大于或等于当前节点的值
            } else {
                //如果右子节点为空，则将其添加为右子节点
                if (this.right == null) {
                    this.right = new Node(value);
                    return;
                }
                //否则向右递归寻找位置添加
                this.right.add(value);
            }
            //如果 右子树的高度 - 左子树的高度 > 1
            if (rightHeight() - leftHeight() > 1) {
                //如果此时右子节点不为空
                //且右子节点的 左子树的高度 > 右子树的高度
                if (right != null && right.leftHeight() > right.rightHeight()) {
                    //则先将该右子树进行右旋转，在进行后续左旋转
                    right.rightRotate();
                }
                //否则直接进行左旋转
                leftRotate();
                return;
            }
            //如果 左子树的高度 - 右子树的高度 > 1
            if (leftHeight() - rightHeight() > 1) {
                //如果此时左子节点不为空
                //且左子节点的 右子树的高度 < 左子树的高度
                if (left != null && left.rightHeight() > left.leftHeight()) {
                    //则将左子树进行左旋转，再进行后续右旋转
                    left.leftRotate();
                }
                //否则直接进行右旋转
                rightRotate();
            }
        }

        /**
         * 中序遍历二叉树
         */
        public void midOrder() {
            if (this.left != null) {
                this.left.midOrder();
            }
            System.out.println(this);
            if (this.right != null) {
                this.right.midOrder();
            }
        }

        public Node search(int value) {
            if (this.value == value) {
                return this;
            } else if (this.left != null && value < this.value) {
                return this.left.search(value);
            } else if (this.right != null && value > this.value) {
                return this.right.search(value);
            }
            return null;
        }

        private Node searchParent(int value) {
            if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
                return this;
            } else if (this.left != null && value < this.value) {
                return this.left.searchParent(value);
            } else if (this.right != null && value > this.value) {
                return this.right.searchParent(value);
            }
            return null;
        }

        /**
         * @return 当前二叉树的高度
         */
        public int height() {
            return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
        }

        /**
         * @return 当前二叉树左子树的高度
         */
        public int leftHeight() {
            if (left == null) {
                return 0;
            } else {
                return left.height();
            }
        }

        /**
         * @return 当前二叉树右子树的高度
         */
        public int rightHeight() {
            if (right == null) {
                return 0;
            } else {
                return right.height();
            }
        }

        /**
         * 左旋转
         */
        public void leftRotate() {
            Node node = new Node(this.value);
            node.left = this.left;
            node.right = this.right.left;
            this.value = this.right.value;
            this.right = this.right.right;
            this.left = node;
        }

        /**
         * 右旋转
         */
        public void rightRotate() {
            Node node = new Node(this.value);
            node.right = this.right;
            node.left = this.left.right;
            this.value = this.left.value;
            this.left = this.left.left;
            this.right = node;
        }
    }

    private Node root;

    public Node getRoot() {
        return root;
    }

    public void add(int value) {
        if (root == null) {
            root = new Node(value);
        } else {
            root.add(value);
        }
    }

    public void midOrder() {
        if (root == null) {
            System.out.println("当前二叉树为空！无法进行中序遍历");
        } else {
            root.midOrder();
        }
    }

    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);
        }
    }

    public int delMinRightNode(Node node) {
        Node target = node;
        if (target.left != null) {
            target = target.left;
        }
        delNode(target.value);
        return target.value;
    }

    public void delNode(int value) {
        if (root == null) {
            System.out.println("当前二叉树为空！无法进行删除操作！");
        } else {
            Node targetNode = search(value);
            if (targetNode == null) {
                return;
            }
            if (root.left == null && root.right == null) {
                root = null;
                return;
            }
            Node parentNode = searchParent(value);
            if (targetNode.left == null && targetNode.right == null) {
                if (parentNode.left == targetNode) {
                    parentNode.left = null;
                } else {
                    parentNode.right = null;
                }
            } else if (targetNode.left != null && targetNode.right != null) {
                targetNode.value = delMinRightNode(targetNode);
            } else {
                if (targetNode.left != null) {
                    if (parentNode != null) {
                        if (parentNode.left == targetNode) {
                            parentNode.left = targetNode.left;
                        } else {
                            parentNode.right = targetNode.left;
                        }
                    } else {
                        root = targetNode.left;
                    }
                } else {
                    if (parentNode != null) {
                        if (parentNode.left == targetNode) {
                            parentNode.left = targetNode.right;
                        } else {
                            parentNode.right = targetNode.right;
                        }
                    } else {
                        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

测试结果：

Node{value=6}
Node{value=7}
Node{value=8}
Node{value=9}
Node{value=10}
Node{value=11}
当前二叉树的高度：
3
当前二叉树左子树的高度：
2
当前二叉树右子树的高度：
2
1
2
3
4
5
6
7
8
9
10
11
12