数据结构 AVL树

作者：花生_TL007 | 2024-04-30 05:13:43

踩

含有n个结点的平衡二叉树的最大深度

　　AVL（Adelson-Velskii和Landis）树即平衡二叉树，是带有平衡条件（balance condition）的二叉搜索树。平衡二叉树要么是一棵空树，要么左子树和右子树都是平衡二叉树，并且左子树和右子树的高度差的绝对值不超过1。平衡因子BF（Balance Factor）定义为结点左子树与右子树的高度差，也就是说，平衡二叉树结点的平衡因子是-1、0或1。含有n个结点的平衡二叉树的最大深度为O(log₂n)，所以，平衡二叉树的平均查找长度为O(log₂n)。

　　保证平衡的基本思想：每当在二叉搜索树中插入（或删除）一个结点时，检查插入路径上的结点是否因为该操作而导致不平衡。如果失衡，那么先找到插入路径上离插入结点最近的平衡因子绝对值大于1的结点A，再对以A为根的子树，在保持二叉搜索树特性的前提下，调整各结点的位置关系，使之重新达到平衡。每次调整的对象都是最小不平衡子树，即在插入路径上离插入结点最近的平衡因子的绝对值大于1的结点作为根的子树。如果需要调整平衡二叉树，那么这棵二叉树肯定是刚刚开始不平衡的，只需要调整插入新结点导致的最小不平衡子树即可。

　　相比于二叉搜索树，平衡二叉树的树结点增加了属性bf，用于存储平衡因子。

 1 // TreeNode静态嵌套类
 2 private static class TreeNode<E> {
 3     // 元素
 4     private E element;
 5     // 左孩子
 6     private TreeNode<E> left;
 7     // 右孩子
 8     private TreeNode<E> right;
 9     // 平衡因子
10     private int bf;
11     
12     private TreeNode(E e) {
13         element = e;
14     }
15 }

　　两个基本操作：左旋转和右旋转

　　左旋转图示：

 1 // 左旋转
 2 /* 
 3     R->lchild (结点2的左孩子) 为NULL    R->lchild != NULL 
 4     例 :   1                          例 ：   9            15  
 5             \                               / \          /  \ 
 6               2    =>    2                 6  15   =>   9   17  
 7                 \       / \                   / \      / \  / 
 8                  3     1   3                 10 17    6  10 16   
 9                                                 / 
10                                                16 
11    */  
12 private TreeNode<E> LeftRotate(TreeNode<E> treeNode) {
13     TreeNode<E> rightTreeNode = treeNode.right;
14     treeNode.right = rightTreeNode.left;
15     rightTreeNode.left = treeNode;
16     
17     return rightTreeNode;
18 }

　　右旋转图示：

 1 // 右旋转
 2 /* 
 3 L->rchild (结点2的右孩子) 为NULL   L->rchild != NULL 
 4 例 :    3                        例 ：  9           6  
 5        /                            　 / \         / \ 
 6       2    =>    2                    6  10   =>  5   9 
 7      /          / \                  / \         /   / \ 
 8     1          1   3                5   7       4   7  10 
 9                                    / 
10                                   4 
11  */  
12 private TreeNode<E> RightRotate(TreeNode<E> treeNode) {
13     TreeNode<E> leftTreeNode = treeNode.left;
14     treeNode.left = leftTreeNode.right;
15     leftTreeNode.right = treeNode;
16     
17     return leftTreeNode;
18 }

　　两个复杂操作：先左旋转后右旋转和先右旋转后左旋转

