[数据结构与算法]-平衡二叉树(AVL)介绍及其简单实现(Java)_数据结构与算法——平衡二叉树及代码实现

作者：不正经 | 2024-05-27 13:12:53

踩

数据结构与算法——平衡二叉树及代码实现

本文欢迎转载，转载前请联系作者，经允许后方可转载。转载后请注明出处，谢谢！ http://blog.csdn.net/colton_null 作者：喝酒不骑马 Colton_Null from CSDN

一.什么平衡二叉树(AVL)

AVL(Adelson-Velskii & Landis)是带有平衡条件的二叉查找树，即一种特殊的二叉查找树，它保证树的深度必须为O(logN)。

那么如何保证二叉查找树的这个特性呢？即一颗平衡二叉树的每个节点的左子树和右子树的高度差最多相差1（空树的高度为-1）。

如图所示，树A为一颗AVL树，而树B则不是。因为节点100左子树高为2，而右子树的高为0，相差大于1。
这里写图片描述

二.二叉查找树不平衡的几种状况

随着节点的插入，我们在某次插入后，可能会导致原本的二叉查找树出现不平衡情况。这时候，我们就需要对其进行平衡，平衡后，该树将成为AVL树。那么如何平衡呢？

其实，对于平衡操作，我们可以用一个简单的操作来完成，即旋转(rotation)。在插入一个节点之后，只有那些从插入点到根节点这条路径上的节点的平衡可能会改变。如果一颗AVL树在插入一个节点后变得不平衡，那当我们从插入点向上寻找时，一定会找到一个节点，该节点的左右子树的高度相差大于2，那么这个点，就是一个要被平衡的点。

我们把需要重新平衡的点称其为α，其特征就是它的左右子树高度差2。

所有的不平衡情况总结起来一共有四种场景：

对α节点的左节点的左子树进行一次插入。
对α节点的左节点的右子树进行一次插入。
对α节点的右节点的左子树进行一次插入。
对α节点的右节点的右子树进行一次插入

这里写图片描述

三.如何平衡二叉查找树？

针对于上述第1种、第4种情况，即插入是在外侧时（左-左或右-右的情况），我们可以通过一次单旋转(single rotation)进行平衡调整。

而对于第2种和第3种情况，插入在内侧时（左-右或右-左的情况），我们需要通过双旋转(double rotation)来处理。

1.单旋转

这里写图片描述

上图中，再插入节点30后，原本平衡的二叉树变得不再平衡。经过观察我们可以发现不平衡点是100，它的左子树比右子树高出2层。我们要做的，就是通过单旋转，让右子树降低一层，让左子树提高一层。

如何进行单旋转呢？很简单。不是100的左子树高么，找到100左子树的根节点50，你可以想象一下你提着50这个节点使劲晃动一下，将50这个节点提到根节点（也就是之前100这个节点所在的位置）的位置。节点25和节点100分别变成了节点50的左右节点，这时候，100节点的左节点是空着的。所以根据二叉查找树的性质，节点75比100节点小，所以节点75就做了节点100的左节点。这样，我们就完成了一次单旋转。平衡后的二叉查找树的样子如图所示。
这里写图片描述

情况4和情况1是对称效果，这里就不再赘述了。

2.双旋转

情况2和情况3都属于双旋转，这里我用情况2举例子，情况3与它也为对称效果。
这里写图片描述

如上图所示，插入节点80后，树不再平衡。这种情况，如果还用单旋转的方法，即50变成根节点，那么旋转后，该树还是不平衡的，如下图

这里写图片描述

所以，针对这种情况，我们要经过两次旋转对该树进行平衡。

第一次旋转，将75提到50的位置。然后再将75旋转到100所在的位置。如图所示。
这里写图片描述

这样，经过一次双旋转（即两次单旋转），保证了该二叉查找树的平衡。

四.AVL树的简单实现

AvlTree.java

import java.util.HashMap;
import java.util.Map;

/**
 * Created with IDEA
 * Author: MaYuzhe
 * Date: 2018/6/18
 * Time: 23:36
 * <p>
 * 平衡二叉树 Adelson-Velskii & Landis
 */
public class AvlTree<T extends Comparable<? super T>> {

