本文代码已同步Github一、AVL树解决了什么问题二叉搜索树能够根据关键字快速完成查找、插入和删除但它的效率依赖于树的形状。如果插入的数据接近有序普通二叉搜索树就可能逐渐退化成单链表。此时树的高度接近节点个数原本希望接近O(logN)的操作也会退化到O(N)。AVL树就是在二叉搜索树的基础上增加了一条平衡规则对树中的任意节点左右子树的高度差都不能超过1。为了描述一个节点左右子树的高度差我们在节点中增加平衡因子。本文统一采用下面的计算方式平衡因子 右子树高度 - 左子树高度。因此一棵AVL树中每个节点的平衡因子只能是-1、0或1。当某个节点的平衡因子变成-2或2时说明以该节点为根的子树已经失衡需要通过旋转恢复平衡。AVL树并不是要求左右子树高度完全相同而是把整棵树的高度控制在O(logN)从而保证查找、插入和删除的时间复杂度都能稳定在O(logN)。二、基础框架搭建AVL树首先是一棵二叉搜索树所以节点中仍然需要保存键值对、左右孩子指针。为了在插入后向上更新祖先节点还要保存父指针和平衡因子。templateclassK,classVstructAVLNode{std::pairK,V_kv;AVLNodeK,V*_left;AVLNodeK,V*_right;AVLNodeK,V*_parent;int_bf;AVLNode(conststd::pairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{public:usingNodeAVLNodeK,V;private:Node*_rootnullptr;};新节点刚插入时还没有左右子树因此平衡因子初始化为0。三、插入与平衡因子的更新1、先按二叉搜索树的规则插入AVL树的插入可以分成两步根据关键字找到新节点的插入位置从新节点的父节点开始沿父指针向上更新平衡因子。第一步和普通二叉搜索树完全相同。真正需要分析的是插入一个节点后为什么有时要继续向上更新有时却可以直接停止2、三种更新结果如果新节点插入在parent的左子树说明左子树高度增加parent-_bf需要减1如果插入在右子树则需要加1。if(parent-_leftcur)--parent-_bf;elseparent-_bf;更新后会出现三种情况。a、平衡因子变成0这说明原来较矮的一侧高度增加后左右子树重新等高。以parent为根的子树高度没有变化因此不会继续影响上一层可以直接停止更新。b、平衡因子变成1或-1这说明以parent为根的子树仍然平衡但它的整体高度增加了1。既然子树高度发生变化就可能继续影响祖先节点因此需要沿父指针向上更新。c、平衡因子变成2或-2这说明当前节点已经失衡需要根据新增节点所在的方向选择对应的旋转。总结一下parent-_bf 0子树高度不变停止向上更新parent-_bf 1 || parent-_bf -1子树高度增加继续向上更新parent-_bf 2 || parent-_bf -2当前子树失衡执行旋转。对于插入操作第一次找到失衡祖先并完成正确旋转后旋转后的子树高度会恢复到本次插入前的高度因此不会再影响更高层的祖先旋转后可以直接结束更新。3、完整的插入逻辑有了前面二叉搜索树的经验插入位置并不难找。这里主要补上平衡因子的更新和四种旋转的选择。boolInsert(conststd::pairK,Vkv){if(_rootnullptr){_rootnewNode(kv);returntrue;}Node*cur_root;Node*parentnullptr;while(cur){if(kv.firstcur-_kv.first){parentcur;curcur-_right;}elseif(kv.firstcur-_kv.first){parentcur;curcur-_left;}else{returnfalse;}}curnewNode(kv);if(kv.firstparent-_kv.first)parent-_rightcur;elseparent-_leftcur;cur-_parentparent;while(parent){if(parent-_leftcur)--parent-_bf;elseparent-_bf;if(parent-_bf0){break;}elseif(parent-_bf1||parent-_bf-1){curparent;parentparent-_parent;}elseif(parent-_bf-2){if(cur-_bf-1)RotateR(parent);elseRotateLR(parent);break;}elseif(parent-_bf2){if(cur-_bf1)RotateL(parent);elseRotateRL(parent);break;}else{assert(false);}}returntrue;}判断旋转类型时要同时观察失衡节点parent和较高孩子cur的平衡因子parent-_bfcur-_bf失衡类型处理方式-2-1左左右单旋21右右左单旋-21左右左右双旋2-1右左右左双旋四、旋转旋转需要同时满足两个目标旋转后仍然符合二叉搜索树的大小关系降低较高一侧的高度让失衡子树重新平衡。旋转一共有四种右单旋、左单旋、左右双旋和右左双旋。1、右单旋当失衡节点的平衡因子为-2并且较高的左孩子平衡因子为-1时新增节点位于较高左子树的左侧这是典型的左失衡需要右单旋。右单旋的关键在于图中的b子树。因为16 b子树中的值 20所以b可以成为20的左子树再让20成为16的右孩子旋转后仍然满足二叉搜索树的规则。实现时可以把旋转点记作RNode它的左孩子记作RNodeL左孩子的右子树记作RNodeLR。voidRotateR(Node*RNode){Node*RNodeLRNode-_left;Node*RNodeLRRNodeL-_right;RNode-_leftRNodeLR;if(RNodeLR)RNodeLR-_parentRNode;Node*RNodePRNode-_parent;RNodeL-_rightRNode;RNode-_parentRNodeL;if(RNodePnullptr){_rootRNodeL;_root-_parentnullptr;}else{if(RNodeP-_leftRNode)RNodeP-_leftRNodeL;elseRNodeP-_rightRNodeL;RNodeL-_parentRNodeP;}RNode-_bfRNodeL-_bf0;}这里有两个容易忽略的细节修改孩子指针时也要同步修改对应节点的父指针RNode既可能是整棵树的根也可能只是一棵局部子树的根因此必须提前保存RNodeP旋转后重新接回上一层。2、左单旋左单旋和右单旋完全对称。当失衡节点的平衡因子为2较高的右孩子平衡因子为1时新增节点位于较高右子树的右侧需要进行左单旋。图中的b子树满足10 b子树中的值 20因此可以把b接到10的右侧再让10成为20的左孩子。voidRotateL(Node*RNode){Node*RNodeRRNode-_right;Node*RNodeRLRNodeR-_left;RNode-_rightRNodeRL;if(RNodeRL)RNodeRL-_parentRNode;Node*RNodePRNode-_parent;RNodeR-_leftRNode;RNode-_parentRNodeR;if(RNodePnullptr){_rootRNodeR;_root-_parentnullptr;}else{if(RNodeP-_leftRNode)RNodeP-_leftRNodeR;elseRNodeP-_rightRNodeR;RNodeR-_parentRNodeP;}RNode-_bfRNodeR-_bf0;}3、左右双旋如果失衡节点左边高但新增节点插入在较高左子树的右侧只进行一次右旋并不能恢复平衡。此时需要先对左孩子进行左单旋把折线形结构转成纯粹的左左失衡再对失衡节点进行右单旋。左右双旋的本质仍然是修改指针指向再更新平衡因子。指针调整可以直接复用前面的RotateL和RotateR但平衡因子不能简单全部置零还有一种h 0的特殊情况设失衡节点为RNode它的左孩子为RNodeL左孩子的右孩子为RNodeLR。双旋完成后RNodeLR会成为这棵子树的新根因此要根据它旋转前的平衡因子分别处理。voidRotateLR(Node*RNode){Node*RNodeLRNode-_left;Node*RNodeLRRNodeL-_right;intbfRNodeLR-_bf;RotateL(RNodeL);RotateR(RNode);if(bf0){RNode-_bf0;RNodeL-_bf0;}elseif(bf1){RNode-_bf0;RNodeL-_bf-1;}elseif(bf-1){RNode-_bf1;RNodeL-_bf0;}else{assert(false);}RNodeLR-_bf0;}当bf 0时说明RNodeLR就是本次新插入的节点双旋后三个节点的平衡因子都为0。当bf为1或-1时说明RNodeLR下面原本还挂着子树需要根据较高方向更新另外两个节点的平衡因子。4、右左双旋右左双旋和左右双旋对称。当失衡节点右边高但新增节点插入在较高右子树的左侧时需要先对右孩子进行右单旋再对失衡节点进行左单旋。除了图中子树高度不为0的情况还要考虑只有三个关键节点的特殊情况。此时中间节点的平衡因子为0双旋后三个节点都恢复平衡。voidRotateRL(Node*RNode){Node*RNodeRRNode-_right;Node*RNodeRLRNodeR-_left;intbfRNodeRL-_bf;RotateR(RNodeR);RotateL(RNode);if(bf0){RNode-_bf0;RNodeR-_bf0;}elseif(bf1){RNode-_bf-1;RNodeR-_bf0;}elseif(bf-1){RNode-_bf0;RNodeR-_bf1;}else{assert(false);}RNodeRL-_bf0;}四种旋转看起来情况很多但判断思路可以归纳成两步先看失衡节点哪一侧更高再看新增节点位于较高子树的外侧还是内侧。新增节点在外侧时使用单旋在内侧时使用双旋。五、查找AVL树仍然遵守二叉搜索树的规则因此查找逻辑不需要改变。需要注意的是查找并不是遍历整棵树而是从根节点开始根据关键字的大小关系沿一条路径向下查找。Node*Find(constKkey){Node*cur_root;while(cur){if(keycur-_kv.first){curcur-_right;}elseif(keycur-_kv.first){curcur-_left;}else{returncur;}}returnnullptr;}因为AVL树能够把高度维持在O(logN)所以查找的时间复杂度也稳定在O(logN)。六、平衡检测只看中序遍历有序并不能证明这棵树就是AVL树。中序遍历只能验证二叉搜索树的大小关系还需要额外验证两个条件每个节点左右子树的高度差不能超过1根据高度重新计算出的平衡因子必须和节点中保存的_bf一致。int_Height(Node*root){if(rootnullptr)return0;intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);returnstd::max(leftHeight,rightHeight)1;}bool_IsBalanceTree(Node*root){if(rootnullptr)returntrue;intleftHeight_Height(root-_left);intrightHeight_Height(root-_right);intdiffrightHeight-leftHeight;if(std::abs(diff)2){std::coutroot-_kv.first高度差异常std::endl;returnfalse;}if(root-_bf!diff){std::coutroot-_kv.first平衡因子异常std::endl;returnfalse;}return_IsBalanceTree(root-_left)_IsBalanceTree(root-_right);}测试时不能只准备一种插入顺序。左左、右右、左右和右左四种失衡都要覆盖再补充一组包含多次旋转的混合数据。四组最小用例的中序遍历结果都有序平衡检测都为true混合插入后的中序结果同样有序并且查找存在和不存在的关键字也符合预期。七、总结AVL树在二叉搜索树的基础上增加了平衡因子并在插入破坏平衡时通过旋转调整结构。插入过程中平衡因子的变化决定了是否继续向上更新变成0说明子树高度不变变成1或-1说明高度增加变成2或-2则需要旋转。四种旋转虽然结构不同但核心始终只有两件事在不破坏二叉搜索树大小关系的前提下重新连接指针根据旋转前的结构更新平衡因子。AVL树的关键不是记住四段旋转代码而是看懂“哪一侧变高、新节点落在内侧还是外侧”。如果觉得有帮助可以关注Github项目持续更新