　　先右旋转后左旋转图示：

 1 // 左平衡旋转调整，左子树高度大于右子树高度，treeNode的平衡因子大于1
 2 /* 
 3         8                     5                    
 4        / \                   / \            
 5       5   9   (直接右旋)     4   8      
 6      / \            =>     /   / \          
 7     4   6                 3   6   9        
 8    /                                                  
 9  3(新插入)             
10                      
11     8                            8                           7 
12    / \                          / \                         /  \ 
13   5   9  (以5为根，左旋转)       7   9   (以8为根，右旋转)     5    8 
14  / \           =>             /               =>          / \    \ 
15 4   7                        5                           4   6    9 
16     /                       / \  
17    6(新插入)                4   6   
18 
19         8                         8                         6 
20        / \                       / \                       / \ 
21       5   9   (以5为根，左旋转)   6   9  (以8为根，右旋转)    5   8 
22      / \             =>        / \            =>         /   / \  
23     4   6                     5   7                     4   7   9 
24          \                   /    
25           7(新插入)          4 
26 */
27 private TreeNode<E> leftBalance(TreeNode<E> treeNode) {
28     TreeNode<E> leftTreeNode = treeNode.left, root = null;
29     // 检查左子树平衡度，并做相应的平衡调整
30     switch (leftTreeNode.bf) {
31     // 新结点插入到左孩子的左子树上，右旋转
32     case LH:
33         treeNode.bf = leftTreeNode.bf = EH;
34         root = rightRotate(treeNode);
35         break;
36     // 新结点插入到左孩子的右子树上，先左旋转后右旋转
37     case RH:
38         TreeNode<E> leftRightTreeNode = leftTreeNode.right;
39         // 检查左孩子的右子树平衡度，并做相应的平衡调整
40         switch (leftRightTreeNode.bf) {
41         case LH:
42             treeNode.bf = RH;
43             leftTreeNode.bf = EH;
44             break;
45         case EH:
46             treeNode.bf = leftTreeNode.bf = EH;
47             break;
48         case RH:
49             treeNode.bf = EH;
50             leftTreeNode.bf = LH;
51             break;
52         }
53         
54         leftRightTreeNode.bf = EH;
55         treeNode.left = leftRotate(leftTreeNode);
56         root = rightRotate(treeNode);
57     }
58     
59     return root;
60 }

 1 // 右平衡旋转调整，左子树高度小于右子树高度，treeNode的平衡因子小于-1
 2 // 与左平衡旋转调整对称
 3 private TreeNode<E> rightBalance(TreeNode<E> treeNode) {
 4     TreeNode<E> rightTreeNode = treeNode.right, root = null;
 5     // 检查右子树平衡度，并做相应的平衡调整
 6     switch (rightTreeNode.bf) {
 7     // 新结点插入到右孩子的右子树上，左旋转
 8     case RH:
 9         treeNode.bf = rightTreeNode.bf = EH;
10         root = leftRotate(treeNode);
11         break;
12     // 新结点插入到右孩子的左子树上，先右旋转后左旋转
13     case LH:
14         TreeNode<E> rightLeftTreeNode = rightTreeNode.left;
15         // 检查右孩子的左子树平衡度，并做相应的平衡调整
16         switch (rightLeftTreeNode.bf) {
17         case RH:
18             treeNode.bf = LH;
19             rightTreeNode.bf = EH;
20             break;
21         case EH:
22             treeNode.bf = rightTreeNode.bf = EH;
23             break;
24         case LH:
25             treeNode.bf = EH;
26             rightTreeNode.bf = RH;
27             break;
28         }
29         
30         rightLeftTreeNode.bf = EH;
31         treeNode.right = rightRotate(rightTreeNode);
32         root = leftRotate(treeNode);
33     }
34     
35     return root;
36 }

 1 // 子树上插入元素
 2 private TreeNode<E> insert(TreeNode<E> treeNode, E e) {
 3     if (treeNode == null) {
 4         return new TreeNode<E>(e);
 5     }
 6     
 7     int compareResult = e.compareTo(treeNode.element);
 8     if (compareResult < 0) {
 9         treeNode.left = insert(treeNode.left, e);
10     } else if (compareResult > 0) {
11         treeNode.right = insert(treeNode.right, e);
12     }
13     
14     return balance(treeNode);
15 }

 1 // 子树上删除元素
 2 private TreeNode<E> remove(TreeNode<E> treeNode, E e) {
 3     if (treeNode == null) {
 4         return null;
 5     }
 6     
 7     int compareResult = e.compareTo(treeNode.element);
 8     TreeNode<E> l = treeNode.left, r = treeNode.right;
 9     if (compareResult < 0) {
10         treeNode.left = remove(l, e);
11     } else if (compareResult > 0) {
12         treeNode.right = remove(r, e);
13     } else if (l != null && r != null) {
14         treeNode.element = findMax(l).element;
15         treeNode.left = remove(treeNode.left, treeNode.element);
16     } else {
17         treeNode = (l != null) ? l : r;
18     }
19     
20     return treeNode;
21 }

 1 // 调整子树
 2 private TreeNode<E> balance(TreeNode<E> treeNode) {
 3     if (treeNode == null) {
 4         return null;
 5     }
 6     
 7     int treeNodeBf = treeNode.bf;
 8     if (treeNodeBf > LH) {
 9         treeNode = leftBalance(treeNode);
10     } else if (treeNodeBf < RH) {
11         treeNode = rightBalance(treeNode);
12     }
13     
14     return treeNode;
15 }

