云深麋鹿专栏C | 用C语言学数据结构 | Java回顾上一篇我们结束了 mapset的使用接下来这篇文章让我们进入到 AVLTree 的学习体会新的设计思路吧~放个目录一 AVL树的概念二 实现2.1 AVLTreeNode2.2 AVLTree2.3 Insert2.3.1 插入流程1新增结点2更新平衡因子3旋转2.3.2 平衡因子更新1更新原则2停止更新条件3代码实现2.3.3 旋转1旋转原则2右单旋3 左单旋4左右双旋5右左双旋2.3.4 Insert完整代码2.4 AVL树的平衡检测2.5 AVL树的查找2.6 简单测试一下一 AVL树的概念AVL树是一棵高度平衡二叉查找树左右子树高度差的绝对值不超过1。每个结点有一个平衡因子balance factor这不是必须的。有些情况下高度差不为0。二 实现2.1 AVLTreeNodetemplateclassK,classVstructAVLTreeNode{pairK,V_kv;AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;int_bf;// balance factorAVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};这里的Node存储的是一个pair键值对应用场景更广一些。需要额外记录每个Node的_parent后面要用到。实现的是带平衡因子后面都简称bf的AVL树。2.2 AVLTreetemplateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public:// ...private:Node*_rootnullptr;};搭个框架。2.3 Insert2.3.1 插入流程1新增结点按二叉搜索树规则来。具体在这篇博客 C | 二叉搜索树 第三大块。代码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-_leftcur;}else{parent-_rightcur;}cur-_parentparent;// ...}2更新平衡因子新增结点更新 新增节点 - 根节点 路径上的bf。具体后面展开讲。3旋转更新bf的过程中出现不平衡左右子树高度差的绝对值超过1需要旋转不平衡子树。平衡后就不用继续往上更新bf了完毕。2.3.2 平衡因子更新1更新原则平衡因子 右子树高度 - 左子树高度子树高度变化影响当前结点平衡因子。插入结点parent更新新结点在左–在右若parent的bf不为零则往上更新。2停止更新条件更新后parent的bf为 零表示parent所在子树高度不变。则parent的parent结点的bf不会受到影响更新结束。更新后parent的bf为 1 或 -1表示parent所在子树原先平衡更新后高度改变。则parent的parent结点的bf也会受到影响往上继续更新。更新后parent的bf为 2 或 -2表示parent所在子树已经不平衡了需要旋转处理。不断更新到rootbf为 1 或 -1 停止。3代码实现先套一个框架新增节点 的 parent 存在时进入循环体。while(parent){//...}更新 parent 的 bfif(parent-_kv.firstkv.first){parent-_bf--;}else{parent-_bf;}判断 parent 的 bf 是否为零if(parent-_bf0){break;}elseif(abs(parent-_bf)1){// continuecurparent;parentparent-_parent;}elseif(abs(parent-_bf)2){// rotatebreak;}else{// errorexit(-1);}接下来进入rotate上面第二个else if。2.3.3 旋转旋转共有四种左旋转、右旋转、左右双旋 和 右左双旋。1旋转原则旋转后保持搜索树的特性。让旋转的树从不平衡变平衡其次降低旋转树的高度。2右单旋左子树太高了。即如图中a子树新增一个结点 高h1太高了。①过程subL的右子树subLR变为parent结点的左子树subL结点到parent结点的位置上。parent上面还有parentParent后面会用到。最终实现结果②代码实现框架voidRotateR(Node*parent){//...}注意修改结点位置也要修改它的_parent。记录各个结点根据传参parentNode*subLparent-_left;Node*subLRsubL-_right;Node*parentParentparent-_parent;处理parent和subLRparent-_leftsubLR;if(subLR){subLR-_parentparent;}存在subLR为nullptr的情况。处理subL和parentsubL-_rightparent;parent-_parentsubL;处理parentParent和subLif(parentParent){if(parentParent-_leftparent){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}else{_rootsubL;_root-_parentnullptr;}涉及parentParent存在不存在的问题。若存在涉及parentParent存在于哪个分支的问题。记得更新bfparent-_bfsubL-_bf0;3 左单旋右子树太高了。即如图中a子树新增一个结点后 高h1①过程subR的左子树subRL变为parent结点的右子树subR结点到parent结点的位置上。最终实现结果②代码实现跟右单旋代码类似voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;Node*parentParentparent-_parent;parent-_rightsubRL;if(subRL){subRL-_parentparent;}subR-_leftparent;parent-_parentsubR;if(parentParent){if(parentParent-_leftparent){parentParent-_leftsubR;}else{parentParent-_rightsubR;}subR-_parentparentParent;}else{_rootsubR;_root-_parentnullptr;}parent-_bfsubR-_bf0;}4左右双旋左子树高了左子树的右子树高了。即图中 e子树 新增结点后 高h。subL 总高h2跟c子树高度差超过1了。①过程subL左单旋 parent右单旋。实现结果②代码实现框架:voidRotateRL(Node*parent){//...}记录各个结点Node*subLparent-_left;Node*subLRsubL-_right;Node*parentParentparent-_parent;额外记录一下bfintbfsubLR-_bf;旋转RotateL(parent-_left);RotateR(parent);这个直接复用写过的代码。重点 更新bfif(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{exit(-1);}演示一下这几种情况5右左双旋右子树高了右子树的左子树高了。即图中 e子树 新增结点后 高h。①过程subR右单旋 parent左单旋。结果②代码实现跟左右双旋类似直接上代码voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;Node*parentParentparent-_parent;intbfsubRL-_bf;RotateR(subR);RotateL(parent);if(bf0){subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf-1){subR-_bf1;subRL-_bf0;parent-_bf0;}elseif(bf1){subR-_bf0;subRL-_bf0;parent-_bf-1;}else{exit(-1);}}2.3.4 Insert完整代码加上省略掉的rotate部分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-_leftcur;}else{parent-_rightcur;}cur-_parentparent;// Update balance factorwhile(parent){if(parent-_kv.firstkv.first){parent-_bf--;}else{parent-_bf;}if(parent-_bf0){break;}elseif(abs(parent-_bf)1){// continuecurparent;parentparent-_parent;}elseif(abs(parent-_bf)2){// rotateif(parent-_bf-2){if(cur-_bf-1){RotateL(parent);}elseif(cur-_bf1){RotateLR(parent);}}elseif(parent-_bf2){if(cur-_bf1){RotateR(parent);}elseif(cur-_bf-1){RotateRL(parent);}}break;}else{// errorexit(-1);}}returntrue;}2.4 AVL树的平衡检测框架boolIsBalanceTree(Node*root){// ...}处理root为空的情况if(rootnullptr){returntrue;}记录左右子树高度intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);计算高度差即为 root 的实际bfintdifferencerightHeight-leftHeight;检查 difference 是否合理if(abs(difference)2){coutroot-_kv.firstabnormal height differenceendl;returnfalse;}检查已存储bf是否正确if(difference!root-_bf){coutroot-_kv.firstabnormal balance factorendl;returnfalse;}不能直接检查bf因为bf可能更新错。递归往root左右判断returnIsBalanceTree(root-_left)IsBalanceTree(root-_right);再开放一个public接口供外部使用boolIsBalanceTree(){return_IsBalanceTree(_root);}2.5 AVL树的查找没啥好说的跟二叉搜索树一样Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}2.6 简单测试一下AVLTree定义在定义域wyzy里了。wyzy::AVLTreeint,intt;inta[]{4,2,6,1,3,5,15,7,16,14};for(autoe:a){t.Insert({e,e});}t.Print();coutendl;coutt.IsBalanceTree()endl;定义了一个Print函数用于输出classAVLTree{publicvoidPrint(){_Print(_root);}private:void_Print(Node*root){if(rootnullptr){return;}_Print(root-_left);coutroot-_kv.first root-_bfendl;_Print(root-_right);}}这个递归老生常谈了就不多说了。运行这么一棵树AVLTree 的学习就到这里下一篇我们再上一个新的树 红黑树 很快bushi会更出来~