- 当前位置：首页 >数据库 >面试官提到的 AVL 树，到底是个啥
面试官提到的 AVL 树，到底是个啥
发布时间：2025-11-03 20:34:38 来源：创站工坊 作者：域名
了解过平衡二叉树的面试朋友们，对它一定有印象，官提个啥今天阿粉就与大家一起深入了解一下AVL树!
一、到的到底摘要
在上篇文章，面试我们详细的官提个啥介绍了二叉树的算法以及代码实践，我们知道不同的到的到底二叉树形态结构，对查询效率也会有很大的面试影响，尤其是官提个啥当树的形态结构变成一个链条结构的时候，查询最后一个元素的到的到底效率极底，如何解决这个问题呢?面试
关键在于如何最大限度的减小树的深度，从而提高查询效率，官提个啥正是到的到底基于这一点，平衡二叉查找树出现了!
平衡二叉查找树，面试算法由Adelson-Velskii和 Landis两位大神发明，官提个啥同时也俗称AVL 树，到的到底来自两位大神的姓名缩写，免费源码下载特性如下：
它的左子树和右子树都是平衡二叉树; 且它的左子树和右子树的深度之差的绝对值(平衡因子 ) 不超过1;简单的说，就是为了保证平衡，当前节点的左子树、右子树的高度差不超过1!
废话也不多说了，直奔主题，算法思路如下!
二、算法思路
平衡二叉查找树的查找思路，与二叉树是一样，每次查询的时候对半分，只查询一部分，以达到提供效率的目的，插入、删除也一样，最大的不同点：每次插入或者删除之后，需要计算节点高度，然后按需进行调整!
如何调整呢?主要方法有：左旋转、右旋转!
下面我们分别来分析一下插入、删除的源码库场景调整。
2.1、插入场景
我们来分析一下插入的场景，如下：
场景一
当我们在40的左边或者右边插入的时候，也就是50的左边，只需绕80进行右旋转，即可达到树高度差不超过1!
场景二
当我们在60的左边或者右边插入的时候，也就是50的右边，需要进行两次旋转，先会绕50左旋转一次，再绕80右旋转一次，即可达到树高度差不超过1!
场景三
当我们在120的左边或者右边插入的时候，也就是90的右边，只需绕80进行左旋转，即可达到树高度差不超过1!
场景四
当我们在85的左边或者右边插入的时候，也就是90的左边，IT技术网需要进行两次旋转，先会绕90右旋转一次，再绕80左旋转一次，即可达到树高度差不超过1!
总结
对于插入这种操作，总共其实只有这四种类型的插入，即：单次左旋转、单次右旋转、左旋转-右旋转、右旋转-左旋转，总结如下：
当插入节点位于需要旋转节点的左节点的左子树时，只需右旋转; 当插入节点位于需要旋转节点的左节点的右子树时，需要左旋转-右旋转; 当插入节点位于需要旋转节点的右节点的右子树时，只需左旋转; 当插入节点位于需要旋转节点的右节点的左子树时，需要右旋转-左旋转;2.2、删除场景
接下来，我们分析一下删除场景!
其实，删除场景跟二叉树的删除思路是一样的，不同的是需要调整，删除的节点所在树，需要层层判断节点的高度差是否大于1，如果大于1，就进行左旋转或者右旋转!
场景一
当删除的节点，只有左子树时，直接将左子树转移到上层即可!
场景二
当删除的节点，只有右子树时，直接将右子树转移到上层即可!
场景三
当删除的节点，有左、右子树时，因为当前节点的左子树的最末端的右子树或者当前节点的右子树的最末端的左子树，最接近当前节点，找到其中任意一个，然后将其内容替换并移除最末端节点，即可实现删除!
总结
第三种场景稍微复杂了一些，但基本都是这么一个套路，与二叉树不同的是，删除之后需要判断树高，对超过1的进行调整，类似上面插入的左旋转、右旋转操作!
三、代码实践
接下来，我们从代码层面来定义一下树的实体结构，如下：
1public class AVLNode<E extends Comparable<E>> { 2 3 /**节点关键字*/ 4 E key; 5 6 /**当前节点树高*/ 7 int height; 8 9 /**当前节点的左子节点*/ 10 AVLNode<E> lChild = null; 11 12 /**当前节点的右子节点*/ 13 AVLNode<E> rChild = null; 14 15 public AVLNode(E key) { 16 this.key = key; 17 } 18 19 @Override 20 public String toString() { 21 return "AVLNode{" + 22 "key=" + key + 23 ", height=" + height + 24 ", lChild=" + lChild + 25 ", rChild=" + rChild + 26 }; 27 } 28}我们创建一个算法类AVLSolution，完整实现如下：
1public class AVLSolution<E extends Comparable<E>> { 2 3 /**定义根节点*/ 4 public AVLNode<E> root = null; 5 6 /** 7 * 插入 8 * @param key 9 */ 10 public void insert(E key){ 11 System.out.println("插入[" + key + "]:"); 12 root = insertAVL(key,root); 13 } 14 15 private AVLNode insertAVL(E key, AVLNode<E> node){ 16 if(node == null){ 17 return new AVLNode<E>(key); 18 } 19 //左子树搜索 20 if(key.compareTo(node.key) < 0){ 21 //当前节点左子树不为空,继续递归向下搜索 22 node.lChild = insertAVL(key,node.lChild); 23 //出现不平衡，只会是左子树比右子树高，大于1的时候，就进行调整 24 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){ 25 if(key.compareTo(node.lChild.key) < 0){ 26 //如果插入的节点位于当前节点的左节点的左子树，进行单次右旋转 27 node = rotateRight(node); 28 }else{ 29 //如果插入的节点位于当前节点的左节点的右子树，先左旋转再右旋转 30 node = rotateLeftRight(node); 31 } 32 } 33 }else if(key.compareTo(node.key) > 0){ 34 //当前节点右子树不为空,继续递归向下搜索 35 node.rChild = insertAVL(key,node.rChild); 36 //出现不平衡，只会是右子树比左子树高，大于1的时候，就进行调整 37 if(getHeight(node.rChild) - getHeight(node.lChild) == 2){ 38 if(key.compareTo(node.rChild.key) < 0){ 39 //如果插入的节点位于当前节点的右节点的左子树，先右旋转再左旋转 40 node = rotateRightLeft(node); 41 }else{ 42 //如果插入的节点位于当前节点的右节点的右子树，进行单次左旋转 43 node = rotateLeft(node); 44 } 45 } 46 } else{ 47 //key已经存在，直接返回 48 } 49 //因为节点插入，树高发生变化，更新节点高度 50 node.height = updateHeight(node); 51 return node; 52 } 53 54 /** 55 * 删除 56 * @param key 57 */ 58 public void delete(E key){ 59 root = deleteAVL(key,root); 60 } 61 62 private AVLNode deleteAVL(E key, AVLNode<E> node){ 63 if(node == null){ 64 return null; 65 } 66 if(key.compareTo(node.key) < 0){ 67 //左子树查找 68 node.lChild = deleteAVL(key,node.lChild); 69 //可能会出现，右子树比左子树高2 70 if (getHeight(node.rChild) - getHeight(node.lChild) == 2){ 71 node = rotateLeft(node); 72 } 73 } else if(key.compareTo(node.key) > 0){ 74 //右子树查找 75 node.rChild = deleteAVL(key, node.rChild); 76 //可能会出现，左子树比右子树高2 77 if (getHeight(node.lChild) - getHeight(node.rChild) == 2){ 78 node = rotateRight(node); 79 } 80 }else{ 81 //找到目标元素，删除分三种情况 82 //1.当前节点没有左子树，直接返回当前节点右子树 83 //2.当前节点没有右子树，直接返回当前节点右子树 84 //3.当前节点有左子树、右子树的时候，寻找当前节点的右子树的最末端的左子树，进行替换和移除 85 if(node.lChild == null){ 86 return node.rChild; 87 } 88 if(node.rChild == null){ 89 return node.lChild; 90 } 91 //找到当前节点的右子树的最末端的左子树，也就是右子树最小节点 92 AVLNode<E> minLChild = searchDeleteMin(node.rChild); 93 //删除最小节点，如果高度变化，进行调整 94 minLChild.rChild = deleteMin(node.rChild); 95 minLChild.lChild = node.lChild;//将当前节点的左子树转移到最小节点上 96 97 node = minLChild;//覆盖当前节点 98 //因为是右子树发生高度变低，因此可能需要调整 99 if(getHeight(node.lChild) - getHeight(node.rChild) == 2){ 100 node = rotateRight(node); 101 } 102 } 103 node.height = updateHeight(node); 104 return node; 105 } 106 107 /** 108 * 搜索 109 * @param key 110 * @return 111 */ 112 public AVLNode<E> search(E key){ 113 return searchAVL(key, root); 114 } 115 116 private AVLNode<E> searchAVL(E key, AVLNode<E> node){ 117 if(node == null){ 118 return null; 119 } 120 //左子树搜索 121 if(key.compareTo(node.key) < 0){ 122 return searchAVL(key, node.lChild); 123 }else if(key.compareTo(node.key) > 0){ 124 return searchAVL(key, node.rChild); 125 } else{ 126 //key已经存在，直接返回 127 return node; 128 } 129 } 130 131 /** 132 * 查找需要删除的元素 133 * @param node 134 * @return 135 */ 136 private AVLNode<E> searchDeleteMin(AVLNode<E> node){ 137 if (node == null){ 138 return null; 139 } 140 while (node.lChild != null){ 141 node = node.lChild; 142 } 143 return node; 144 } 145 146 /** 147 * 删除元素 148 * @param node 149 * @return 150 */ 151 private AVLNode<E> deleteMin(AVLNode<E> node){ 152 if(node == null){ 153 return null; 154 } 155 if (node.lChild == null){ 156 return node.rChild; 157 } 158 //移除最小节点 159 node.lChild = deleteMin(node.lChild); 160 //此时移除的是左节点，判断是否平衡高度被破坏 161 if(getHeight(node.rChild) - getHeight(node.lChild) == 2){ 162 //进行调整 163 node = rotateLeft(node); 164 } 165 return node; 166 167 } 168 169 /** 170 * 单次左旋转 171 * @param node 172 * @return 173 */ 174 private AVLNode<E> rotateLeft(AVLNode<E> node){ 175 System.out.println("节点：" + node.key + "，单次左旋转"); 176 AVLNode<E> x = node.rChild;//获取旋转节点的右节点 177 node.rChild = x.lChild;//将旋转节点的右节点的左节点转移，作为旋转节点的右子树 178 x.lChild = node;//将旋转节点作为旋转节点的右子树的左子树 179 180 //更新调整节点高度(先调整旋转节点node) 181 node.height = updateHeight(node); 182 x.height = updateHeight(x); 183 return x; 184 } 185 186 /** 187 * 单次右旋转 188 * @return 189 */ 190 private AVLNode<E> rotateRight(AVLNode<E> node){ 191 System.out.println("节点：" + node.key + "，单次右旋转"); 192 AVLNode<E> x = node.lChild;//获取旋转节点的左节点 193 node.lChild = x.rChild;//将旋转节点的左节点的右节点转移，作为旋转节点的左子树 194 x.rChild = node;//将旋转节点作为旋转节点的左子树的右子树 195 196 //更新调整节点高度(先调整旋转节点node) 197 node.height = updateHeight(node); 198 x.height = updateHeight(x); 199 return x; 200 } 201 202 /** 203 * 左旋转-右旋转 204 * @param node 205 * @return 206 */ 207 private AVLNode<E> rotateLeftRight(AVLNode<E> node){ 208 System.out.println("节点：" + node.key + "，左旋转-右旋转"); 209 //先对当前节点的左节点进行左旋转 210 node.lChild = rotateLeft(node.lChild); 211 //再对当前节点进行右旋转 212 return rotateRight(node); 213 } 214 215 /** 216 * 右旋转-左旋转 217 * @param node 218 * @return 219 */ 220 private AVLNode<E> rotateRightLeft(AVLNode<E> node){ 221 System.out.println("节点：" + node.key + "，右旋转-左旋转"); 222 //先对当前节点的右节点进行右旋转 223 node.rChild = rotateRight(node.rChild); 224 return rotateLeft(node); 225 226 } 227 228 /** 229 * 获取节点高度，如果为空，等于-1 230 * @param node 231 * @return 232 */ 233 private int getHeight(AVLNode<E> node){ 234 return node != null ? node.height: -1; 235 } 236 237 /** 238 * 更新节点高度 239 * @param node 240 * @return 241 */ 242 private int updateHeight(AVLNode<E> node){ 243 //比较当前节点左子树、右子树高度，获取节点高度 244 return Math.max(getHeight(node.lChild), getHeight(node.rChild)) + 1; 245 } 246 247 /** 248 * 前序遍历 249 * @param node 250 */ 251 public void frontTreeIterator(AVLNode<E> node){ 252 if(node != null){ 253 System.out.println("key:" + node.key); 254 frontTreeIterator(node.lChild);//遍历当前节点左子树 255 frontTreeIterator(node.rChild);//遍历当前节点右子树 256 } 257 } 258 259 /** 260 * 中序遍历 261 * @param node 262 */ 263 public void middleTreeIterator(AVLNode<E> node){ 264 if(node != null){ 265 middleTreeIterator(node.lChild);//遍历当前节点左子树 266 System.out.println("key:" + node.key); 267 middleTreeIterator(node.rChild);//遍历当前节点右子树 268 } 269 } 270 271 /** 272 * 后序遍历 273 * @param node 274 */ 275 public void backTreeIterator(AVLNode<E> node){ 276 if(node != null){ 277 backTreeIterator(node.lChild);//遍历当前节点左子树 278 backTreeIterator(node.rChild);//遍历当前节点右子树 279 System.out.println("key:" + node.key); 280 } 281 } 282 283}测试代码，如下：
1public class AVLClient { 2 3 public static void main(String[] args) { 4 //创建一个Integer型的数据结构 5 AVLSolution<Integer> avlTree = new AVLSolution<Integer>(); 6 7 //插入节点 8 System.out.println("========插入元素========"); 9 avlTree.insert(new Integer(100)); 10 avlTree.insert(new Integer(85)); 11 avlTree.insert(new Integer(120)); 12 avlTree.insert(new Integer(60)); 13 avlTree.insert(new Integer(90)); 14 avlTree.insert(new Integer(80)); 15 avlTree.insert(new Integer(130)); 16 System.out.println("========中序遍历元素========"); 17 18 //中序遍历 19 avlTree.middleTreeIterator(avlTree.root); 20 System.out.println("========查找key为100的元素========"); 21 22 //查询节点 23 AVLNode<Integer> searchResult = avlTree.search(120); 24 System.out.println("查找结果：" + searchResult); 25 System.out.println("========删除key为90的元素========"); 26 27 //删除节点 28 avlTree.delete(90); 29 System.out.println("========再次中序遍历元素========"); 30 31 //中序遍历 32 avlTree.middleTreeIterator(avlTree.root); 33 } 34}输出结果如下：
四、总结
平衡二叉树查找树，俗称AVL树，在查询的时候，操作与普通二叉查找树上的查找操作相同;插入的时候，每一次插入结点操作最多只需要单旋转或双旋转;如果是动态删除，删除之后必须检查从删除结点开始到根结点路径上的所有结点的平衡因子，也就是高度差，如果超过1就需要调整，最多可能需要O(logN)次旋转。
整体上来说，平衡二叉树优于普通二叉查找树!
五、参考
[1] 简书 - nicktming - 二叉平衡树: https://www.jianshu.com/p/22c00b3731f5
[2] iteye - Heart.X.Raid - 平衡二叉查找树 [AVL]: https://www.iteye.com/blog/hxraid-609949
源码库源码下载服务器租用企商汇香港云服务器IT资讯网IT技术网亿华云益华科技智能时代亿华智造益华科技亿华科技亿华互联IT资讯网益强资讯优选云站无忧多维IT资讯创站工坊益强前沿资讯益强智未来思维库亿华灵动益强智囊团运维纵横益强IT技术网益华IT技术论坛科技前瞻编程之道益强科技益强科技汇智坊云智核码力社全栈开发极客编程极客码头亿华云计算益强编程舍益强编程堂技术快报码上建站益华科技
- Copyright © 2025 Powered by 面试官提到的 AVL 树，到底是个啥,创站工坊 滇ICP备2023006006号-44sitemap