    private static class AvlNode<T> {
        T element;
        AvlNode<T> left;
        AvlNode<T> right;
        int height;

        AvlNode(T element) {
            this(element, null, null);
        }

        AvlNode(T element, AvlNode<T> left, AvlNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }
    }

    private static final int ALLOWED_IMBALANCE = 1;

    private AvlNode<T> root;

    public AvlTree() {
        root = null;
    }

    /**
     * 插入元素
     *
     * @param t 要被插入的元素
     */
    public void insert(T t) {
        root = insert(t, root);
    }

    /**
     * 移除元素
     *
     * @param t 要被移除的元素
     */
    public void remove(T t) {
        root = remove(t, root);
    }

    /**
     * 检查树是否平衡
     */
    public boolean checkBalance() {
        Map<String, Boolean> resultMap = new HashMap<>(1);
        resultMap.put("isBalance", true);
        checkBalance(root, resultMap);
        return resultMap.get("isBalance");
    }

    /**
     * 按照中序遍历打印树
     */
    public void printTree() {
        if (isEmpty()) {
            System.out.println("空树/Empty tree");
        } else {
            printTree(root);
        }
    }

    /**
     * 判断树是否为空
     *
     * @return 为空则返回true，否则返回false
     */
    public boolean isEmpty() {
        return root == null;
    }

    /**
     * 判断元素是否在树中
     *
     * @param t 要被判断的元素
     * @return 存在则返回true，不存在返回false
     */
    public boolean contains(T t) {
        return contains(t, root);
    }

    /**
     * 使树置空
     */
    public void makeEmpty() {
        root = null;
    }

    /**
     * 查找最小元素
     *
     * @return 最小元素
     */
    public T findMin() {
        if (isEmpty()) {
            return null;
        }
        return findMin(root).element;
    }

    /**
     * 查找最大元素
     *
     * @return 最大元素
     */
    public T findMax() {
        if (isEmpty()) {
            return null;
        }
        return findMax(root).element;
    }

    /**
     * 获得节点的高度
     *
     * @param node 节点
     * @return 节点高度
     */
    private int height(AvlNode<T> node) {
        return node == null ? -1 : node.height;
    }


    private AvlNode<T> insert(T t, AvlNode<T> node) {
        if (node == null) {
            return new AvlNode<>(t, null, null);
        }

        int compareResult = t.compareTo(node.element);
        if (compareResult < 0) {
            node.left = insert(t, node.left);
        } else if (compareResult > 0) {
            node.right = insert(t, node.right);
        }
        return balance(node);
    }

    private AvlNode<T> remove(T t, AvlNode<T> node) {
        if (t == null) {
            return null;
        }
        int compareResult = t.compareTo(node.element);

        if (compareResult < 0) {
            node.left = remove(t, node.left);
        } else if (compareResult > 0) {
            node.right = remove(t, node.right);
        } else if (node.left != null && node.right != null) {
//            node.element = findMin(node.right).element;
//            node.right = remove(node.element, node.right);
            // 用removeRightMin方法替代上面两个操作，将两次遍历合并成一次遍历完成，提高效率
            node.right = removeRightMin(node, node.right);
        } else {
            node = node.left != null ? node.left : node.right;
        }
        return balance(node);
    }

    private AvlNode<T> removeRightMin(AvlNode<T> node, AvlNode<T> rNode) {
        if (rNode.left != null) {
            rNode.left = removeRightMin(node, rNode.left);
        } else {
            node.element = rNode.element;
            rNode = rNode.right;
        }
        return rNode;
    }

    /**
     * 平衡节点
     *
     * @param node
     * @return
     */
    private AvlNode<T> balance(AvlNode<T> node) {
        if (node == null) {
            return null;
        }

        if (height(node.left) - height(node.right) > ALLOWED_IMBALANCE) {
            if (height(node.left.left) >= height(node.left.right)) {
                // 左节点的左子节点高度大于左节点的右子节点或者左右子节点高度相等时
                node = rotateWithLeftChild(node);
            } else {
                node = doubleWithLeftChild(node);
            }
        } else if (height(node.right) - height(node.left) > ALLOWED_IMBALANCE) {
            if (height(node.right.right) >= height(node.right.left)) {
                // 右节点的右子节点高度大于右节点的左子节点或者左右子节点高度相等时
                node = rotateWithRightChild(node);
            } else {
                node = doubleWithRightChild(node);
            }
        }
        node.height = Math.max(height(node.left), height(node.right)) + 1;
        return node;
    }

