AVL树从平衡因子到四种旋转的完整实现文章目录AVL树从平衡因子到四种旋转的完整实现1 AVL树的基本概念AVL树的定义2 为什么要求高度差不超过13 平衡因子 Balance Factor4 AVL树的结点结构5 AVL树的整体结构6 AVL树的插入7 AVL树插入的基本过程8 平衡因子的更新规则插入到左边插入到右边9 更新平衡因子的三种情况9.1 更新后变成09.2 更新后变成1或-19.3 更新后变成2或-210 AVL插入代码11 AVL树的旋转原则一原则二12 右单旋13 右单旋的核心14 右单旋代码15 右旋过程中为什么需要处理subLR16 左单旋17 左单旋代码18 左右双旋19 左右双旋的结构变化20 左右双旋为什么需要特殊处理平衡因子21 左右双旋代码22 右左双旋23 右左双旋代码24 四种旋转如何判断25 AVL树查找26 AVL树的平衡检测27 计算树的高度28 判断是否为AVL树29 AVL树平衡检测代码30 AVL树的测试31 大规模数据测试32 AVL树的核心代码逻辑1 AVL树的基本概念AVL树是一种自平衡二叉搜索树普通二叉搜索树在插入数据后如果数据本身具有某种顺序例如依次插入1 2 3 4 5很容易退化成类似链表的结构此时搜索效率会从理想情况下的O(logN)退化到O(N)AVL树通过控制树的高度使二叉搜索树始终保持较好的平衡状态从而保证查找等操作的效率AVL树的定义一棵树满足下面几个条件就可以认为它是一棵 AVL 树1 这棵树是一棵空树或者是一棵二叉搜索树2 左右子树本身也必须是 AVL 树3 任意结点的左右子树高度差的绝对值不能超过1也就是abs(左子树高度-右子树高度)1因此 AVL 树本质上是一棵高度平衡的二叉搜索树2 为什么要求高度差不超过1很多人第一次接触 AVL 树时会产生一个问题既然是平衡树为什么不直接要求左右子树高度完全相等呢也就是为什么不要求左子树高度右子树高度原因是这种要求过于严格有些结点数量下根本无法做到例如一棵树只有两个结点1 \ 2此时左右子树高度必然存在差异因此 AVL 树采用的是更加合理的要求左右子树高度差 1这样既可以保证树不会严重倾斜又不会对树的结构要求过于苛刻3 平衡因子 Balance Factor为了方便判断 AVL 树是否平衡给每一个结点增加一个平衡因子_bf平衡因子的定义是平衡因子右子树高度-左子树高度因此_bf rightHeight - leftHeight对于正常的 AVL 树来说每个结点的平衡因子只能是-1 0 1如果出现2说明右边太高如果出现-2说明左边太高例如10 / 5左边高度比右边高1所以_bf 0 - 1 -1再例如10 \ 15右边高度比左边高1所以_bf 1 - 0 1如果变成10 / 5 / 3那么左子树高度 2 右子树高度 0 _bf 0 - 2 -2此时就出现了不平衡需要进行旋转4 AVL树的结点结构AVL树的结点不仅需要保存左右孩子还需要保存父亲结点以及平衡因子templateclassK,classVstructAVLTreeNode{pairK,V_kv;AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;int_bf;AVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};各成员的作用成员作用_kv保存键值对_left指向左孩子_right指向右孩子_parent指向父亲结点_bf保存平衡因子这里的_parent非常重要因为插入一个新结点之后需要从新结点的父亲开始一路向上更新平衡因子如果没有_parent就无法直接从当前结点找到上一层结点5 AVL树的整体结构templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;private:Node*_rootnullptr;};_root保存整棵 AVL 树的根结点6 AVL树的插入AVL树插入一个结点的过程可以分成几个阶段按照二叉搜索树规则插入 ↓ 更新祖先结点的平衡因子 ↓ 判断是否出现不平衡 ↓ 如果平衡继续向上更新 ↓ 如果不平衡进行旋转 ↓ 旋转完成后结束最关键的一点是AVL树的插入首先仍然遵循二叉搜索树的插入规则AVL树并没有改变二叉搜索树的基本性质7 AVL树插入的基本过程假设现在插入一个新结点首先按照普通二叉搜索树的方法寻找插入位置如果 key 当前结点 向左走 如果 key 当前结点 向右走 如果 key 当前结点 插入失败新结点插入以后需要开始向上更新平衡因子更新路径为新结点 ↑ parent ↑ parent ↑ ... ↑ root最坏情况下需要一直更新到根结点但并不是每次都需要更新到根有些情况下更新到中间位置就可以停止8 平衡因子的更新规则AVL树中平衡因子的定义是_bf右子树高度-左子树高度插入一个新结点后新结点所在的子树高度可能增加因此父亲结点的平衡因子可能发生变化插入到左边如果新结点插入到parent的左子树parent-_bf--;因为左子树高度增加了插入到右边如果新结点插入到parent的右子树parent-_bf;因为右子树高度增加了9 更新平衡因子的三种情况这是 AVL 插入中最重要的部分之一更新父亲结点的平衡因子以后主要有三种情况0 1 或 -1 2 或 -29.1 更新后变成0例如-1 → 0或者1 → 0说明原来两边高度不一样新结点插入到了原来较矮的一边插入以后两边重新变得一样高关键点在于当前子树的高度没有增加因此不会继续影响父亲结点所以可以直接结束更新if(parent-_bf0){break;}9.2 更新后变成1或-1例如0 → 1或者0 → -1说明原来左右子树高度相同插入以后其中一边变高了当前结点仍然满足 AVL 的平衡要求但是当前子树的高度增加了1因此还可能影响父亲结点所以需要继续向上更新curparent;parentparent-_parent;9.3 更新后变成2或-2例如1 → 2或者-1 → -2此时说明当前结点已经失去平衡必须通过旋转恢复平衡elseif(parent-_bf2||parent-_bf-2){// 不平衡了旋转处理break;}旋转的两个目标1 恢复平衡 2 降低当前子树的高度当旋转完成后当前子树的高度恢复到插入之前的状态因此不会继续影响上一层所以插入操作可以结束10 AVL插入代码核心代码结构如下boolInsert(constpairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(parent-_kv.firstkv.first){parent-_rightcur;}else{parent-_leftcur;}cur-_parentparent;while(parent){if(curparent-_left)parent-_bf--;elseparent-_bf;if(parent-_bf0){break;}elseif(parent-_bf1||parent-_bf-1){curparent;parentparent-_parent;}elseif(parent-_bf2||parent-_bf-2){// 不平衡break;}else{assert(false);}}returntrue;}这里需要特别理解一个问题为什么更新平衡因子时要同时维护cur parent因为当前需要判断cur到底是parent的左孩子还是parent的右孩子然后决定parent-_bf--;还是parent-_bf;更新完成以后再把当前结点整体向上移动curparent;parentparent-_parent;这样就可以继续处理上一层11 AVL树的旋转当某个结点的平衡因子变成2或者-2说明树已经不平衡此时需要旋转AVL树一共有四种旋转情况右单旋 左单旋 左右双旋 右左双旋旋转必须满足两个原则原则一旋转以后仍然必须满足二叉搜索树的大小关系原则二旋转以后恢复平衡并尽可能将树的高度降低到插入之前的高度12 右单旋右单旋主要解决左边过高并且新增结点位于左子树的左侧典型结构parent / subL / ...例如10 / 5 / 3此时10的平衡因子 -2需要进行右旋旋转之后5 / \ 3 10原来的5成为新的根原来的10成为5的右孩子13 右单旋的核心假设结构为parent / subL / \ a b其中a subL b parent右旋之后subL / \ a parent / b为什么b可以成为parent的左子树因为满足subL b parent所以不会破坏二叉搜索树的性质14 右单旋代码voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-_leftsubLR;if(subLR)subLR-_parentparent;Node*parentParentparent-_parent;subL-_rightparent;parent-_parentsubL;if(parentParentnullptr){_rootsubL;subL-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}parent-_bfsubL-_bf0;}右旋最容易出错的地方并不是旋转方向而是指针关系的修改需要同时处理孩子指针 父亲指针 _root 上一层结点的孩子指针15 右旋过程中为什么需要处理subLR假设parent / subL \ subLR右旋后subL \ parent / subLR因此原来的subL-_right必须变成parent而原来的subLR必须移动到parent-_left所以代码中有Node*subLRsubL-_right;parent-_leftsubLR;if(subLR)subLR-_parentparent;这一步非常关键16 左单旋左单旋与右单旋完全对称它主要解决右边过高例如10 \ 15 \ 20此时10的平衡因子 2需要左旋旋转以后15 / \ 10 2017 左单旋代码voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}parent-_bfsubR-_bf0;}左旋和右旋实际上就是镜像关系右旋左孩子上升 原根下降到右边左旋右孩子上升 原根下降到左边18 左右双旋有些情况下单旋无法解决问题例如10 / 5 \ 8此时10左边高但是新增结点并不是位于5的左边而是位于5的右边因此直接对10进行右旋无法彻底解决问题这就是左右双旋处理过程先以5为旋转点进行左旋 ↓ 再以10为旋转点进行右旋也就是RotateL(parent-_left);RotateR(parent);19 左右双旋的结构变化初始10 / 5 \ 8第一次左旋10 / 8 / 5第二次右旋8 / \ 5 10这样就重新恢复平衡20 左右双旋为什么需要特殊处理平衡因子左右双旋与单旋不同旋转之前中间结点的平衡因子可能不同因此旋转以后三个关键结点的平衡因子并不一定全部为0代码需要提前保存中间结点的平衡因子intbfsubLR-_bf;然后进行两次旋转RotateL(parent-_left);RotateR(parent);最后根据旋转之前保存的bf设置三个结点的平衡因子21 左右双旋代码voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);RotateR(parent);if(bf0){subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1){subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1){subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}}这里最重要的是理解intbfsubLR-_bf;必须在旋转之前保存因为旋转之后结点之间的关系已经发生变化如果之后再判断原来的平衡因子就无法得到原始信息22 右左双旋右左双旋与左右双旋完全对称典型结构10 \ 15 / 12此时10的右边过高但是新增结点位于15的左边所以不能直接左旋需要先对15进行右旋 再对10进行左旋也就是RotateR(parent-_right);RotateL(parent);23 右左双旋代码voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf0){subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf1){subR-_bf0;subRL-_bf0;parent-_bf-1;}elseif(bf-1){subR-_bf1;subRL-_bf0;parent-_bf0;}else{assert(false);}}24 四种旋转如何判断判断 AVL 树旋转类型时可以根据失衡结点的平衡因子以及较高子树根结点的平衡因子来判断可以记成下面的关系情况结构旋转LL左左右单旋RR右右左单旋LR左右左右双旋RL右左右左双旋其中LL表示失衡结点的左子树的左边更高RR表示失衡结点的右子树的右边更高LR表示失衡结点的左子树的右边更高RL表示失衡结点的右子树的左边更高最重要的不是死记旋转名称而是观察失衡发生在哪一侧 新增结点又位于这一侧的哪一边25 AVL树查找AVL树本质上还是二叉搜索树所以查找逻辑与普通二叉搜索树基本一致Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}查找过程key 当前结点 ↓ 向右走 key 当前结点 ↓ 向左走 key 当前结点 ↓ 找到AVL树通过控制树的高度使查找效率保持在O(logN)26 AVL树的平衡检测实现 AVL 树之后不能只依赖插入代码判断自己是否正确还可以编写一个检测函数通过重新计算每个结点左右子树的高度然后检查实际平衡因子和结点保存的_bf是否一致27 计算树的高度int_Height(Node*root){if(rootnullptr)return0;intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);returnleftHeightrightHeight?leftHeight1:rightHeight1;}递归计算高度的基本思想空树高度 0 非空树高度 max(左子树高度, 右子树高度) 128 判断是否为AVL树首先计算当前结点左右子树高度intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);intdiffrightHeight-leftHeight;这里的diff就是根据真实高度重新计算出来的平衡因子然后检查abs(diff)1同时检查root-_bfdiff也就是说不仅要检查树是否平衡还要检查代码维护的_bf是否正确29 AVL树平衡检测代码bool_IsBalanceTree(Node*root){if(rootnullptr)returntrue;intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);intdiffrightHeight-leftHeight;if(abs(diff)2){coutroot-_kv.first高度差异常endl;returnfalse;}if(root-_bf!diff){coutroot-_kv.first平衡因子异常endl;returnfalse;}return_IsBalanceTree(root-_left)_IsBalanceTree(root-_right);}这个检测函数实际上检查了两件事情第一 左右子树高度差是否超过1 第二 代码维护的_bf是否等于真实计算出来的平衡因子只要其中一个条件不满足就说明 AVL 树实现存在问题30 AVL树的测试测试 AVL 树时可以准备一些容易触发双旋的特殊数据例如inta[]{4,2,6,1,3,5,15,7,16,14};插入完成后进行中序遍历t.InOrder();再检查t.IsBalanceTree();这样可以同时验证插入逻辑 搜索树性质 旋转逻辑 平衡因子31 大规模数据测试除了特殊数据还可以进行大量随机数据测试例如constintN100000;生成大量数据之后插入 AVL 树然后统计插入耗时 查找耗时 树高 结点数量例如coutInsert:end2-begin2endl;coutt.IsBalanceTree()endl;coutHeight:t.Height()endl;coutSize:t.Size()endl;这种测试可以验证 AVL 树在大量数据下是否仍然保持较好的树高和运行效率32 AVL树的核心代码逻辑整个 AVL 插入过程可以浓缩成下面这条逻辑链按照BST规则插入 ↓ 新结点连接parent ↓ 从parent开始向上更新_bf ↓ _bf 0 ↓ 停止更新 _bf 1 或 -1 ↓ 继续向上更新 _bf 2 或 -2 ↓ 判断旋转类型 ↓ LL → 右单旋 RR → 左单旋 LR → 左右双旋 RL → 右左双旋 ↓ 恢复平衡 ↓ 插入结束真正实现 AVL 树时最需要关注的并不是某一行代码而是这几个核心关系二叉搜索树规则 parent指针 平衡因子 四种旋转 旋转后的父子指针维护其中旋转代码最容易出问题的地方主要是1 修改孩子指针 2 修改孩子的parent 3 修改原parent的parent 4 修改上一层结点指向 5 必要时修改_root 6 更新旋转后结点的_bfAVL树的删除在该实现中没有展开讲解