首页 > 代码库 > AVL 树的插入、删除、旋转归纳
AVL 树的插入、删除、旋转归纳
参考链接：
http://blog.csdn.net/gabriel1026/article/details/6311339
之前简单了解过 AVL 树，知道概念但一直没动手实践过。Now
AVL 树是二叉搜索树的一种。二叉搜索树的规则就是：每个节点的 left child 都比自己小，right child 都比自己大。而 AVL 的在此之上又加了一个规则：每个节点的 left 深度与 right 深度只差<=1，这样就能充分利用 二叉树的结构，避免出现一个分支走到黑，导致搜索效率变低。如下图：
这种树结构，搜索起来完全没有体现出二叉搜索树的优势
所以同样多的元素，搜索树的深度越低，就会越快的定位到搜索点。
AVL 树为了保持树的平衡，每次插入、删除都会检查 每个受影响的节点，深度差是否 < 1。最难的部分就是如果树失衡，如何调整节点。插入的处理流程大致如下：
给定一个 value，一路比较直到插入到某个位置。然后查找哪些节点因此而失衡，针对第一个失衡的节点进行旋转。
下面是我从另一个博客上找来的图（http://blog.csdn.net/gabriel1026/article/details/6311339），介绍了四种失衡的情况，以及调整方式：
注：图中红色的小块 表示新插入的元素，A 点表示从插入点向上，发现的第一个失衡的点。
AVL树的旋转一共有四种情形，注意所有旋转情况都是围绕着使得二叉树不平衡的第一个节点展开的。
1：
图中在 Bl 下新插入一个子节点，导致 A 左侧深度为 3，右侧为 1，失衡。右旋。
2：
3：
4：
不知道大家看明白了调整的规则吗？
如果您看明白了，你真是大牛！！！
没看图之前我大致明白了四种调整规则，看了后两幅图片之后，彻底迷糊了。完全不知道如何用程序来表示四种规则，也不知道怎么从一棵树中提取到这四个特征。。。后两张图折磨了我一天多，才发现：后两张图应该是存在逻辑错误的。。。
AVL 树每次插入之前，以及插入之后，都应该是平衡的。而 图3 和图4，插入之前就不平衡：拿图三来说：插入之前，A 的 left 深度为3，right 深度为 1，本身就有问题
虽然上面的图有问题，但是介绍的思路是非常正确的，只是检查到底符合 LL、RR、LR、RL 中哪个特征时，被带跑偏了。
所以明白了这四种调整方式后，下一步就是用程序的思维，检查何时用哪种规则了。这一点我认为网上的博客介绍的也不太详细，我这理解力一般的人，看过教程后，实现起来依旧是一团麻。下面是我用到的插入流程：
1：拿到新节点 newNode，根据左小右大的二叉搜索树规则，一路定位到一个具体的节点 currNode，把 newNode 当成 currNode 的 child 插入到树中。（不用记录 newNode 是 currNode 的 left 还是 right ）
2：检查 currNode 是否失衡，如果没有失衡，就检查 currNode 的 parent，不失衡就在检查 parent 的 parent….. 这样直到拿到一个失衡节点（如果直到根节点依旧平衡，那当前树就不用做任何调整），把失衡点当成 currNode
3：关键点的平衡来了：
如果 Depth(currNode.left) - Depth(currNode.right) = 2：说明左侧深度大于右侧深度，可能是 LL、LR 中的一种：此时检查 newNode 和 currNode、currNode.left 的大小关系
1）如果 newNode 比 currNode 小，并且 newNode 比 currNode.left 小，此时符合 LL：对 currNode 右旋；
2）如果 newNode 比 currNode 小，但是 newNode 比 currNode.left 大，此时符合 LR：先对 currNode.left 左旋，然后对 currNode 右旋；
如果 Depth(currNode.right) - Depth(currNode.left) = 2：说明右侧深度大于左侧深度，可能是 RR、RL 中的一种：此时检查 newNode 和 currNode、currNode.right 的大小关系：
1）如果 newNode 比 currNode 大，并且 newNode 比 currNode.right 大，符合 RR，对 currNode 左旋；
2）如果 newNode 比 currNode 大，并且 newNode 比 currNode.right 小，符合 RL：先对 currNode.right 右旋，然后对 currNode 左旋；
插入、调整结束。
中间有几个容易混的地方。这样叙述起来，用程序实现就很方便了。剩下的就是 左旋、右旋的函数实现，这两个函数需要特别小心，每个节点的 parent、left、right 都要很小心的处理。基本上包含四个函数：
insert 负责执行 1
balance 负责执行 2、3、4
leftRotate、rightRotate 函数用来实现旋转。
代码我在最后统一贴出来。
插入搞定了，还有删除操作：删除的流程如下：
1：拿到要删除的数字 value，从根节点开始比对，知道找到一个要删除的节点：currNode （没找到正好不用删了 →_→）
2：从左子树中找到一个最大值（左子树中的值都比 currNode 小）：targetNode（如果左子树为空，那就直接把 right 节点上位；如果 right 也是空的，那就直接删掉 currNode 就好了）
3：把 targetNode 放到 currNode 的位置上：因为每个 节点都有 parent、left、right 三个关联点，要仔细处理（错误了好几次才正确→_→）
4：和 插入类似，从 targetNode 开始一路向上，找到第一个失衡点。此时只有 LL 和 RR 两种失衡情况，判断起来相对容易些
AVL 树最基本的插入和删除就是这样了。插入删除过程中，具体为什么旋转、为什么使用这种规则，是否覆盖到了所有的特例等问题，都是有规律可以归纳的。对这些规律我还比较模糊，知其然不知其所以然。。。树是一个很神奇的数据结构，诸多奇思妙想都能用树结构来实现，还要多想想树的规律。
JS 代码如下：
1 /** 2 * Created by CG on 16/11/20. 3 */ 4 5 6 7 var TreeNode = function(){ 8 this.parent = null; 9 this.left = null; 10 this.right = null; 11 12 this.value = http://www.mamicode.com/null; 13 }; 14 15 16 var AVLTree = { 17 18 insert : function (value) { 19 this.log("新加节点:new add: " + value); 20 if(this._tree == null){ 21 var node = new TreeNode(); 22 node.value =http://www.mamicode.com/ value; 23 this._tree = node; 24 return; 25 } 26 27 var newNode = new TreeNode(); 28 newNode.value =http://www.mamicode.com/ value; 29 30 var currNode = this._tree; 31 while(true){ 32 if(currNode == null){ 33 this.log(" ======== currNode: null"); 34 return; 35 } 36 37 //走向左子树 38 if(value <= currNode.value){ 39 this.log(" to left: value: " + value + " currValue: " + currNode.value); 40 if(currNode.left){ 41 currNode = currNode.left; 42 continue; 43 } 44 else { 45 newNode.parent = currNode; 46 currNode.left = newNode; 47 this.balanceTree(currNode, newNode); 48 break; 49 } 50 } 51 //走向右子树 52 else { 53 this.log(" to right: value: " + value + " currValue: " + currNode.value); 54 if(currNode.right){ 55 currNode = currNode.right; 56 continue; 57 } 58 else { 59 newNode.parent = currNode; 60 currNode.right = newNode; 61 this.balanceTree(currNode, newNode); 62 break; 63 } 64 } 65 } 66 }, 67 balanceTree : function (currNode, newNode) { 68 if(!currNode){ 69 return; 70 } 71 72 this.printTreeByLevel(); 73 while(currNode){ 74 this.log("---------===========--- check if adjust: " + currNode.value); 75 if(currNode.parent){ 76 this.log(" parent: " + currNode.parent.value); 77 } 78 var leftDepth = this.calcuDepth(currNode.left); 79 var rightDepth = this.calcuDepth(currNode.right); 80 this.log("leftDepth: " + leftDepth + " rightDepth: " + rightDepth); 81 if(leftDepth - rightDepth == 2){ 82 if(newNode == null){ 83 this.rightRotate(currNode); 84 } 85 else if(newNode.value < currNode.value && newNode.value < currNode.left.value){ 86 this.log("LL"); 87 this.rightRotate(currNode); 88 } 89 else if(newNode.value < currNode.value && newNode.value > currNode.left.value){ 90 this.log("LR"); 91 this.leftRotate(currNode.left); 92 this.rightRotate(currNode); 93 } 94 } 95 else if(rightDepth - leftDepth == 2){ 96 if(newNode == null){ 97 this.leftRotate(currNode); 98 } 99 else if(newNode.value > currNode.value && newNode.value > currNode.right.value){100 this.log("RR");101 this.leftRotate(currNode);102 }103 else if(newNode.value > currNode.value && newNode.value < currNode.right.value){104 this.log("RL");105 this.rightRotate(currNode.right);106 this.leftRotate(currNode);107 }108 }109 110 currNode = currNode.parent;111 this.printTreeByLevel();112 }113 },114 leftRotate : function (currNode) {115 this.log("leftRotate: " + currNode.value);116 var oldRight = currNode.right;117 118 //如果当前节点就是根节点，更新外界引用的根节点119 if(currNode == this._tree){120 this._tree = oldRight;121 }122 else {123 //更新变动前的 currNode 的 parent 的指向124 if(currNode.parent.left == currNode){125 currNode.parent.left = oldRight;126 }127 else if(currNode.parent.right == currNode){128 currNode.parent.right = oldRight;129 }130 }131 132 //更新 curr 和 oldRight 的 parent133 oldRight.parent = currNode.parent;134 135 //更新 curr 和 oldRight 的 child136 currNode.right = oldRight.left;137 if(oldRight.left){138 oldRight.left.parent = currNode;139 }140 141 oldRight.left = currNode;142 currNode.parent = oldRight;143 144 this._tree.parent = null;145 return oldRight;146 },147 rightRotate : function (currNode) {148 this.log("rightRotate: " + currNode.value);149 var oldLeft = currNode.left;150 151 //如果当前节点就是根节点，更新外界引用的根节点152 if(currNode == this._tree){153 this._tree = oldLeft;154 }155 else {156 //更新变动前的 currNode 的 parent 的指向157 if(currNode.parent.left == currNode){158 currNode.parent.left = oldLeft;159 }160 else if(currNode.parent.right == currNode){161 currNode.parent.right = oldLeft;162 }163 }164 165 //更新 curr 和 oldLeft 的 parent166 oldLeft.parent = currNode.parent;167 168 //更新 curr 和 oldLeft 的 child169 currNode.left = oldLeft.right;170 if(oldLeft.right){171 oldLeft.right.parent = currNode;172 }173 174 oldLeft.right = currNode;175 currNode.parent = oldLeft;176 177 this._tree.parent = null;178 return oldLeft;179 },180 181 /**182 * 计算左右节点的深度。叶子节点的深度都是 1，依次向上加 1183 * @param treeNode184 * @returns {number}185 */186 calcuDepth : function (treeNode) {187 if(!treeNode){188 return 0;189 }190 if(treeNode.left == null && treeNode.right == null){191 return 1;192 }193 return 1 + Math.max(this.calcuDepth(treeNode.left), this.calcuDepth(treeNode.right));194 },195 196 /**197 * 从树中删除一个节点198 * @param value199 */200 remove : function (value) {201 this.log(" ===== 将要删除元素：" + value);202 if(!value){203 return;204 }205 206 //定位到节点207 var currNode = this._tree;208 while(currNode){209 if(currNode.value =http://www.mamicode.com/= value){210 break;211 }212 currNode = value > currNode.value ? currNode.right : currNode.left;213 }214 if(currNode.value != value){215 this.log("没找到啊");216 return;217 }218 219 var targetNode = null;220 //删除该节点221 if(currNode.left){222 //有左子树，找到其中最大值来替代空位223 targetNode = this.findMaxNode(currNode.left);224 this.log(" == currNode.left: " + targetNode.value);225 226 //更新 target 父节点的 child 指向227 if(targetNode.parent != currNode){228 var newChild = targetNode.left ? targetNode.left : targetNode.right;229 if(targetNode.parent.left == targetNode){230 targetNode.parent.left = newChild;231 }232 else {233 targetNode.parent.right = newChild;234 }235 }236 //更新 target 的 parent 指向237 targetNode.parent = currNode.parent;238 239 // 更新 target 的 right 指向240 targetNode.right = currNode.right;241 if(currNode.right){242 currNode.right.parent = targetNode;243 }244 // 更新 target 的 left 指向 、、一定要注意避免自身死循环245 if(currNode.left != targetNode){246 targetNode.left = currNode.left;247 currNode.left.parent = targetNode;248 }249 }250 //没有左子树，但是有右子树，直接把右子树提上去就好了251 else if(currNode.right){252 targetNode = currNode.right;253 targetNode.parent = currNode.parent;254 this.log(" == currNode.right: " + targetNode.value);255 }256 //如果 curr 是叶子节点，只要更新 curr 的 parent 就可以了，没有额外处理257 258 //更新 curr 父节点的 child 指向259 if(currNode.parent && currNode.parent.left == currNode){260 currNode.parent.left = targetNode;261 }262 else if(currNode.parent && currNode.parent.right == currNode){263 currNode.parent.right = targetNode;264 }265 else {266 this._tree = targetNode; //说明是 根节点267 }268 269 this.log(" +++++++++++++ ");270 this.printTreeByLevel();271 this.balanceTree(targetNode == null ? currNode.parent : targetNode);272 this.log(" +++++++++++++ ");273 },274 275 276 findMaxNode : function(treeNode){277 while(treeNode){278 if(treeNode.right){279 treeNode = treeNode.right;280 }281 else {282 return treeNode;283 }284 }285 return treeNode;286 },287 288 289 290 log : function (str) {291 console.log(str);292 },293 /**294 * 按照层级打印一棵树的各层节点名字295 **/296 printTreeByLevel : function () {297 this.log("-----------------------");298 if(!this._tree){299 this.log(" === empty ===");300 return;301 }302 var nodeList = [];303 nodeList.push(this._tree);304 while(nodeList.length > 0){305 var len = nodeList.length;306 var valuehttp://www.mamicode.com/= "";307 for(var i=0; i<len; ++i){308 var currNode = nodeList[i];309 value += currNode.value + " ";310 if(currNode.left){311 nodeList.push(currNode.left);312 }313 if(currNode.right){314 nodeList.push(currNode.right);315 }316 }317 this.log(value);318 319 nodeList = nodeList.slice(len);320 }321 },322 };323 324 325 AVLTree.printTreeByLevel();326 AVLTree.log("====================================================================================================");327 var list = [3,7,9,23,45, 1,5,14,25,24, 13,11, 26];328 for(var index in list){329 AVLTree.insert(list[index]);330 }331 AVLTree.log("====================================================================================================");332 AVLTree.printTreeByLevel();333 // AVLTree.remove(1);334 // AVLTree.remove(25);335 // AVLTree.printTreeByLevel();
AVL 树的插入、删除、旋转归纳
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。