    /**
     * 左单旋转
     *
     * @param k2
     * @return
     */
    private AvlNode<T> rotateWithLeftChild(AvlNode<T> k2) {
        AvlNode<T> k1 = k2.left;
        k2.left = k1.right;
        k1.right = k2;
        k2.height = Math.max(height(k2.left), height(k2.right)) + 1;
        k1.height = Math.max(height(k1.left), k2.height);
        return k1;
    }

    /**
     * 右单旋转
     *
     * @param k1
     * @return
     */
    private AvlNode<T> rotateWithRightChild(AvlNode<T> k1) {
        AvlNode<T> k2 = k1.right;
        k1.right = k2.left;
        k2.left = k1;
        k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
        k2.height = Math.max(height(k2.right), k1.height) + 1;
        return k2;
    }

    /**
     * 左-右双旋转
     *
     * @param k3
     * @return
     */
    private AvlNode<T> doubleWithLeftChild(AvlNode<T> k3) {
        k3.left = rotateWithRightChild(k3.left);
        return rotateWithLeftChild(k3);
    }

    /**
     * 右-左双旋转
     *
     * @param k1
     * @return
     */
    private AvlNode<T> doubleWithRightChild(AvlNode<T> k1) {
        k1.right = rotateWithLeftChild(k1.right);
        return rotateWithRightChild(k1);
    }

    private boolean contains(T t, AvlNode<T> node) {
        while (node != null) {
            int compareResult = t.compareTo(node.element);

            if (compareResult < 0) {
                node = node.left;
            } else if (compareResult > 0) {
                node = node.right;
            } else {
                return true;    // Match
            }
        }

        return false;   // No match
    }

    private AvlNode<T> findMin(AvlNode<T> node) {
        if (node == null) {
            return null;
        }

        while (node.left != null) {
            node = node.left;
        }
        return node;
    }


    private AvlNode<T> findMax(AvlNode<T> node) {
        if (node == null) {
            return null;
        }

        while (node.right != null) {
            node = node.right;
        }
        return node;
    }

    private int checkBalance(AvlNode<T> node, Map<String, Boolean> resultMap) {
        if (node == null) {
            return -1;
        }
        int leftHeight = checkBalance(node.left, resultMap);
        int rightHeight = checkBalance(node.right, resultMap);
        if (Math.abs(height(node.left) - height(node.right)) > 1 ||
                height(node.left) != leftHeight || height(node.right) != rightHeight)
//            System.out.println("该树不平衡/Not balance");
            resultMap.put("isBalance", false);
        return height(node);
    }

    private void printTree(AvlNode<T> node) {
        if (node != null) {
            printTree(node.left);
            System.out.println(node.element);
            printTree(node.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

测试类
AvlTreeTest.java

/**
 * Created with IDEA
 * Author: MaYuzhe
 * Date: 2018/6/19
 * Time: 18:44
 *
 * AVL测试类
 */
public class AvlTreeTest {
    public static void main(String[] args) {
        AvlTree<Integer> avlTree = new AvlTree<>();
        for (int i = 1; i <= 10; i++) {
            avlTree.insert(i);
        }
        avlTree.printTree();
        System.out.println("该树是否平衡:" + avlTree.checkBalance());

        avlTree.remove(5);
        avlTree.printTree();
        System.out.println("该树是否平衡:" + avlTree.checkBalance());
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

输出：

1
2
3
4
5
6
7
8
9
10
该树是否平衡:true
1
2
3
4
6
7
8
9
10
该树是否平衡:true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

证明AvlTree可用。

以上就是有关平衡二叉树(AVL)的介绍及其基于Java的简单实现。

有关[数据结构与算法]的学习内容已经上传到github，喜欢的朋友可以支持一下。
data-structures-and-algorithm-study-notes-java

站在前人的肩膀上前行，感谢以下博客及文献的支持。

《数据结构与算法分析(第3 版) 工业出版社》

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/632160