个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》,《拾光Linux》《网络安全》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录AVL树1.AVL树的定义2.AVL树的实现2.1AVL树的结构2.2AVL树的插入及平衡因子的更新3.旋转右单旋左单旋左右双旋右左双旋AVL树1.AVL树的定义AVL树是一颗空树或者具备以下性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。每个结点都有一个平衡因子右子树高度减去左子树高度即任何结点的平衡因子等于0/1/-1通过平衡因子判断AVL树是否平衡。2.AVL树的实现2.1AVL树的结构templateclassK,classVstructAVLTreeNode{// 需要parent指针后续更新平衡因⼦可以看到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){}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public://...private:Node*_rootnullptr;};2.2AVL树的插入及平衡因子的更新插入插入一个值按二叉搜索树规则进行插入。新增节点以后只会影响祖先结点的高度平衡因子更新时平衡因子没问题则结束若平衡因子不平衡则需要对不平衡子树进行旋转直至不在影响上一层插入结束。更新原则只有子树高度变化才会影响当前结点平衡因子。新增结点在parent的右子树parent的平衡因子 新增结点在parent的左子树parent平衡因子- -更新停止条件更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0 或者 1-0说明更新前parent子树⼀边高⼀边低新增的结点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲结点的平衡因子更新结束。更新后parent的平衡因子等于1 或 -1更新前更新中parent的平衡因子变化为0-1 或者 0--1说明更新前parent子树两边⼀样高新增的插入结点后parent所在的子树⼀边高⼀边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上更新。更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新插入结束。不断更新更新到根根的平衡因子是1或-1也停止了。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;}3.旋转右单旋下图展示的是10为根的树有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。在a子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要往右边旋转控制两棵树的平衡。旋转步骤将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原则。 下面我们来实现一下注意处理parent结点的时候要分两种情况parent就是这棵树的根节点parent为parentParent的右子节点或左子节点。在旋转完成之后要更新平衡因子。voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-leftsubLR;if(subLR)//这里subLR要判空subLR-_parentparent;subL-rightparent;parent-_parentsubL;Node*parentParentparent-_parent;if(parent_root){_rootsubL;subL-_parentnullptr;}else//还要包括parent有_parent的情况,但是不知道parent是左子节点还是右子节点{if(parentParent-_leftparent){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}subL-_bfparent-_bf0;//更改平衡因子}左单旋左单旋类似于反过来的右单旋旋转步骤将b变成10的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原则。下面我们来实现一下voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL){subRL-_parentparent;}subR-_leftparent;parent-_parentsubR;Node*parentParentparent-_parent;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentParent-_rightparent){parentParent-_rightsubR;}else{parentParent-_leftsubR;}subR-_parentparentParent;}subR-_bfparent-_bf0;}左右双旋右单旋解决的纯粹的左边高。 而遇到这种左孩子高且左孩子的右子树高光用单纯的右单旋是无法解决的。这时就需要两次旋转才能解决。因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论场景一h 1时,新增结点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。场景二h 1时新增结点插入在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中**8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1。**场景二和场景一同样的旋转法只不过旋转后平衡因子的变化有所不同。场景三h 0时a/b/c都是空树b自己就是⼀个新增结点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。下面我们来实现一下左右双旋voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);//先左旋RotateR(parent);//再右旋//重点平衡因子的调节if(bf0){parent-_bf0;subL-_bf0;subLR-_bf0;}elseif(bf1){parent-_bf0;subL-_bf-1;subLR-_bf0;}elseif(bf-1){parent-_bf1;subL-_bf0;subLR-_bf0;}else{assert(false);}}右左双旋右左双旋和左右双旋差不多同样也分三个场景场景一h 1时新增结点插入在e子树e子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1。场景二h 1时新增结点插入在f子树f子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。场景三h 0时a/b/c都是空树b自己就是⼀个新增结点不断更新15-10平衡因子引发旋转其中12的平衡因子为0旋转后10和12和15平衡因子均为0。下面我们来实现一下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);}}到这儿本期C——【AVL树】的实现的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习。不见不散✌️ 
长河君 · 2026/10/11 1:40:24 · 阅读 1.2k C++——【AVL树】的代码实现、旋转
个人主页ꪔ小林Y✨个人专栏《C小白闯关日记》《C语言小白闯关日记》《数据结构入门——从原理到实战》,《拾光Linux》《网络安全》代码信条每一行代码都是成长的脚印每一次调试成功都是对坚持的回应目录AVL树1.AVL树的定义2.AVL树的实现2.1AVL树的结构2.2AVL树的插入及平衡因子的更新3.旋转右单旋左单旋左右双旋右左双旋AVL树1.AVL树的定义AVL树是一颗空树或者具备以下性质的二叉搜索树它的左右子树都是AVL树且左右子树的高度差的绝对值不超过1。每个结点都有一个平衡因子右子树高度减去左子树高度即任何结点的平衡因子等于0/1/-1通过平衡因子判断AVL树是否平衡。2.AVL树的实现2.1AVL树的结构templateclassK,classVstructAVLTreeNode{// 需要parent指针后续更新平衡因⼦可以看到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){}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;public://...private:Node*_rootnullptr;};2.2AVL树的插入及平衡因子的更新插入插入一个值按二叉搜索树规则进行插入。新增节点以后只会影响祖先结点的高度平衡因子更新时平衡因子没问题则结束若平衡因子不平衡则需要对不平衡子树进行旋转直至不在影响上一层插入结束。更新原则只有子树高度变化才会影响当前结点平衡因子。新增结点在parent的右子树parent的平衡因子 新增结点在parent的左子树parent平衡因子- -更新停止条件更新后parent的平衡因子等于0更新中parent的平衡因子变化为-1-0 或者 1-0说明更新前parent子树⼀边高⼀边低新增的结点插入在低的那边插入后parent所在的子树高度不变不会影响parent的父亲结点的平衡因子更新结束。更新后parent的平衡因子等于1 或 -1更新前更新中parent的平衡因子变化为0-1 或者 0--1说明更新前parent子树两边⼀样高新增的插入结点后parent所在的子树⼀边高⼀边低parent所在的子树符合平衡要求但是高度增加了1会影响parent的父亲结点的平衡因子所以要继续向上更新。更新后parent的平衡因子等于2 或 -2更新前更新中parent的平衡因子变化为1-2 或者 -1--2说明更新前parent子树⼀边高⼀边低新增的插入结点在高的那边parent所在的子树高的那边更高了破坏了平衡parent所在的子树不符合平衡要求需要旋转处理旋转的目标有两个1、把parent子树旋转平衡。2、降低parent子树的高度恢复到插入结点以前的高度。所以旋转后也不需要继续往上更新插入结束。不断更新更新到根根的平衡因子是1或-1也停止了。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;}3.旋转右单旋下图展示的是10为根的树有a/b/c抽象为三棵高度为h的子树(h0)a/b/c均符合AVL树的要求。10可能是整棵树的根也可能是⼀个整棵树中局部的子树的根。在a子树中插入一个新结点导致a子树的高度从h变成h1不断向上更新平衡因子导致10的平衡因子从-1变成-210为根的树左右高度差超过1违反平衡规则。10为根的树左边太高了需要往右边旋转控制两棵树的平衡。旋转步骤将b变成10的左子树10变成5的右子树5变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原则。 下面我们来实现一下注意处理parent结点的时候要分两种情况parent就是这棵树的根节点parent为parentParent的右子节点或左子节点。在旋转完成之后要更新平衡因子。voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;parent-leftsubLR;if(subLR)//这里subLR要判空subLR-_parentparent;subL-rightparent;parent-_parentsubL;Node*parentParentparent-_parent;if(parent_root){_rootsubL;subL-_parentnullptr;}else//还要包括parent有_parent的情况,但是不知道parent是左子节点还是右子节点{if(parentParent-_leftparent){parentParent-_leftsubL;}else{parentParent-_rightsubL;}subL-_parentparentParent;}subL-_bfparent-_bf0;//更改平衡因子}左单旋左单旋类似于反过来的右单旋旋转步骤将b变成10的右子树10变成15的左子树15变成这棵树新的根符合搜索树的规则控制了平衡同时这棵的高度恢复到了插入之前的h2符合旋转原则。下面我们来实现一下voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL){subRL-_parentparent;}subR-_leftparent;parent-_parentsubR;Node*parentParentparent-_parent;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentParent-_rightparent){parentParent-_rightsubR;}else{parentParent-_leftsubR;}subR-_parentparentParent;}subR-_bfparent-_bf0;}左右双旋右单旋解决的纯粹的左边高。 而遇到这种左孩子高且左孩子的右子树高光用单纯的右单旋是无法解决的。这时就需要两次旋转才能解决。因为我们要对b的父亲5为旋转点进行左单旋左单旋需要动b树中的左子树。b子树中新增结点的位置不同平衡因子更新的细节也不同通过观察8的平衡因子不同这里我们要分三个场景讨论场景一h 1时,新增结点插入在e子树e子树高度从h-1并为h并不断更新8-5-10平衡因子引发旋转其中8的平衡因子为-1旋转后8和5平衡因子为010平衡因子为1。场景二h 1时新增结点插入在f子树f子树高度从h-1变为h并不断更新8-5-10平衡因子引发旋转其中**8的平衡因子为1旋转后8和10平衡因子为05平衡因子为-1。**场景二和场景一同样的旋转法只不过旋转后平衡因子的变化有所不同。场景三h 0时a/b/c都是空树b自己就是⼀个新增结点不断更新5-10平衡因子引发旋转其中8的平衡因子为0旋转后8和10和5平衡因子均为0。下面我们来实现一下左右双旋voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);//先左旋RotateR(parent);//再右旋//重点平衡因子的调节if(bf0){parent-_bf0;subL-_bf0;subLR-_bf0;}elseif(bf1){parent-_bf0;subL-_bf-1;subLR-_bf0;}elseif(bf-1){parent-_bf1;subL-_bf0;subLR-_bf0;}else{assert(false);}}右左双旋右左双旋和左右双旋差不多同样也分三个场景场景一h 1时新增结点插入在e子树e子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为-1旋转后10和12平衡因子为015平衡因子为1。场景二h 1时新增结点插入在f子树f子树高度从h-1变为h并不断更新12-15-10平衡因子引发旋转其中12的平衡因子为1旋转后15和12平衡因子为010平衡因子为-1。场景三h 0时a/b/c都是空树b自己就是⼀个新增结点不断更新15-10平衡因子引发旋转其中12的平衡因子为0旋转后10和12和15平衡因子均为0。下面我们来实现一下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);}}到这儿本期C——【AVL树】的实现的内容就结束了。如果文中有表述不准的地方或是你有更清晰的理解思路强烈欢迎在评论区留言交流——技术路上多碰撞才能更快进步觉得内容对你有帮助的话别忘了点赞❤️➕收藏方便后续回顾复习想跟着一起系统学习数据结构的朋友也可以点击关注下一期我们会聚焦更进一步的学习。不见不散✌️