　　完整代码：

  1 // 实现了Comparable接口的元素可以通过compareTo方法来比较
  2 public class AVLTree<E extends Comparable<? super E>> {
  3     // 左高
  4     private static final int LH = 1;
  5     // 等高
  6     private static final int EH = 0;
  7     // 右高
  8     private static final int RH = -1;
  9     
 10     // TreeNode静态嵌套类
 11     private static class TreeNode<E> {
 12         // 元素
 13         private E element;
 14         // 左孩子
 15         private TreeNode<E> left;
 16         // 右孩子
 17         private TreeNode<E> right;
 18         // 平衡因子
 19         private int bf;
 20         
 21         private TreeNode(E e) {
 22             element = e;
 23         }
 24     }
 25     
 26     // 根结点
 27     private TreeNode<E> root;
 28     
 29     // 无参构造方法
 30     public AVLTree() {
 31         root = null;
 32     }
 33     
 34     // 二叉搜索树置空
 35     public void makeEmpty() {
 36         root = null;
 37     }
 38     
 39     // 判断树是否为空
 40     public boolean isEmpty() {
 41         return root == null;
 42     }
 43     
 44     // 判断是否包含指定元素
 45     public boolean contains(E e) {
 46         return contains(root, e);
 47     }
 48     
 49     // 获取最小元素
 50     public E findMin() {
 51         if (isEmpty()) {
 52             throw new NullPointerException();
 53         }
 54         
 55         return findMin(root).element;
 56     }
 57     
 58     // 获取最大元素
 59     public E findMax() {
 60         if (isEmpty()) {
 61             throw new NullPointerException();
 62         }
 63         
 64         return findMax(root).element;
 65     }
 66         
 67     // 插入指定元素
 68     public void insert(E e) {
 69         root = insert(root, e);
 70     }
 71     
 72     // 刪除指定元素
 73     public void remove(E e) {
 74         root = remove(root, e);
 75     }
 76         
 77     // 遍历树
 78     public void printTree() {
 79         if (root == null) {
 80             throw new NullPointerException();
 81         }
 82         
 83         inorder(root);
 84     }
 85     
 86     // 判断子树上是否包含指定元素
 87     private boolean contains(TreeNode<E> treeNode, E e) {
 88         if (treeNode == null) {
 89             return false;
 90         }
 91         
 92         while (treeNode != null) {
 93             int compareResult = e.compareTo(treeNode.element);
 94             if (compareResult == 0) {
 95                 return true;
 96             } else if (compareResult < 0) {
 97                 treeNode = treeNode.left;
 98             } else {
 99                 treeNode = treeNode.right;
100             }
101         }
102         
103         return false;
104     }
105         
106     // 子树上寻找最小值
107     private TreeNode<E> findMin(TreeNode<E> treeNode) {
108         if (treeNode == null) {
109             return null;
110         }
111         
112         while (treeNode.left != null) {
113             treeNode = treeNode.left;
114         }
115         
116         return treeNode;
117     }
118     
119     // 子树上寻找最大值
120     private TreeNode<E> findMax(TreeNode<E> treeNode) {
121         if (treeNode == null) {
122             return null;
123         }
124         
125         while (treeNode.right != null) {
126             treeNode = treeNode.right;
127         }
128         
129         return treeNode;
130     }
131         
132     // 子树上插入元素
133     private TreeNode<E> insert(TreeNode<E> treeNode, E e) {
134         if (treeNode == null) {
135             return new TreeNode<E>(e);
136         }
137         
138         int compareResult = e.compareTo(treeNode.element);
139         if (compareResult < 0) {
140             treeNode.left = insert(treeNode.left, e);
141         } else if (compareResult > 0) {
142             treeNode.right = insert(treeNode.right, e);
143         }
144         
145         return balance(treeNode);
146     }
147     
148     // 子树上删除元素
149     private TreeNode<E> remove(TreeNode<E> treeNode, E e) {
150         if (treeNode == null) {
151             return null;
152         }
153         
154         int compareResult = e.compareTo(treeNode.element);
155         TreeNode<E> l = treeNode.left, r = treeNode.right;
156         if (compareResult < 0) {
157             treeNode.left = remove(l, e);
158         } else if (compareResult > 0) {
159             treeNode.right = remove(r, e);
160         } else if (l != null && r != null) {
161             treeNode.element = findMax(l).element;
162             treeNode.left = remove(treeNode.left, treeNode.element);
163         } else {
164             treeNode = (l != null) ? l : r;
165         }
166         
167         return treeNode;
168     }
169     
170     // 调整子树
171     private TreeNode<E> balance(TreeNode<E> treeNode) {
172         if (treeNode == null) {
173             return null;
174         }
175         
176         int treeNodeBf = treeNode.bf;
177         if (treeNodeBf > LH) {
178             treeNode = leftBalance(treeNode);
179         } else if (treeNodeBf < RH) {
180             treeNode = rightBalance(treeNode);
181         }
182         
183         return treeNode;
184     }
185     
186     // 左旋转
187     private TreeNode<E> leftRotate(TreeNode<E> treeNode) {
188         TreeNode<E> rightTreeNode = treeNode.right;
189         treeNode.right = rightTreeNode.left;
190         rightTreeNode.left = treeNode;
191         
192         return rightTreeNode;
193     }
194     
195     // 右旋转
196     private TreeNode<E> rightRotate(TreeNode<E> treeNode) {
197         TreeNode<E> leftTreeNode = treeNode.left;
198         treeNode.left = leftTreeNode.right;
199         leftTreeNode.right = treeNode;
200         
201         return leftTreeNode;
202     }
203     
204     // 左平衡旋转调整，左子树高度大于右子树高度，treeNode的平衡因子大于1
205     private TreeNode<E> leftBalance(TreeNode<E> treeNode) {
206         TreeNode<E> leftTreeNode = treeNode.left, root = null;
207         // 检查左子树平衡度，并做相应的平衡调整
208         switch (leftTreeNode.bf) {
209         // 新结点插入到左孩子的左子树上，右旋转
210         case LH:
211             treeNode.bf = leftTreeNode.bf = EH;
212             root = rightRotate(treeNode);
213             break;
214         // 新结点插入到左孩子的右子树上，先左旋转后右旋转
215         case RH:
216             TreeNode<E> leftRightTreeNode = leftTreeNode.right;
217             // 检查左孩子的右子树平衡度，并做相应的平衡调整
218             switch (leftRightTreeNode.bf) {
219             case LH:
220                 treeNode.bf = RH;
221                 leftTreeNode.bf = EH;
222                 break;
223             case EH:
224                 treeNode.bf = leftTreeNode.bf = EH;
225                 break;
226             case RH:
227                 treeNode.bf = EH;
228                 leftTreeNode.bf = LH;
229                 break;
230             }
231             
232             leftRightTreeNode.bf = EH;
233             treeNode.left = leftRotate(leftTreeNode);
234             root = rightRotate(treeNode);
235         }
236         
237         return root;
238     }
239     
240     // 右平衡旋转调整，左子树高度小于右子树高度，treeNode的平衡因子小于-1
241     // 与左平衡旋转调整对称
242     private TreeNode<E> rightBalance(TreeNode<E> treeNode) {
243         TreeNode<E> rightTreeNode = treeNode.right, root = null;
244         // 检查右子树平衡度，并做相应的平衡调整
245         switch (rightTreeNode.bf) {
246         // 新结点插入到右孩子的右子树上，左旋转
247         case RH:
248             treeNode.bf = rightTreeNode.bf = EH;
249             root = leftRotate(treeNode);
250             break;
251         // 新结点插入到右孩子的左子树上，先右旋转后左旋转
252         case LH:
253             TreeNode<E> rightLeftTreeNode = rightTreeNode.left;
254             // 检查右孩子的左子树平衡度，并做相应的平衡调整
255             switch (rightLeftTreeNode.bf) {
256             case RH:
257                 treeNode.bf = LH;
258                 rightTreeNode.bf = EH;
259                 break;
260             case EH:
261                 treeNode.bf = rightTreeNode.bf = EH;
262                 break;
263             case LH:
264                 treeNode.bf = EH;
265                 rightTreeNode.bf = RH;
266                 break;
267             }
268             
269             rightLeftTreeNode.bf = EH;
270             treeNode.right = rightRotate(rightTreeNode);
271             root = leftRotate(treeNode);
272         }
273         
274         return root;
275     }
276         
277     // 中序遍历
278     private void inorder(TreeNode<E> treeNode) {
279         if (treeNode == null) {
280             return;
281         }
282         
283         TreeNode<E> l = treeNode.left, r = treeNode.right;
284         if (l != null) {
285             inorder(l);
286         }
287         
288         System.out.print(" " + treeNode.element);
289         
290         if (r != null) {
291             inorder(r);
292         }
293     }
294     
295     public static void main(String[] args) {
296         AVLTree<String> avlTree = new AVLTree<String>();
297         String[] key = {"62", "88", "58", "47", "35", "73", "51", "99", "37", "93"};
298         for (int i = 0; i < 10; i++) {
299             avlTree.insert(key[i]);
300         }
301         
302         System.out.println("中序遍历结果：");
303         avlTree.printTree();
304         System.out.println();
305         
306         avlTree.remove("58");
307         System.out.println("删除58后中序遍历结果：");
308         avlTree.printTree();
309         System.out.println();
310     }
311 }

　　输出结果

中序遍历结果：
 35 37 47 51 58 62 73 88 93 99
删除58后中序遍历结果：
 35 37 47 51 62 73 88 93 99

　　参考资料

　　平衡二叉树（AVL树）

　　《数据结构与算法分析Java语言描述原书第3版》 P91-94

　　《2017年数据结构联考复习指导》 P156

转载于:https://www.cnblogs.com/WJQ2017/p/8342287.html

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