本文代码已同步Github

一、AVL树解决了什么问题

二叉搜索树能够根据关键字快速完成查找、插入和删除，但它的效率依赖于树的形状。

如果插入的数据接近有序，普通二叉搜索树就可能逐渐退化成单链表。此时树的高度接近节点个数，原本希望接近O(logN)的操作也会退化到O(N)。

AVL树就是在二叉搜索树的基础上增加了一条平衡规则：

对树中的任意节点，左右子树的高度差都不能超过1。

为了描述一个节点左右子树的高度差，我们在节点中增加平衡因子。本文统一采用下面的计算方式：

平衡因子 = 右子树高度 - 左子树高度。

因此，一棵AVL树中每个节点的平衡因子只能是-1、0或1。当某个节点的平衡因子变成-2或2时，说明以该节点为根的子树已经失衡，需要通过旋转恢复平衡。

AVL树并不是要求左右子树高度完全相同，而是把整棵树的高度控制在O(logN)，从而保证查找、插入和删除的时间复杂度都能稳定在O(logN)。

二、基础框架搭建

AVL树首先是一棵二叉搜索树，所以节点中仍然需要保存键值对、左右孩子指针。为了在插入后向上更新祖先节点，还要保存父指针和平衡因子。

template<classK,classV>structAVLNode{std::pair<K,V>_kv;AVLNode<K,V>*_left;AVLNode<K,V>*_right;AVLNode<K,V>*_parent;int_bf;AVLNode(conststd::pair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};template<classK,classV>classAVLTree{public:usingNode=AVLNode<K,V>;private:Node*_root=nullptr;};

新节点刚插入时还没有左右子树，因此平衡因子初始化为0。

三、插入与平衡因子的更新

1、先按二叉搜索树的规则插入

AVL树的插入可以分成两步：

1. 根据关键字找到新节点的插入位置；
2. 从新节点的父节点开始，沿父指针向上更新平衡因子。

第一步和普通二叉搜索树完全相同。真正需要分析的是：插入一个节点后，为什么有时要继续向上更新，有时却可以直接停止？

2、三种更新结果

如果新节点插入在parent的左子树，说明左子树高度增加，parent->_bf需要减1；如果插入在右子树，则需要加1。

if(parent->_left==cur)--parent->_bf;else++parent->_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::pair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*cur=_root;Node*parent=nullptr;while(cur){if(kv.first>cur->_kv.first){parent=cur;cur=cur->_right;}elseif(kv.first<cur->_kv.first){parent=cur;cur=cur->_left;}else{returnfalse;}}cur=newNode(kv);if(kv.first>parent->_kv.first)parent->_right=cur;elseparent->_left=cur;cur->_parent=parent;while(parent){if(parent->_left==cur)--parent->_bf;else++parent->_bf;if(parent->_bf==0){break;}elseif(parent->_bf==1||parent->_bf==-1){cur=parent;parent=parent->_parent;}elseif(parent->_bf==-2){if(cur->_bf==-1)RotateR(parent);elseRotateLR(parent);break;}elseif(parent->_bf==2){if(cur->_bf==1)RotateL(parent);elseRotateRL(parent);break;}else{assert(false);}}returntrue;}

判断旋转类型时，要同时观察失衡节点parent和较高孩子cur的平衡因子：

四、旋转

旋转需要同时满足两个目标：

• 旋转后仍然符合二叉搜索树的大小关系；
• 降低较高一侧的高度，让失衡子树重新平衡。

旋转一共有四种：右单旋、左单旋、左右双旋和右左双旋。

1、右单旋

当失衡节点的平衡因子为-2，并且较高的左孩子平衡因子为-1时，新增节点位于较高左子树的左侧，这是典型的左失衡，需要右单旋。

右单旋的关键在于图中的b子树。

因为16 < b子树中的值 < 20，所以b可以成为20的左子树；再让20成为16的右孩子，旋转后仍然满足二叉搜索树的规则。

实现时可以把旋转点记作RNode，它的左孩子记作RNodeL，左孩子的右子树记作RNodeLR。

voidRotateR(Node*RNode){Node*RNodeL=RNode->_left;Node*RNodeLR=RNodeL->_right;RNode->_left=RNodeLR;if(RNodeLR)RNodeLR->_parent=RNode;Node*RNodeP=RNode->_parent;RNodeL->_right=RNode;RNode->_parent=RNodeL;if(RNodeP==nullptr){_root=RNodeL;_root->_parent=nullptr;}else{if(RNodeP->_left==RNode)RNodeP->_left=RNodeL;elseRNodeP->_right=RNodeL;RNodeL->_parent=RNodeP;}RNode->_bf=RNodeL->_bf=0;}

这里有两个容易忽略的细节：

• 修改孩子指针时，也要同步修改对应节点的父指针；
• RNode既可能是整棵树的根，也可能只是一棵局部子树的根，因此必须提前保存RNodeP，旋转后重新接回上一层。

2、左单旋

左单旋和右单旋完全对称。

当失衡节点的平衡因子为2，较高的右孩子平衡因子为1时，新增节点位于较高右子树的右侧，需要进行左单旋。

图中的b子树满足10 < b子树中的值 < 20，因此可以把b接到10的右侧，再让10成为20的左孩子。

voidRotateL(Node*RNode){Node*RNodeR=RNode->_right;Node*RNodeRL=RNodeR->_left;RNode->_right=RNodeRL;if(RNodeRL)RNodeRL->_parent=RNode;Node*RNodeP=RNode->_parent;RNodeR->_left=RNode;RNode->_parent=RNodeR;if(RNodeP==nullptr){_root=RNodeR;_root->_parent=nullptr;}else{if(RNodeP->_left==RNode)RNodeP->_left=RNodeR;elseRNodeP->_right=RNodeR;RNodeR->_parent=RNodeP;}RNode->_bf=RNodeR->_bf=0;}

3、左右双旋

如果失衡节点左边高，但新增节点插入在较高左子树的右侧，只进行一次右旋并不能恢复平衡。

此时需要先对左孩子进行左单旋，把折线形结构转成纯粹的左左失衡；再对失衡节点进行右单旋。

左右双旋的本质仍然是修改指针指向，再更新平衡因子。指针调整可以直接复用前面的RotateL和RotateR，但平衡因子不能简单全部置零；

还有一种h = 0的特殊情况

设失衡节点为RNode，它的左孩子为RNodeL，左孩子的右孩子为RNodeLR。双旋完成后，RNodeLR会成为这棵子树的新根，因此要根据它旋转前的平衡因子分别处理。

voidRotateLR(Node*RNode){Node*RNodeL=RNode->_left;Node*RNodeLR=RNodeL->_right;intbf=RNodeLR->_bf;RotateL(RNodeL);RotateR(RNode);if(bf==0){RNode->_bf=0;RNodeL->_bf=0;}elseif(bf==1){RNode->_bf=0;RNodeL->_bf=-1;}elseif(bf==-1){RNode->_bf=1;RNodeL->_bf=0;}else{assert(false);}RNodeLR->_bf=0;}

当bf == 0时，说明RNodeLR就是本次新插入的节点，双旋后三个节点的平衡因子都为0。

当bf为1或-1时，说明RNodeLR下面原本还挂着子树，需要根据较高方向更新另外两个节点的平衡因子。

4、右左双旋

右左双旋和左右双旋对称。

当失衡节点右边高，但新增节点插入在较高右子树的左侧时，需要先对右孩子进行右单旋，再对失衡节点进行左单旋。

除了图中子树高度不为0的情况，还要考虑只有三个关键节点的特殊情况。此时中间节点的平衡因子为0，双旋后三个节点都恢复平衡。

voidRotateRL(Node*RNode){Node*RNodeR=RNode->_right;Node*RNodeRL=RNodeR->_left;intbf=RNodeRL->_bf;RotateR(RNodeR);RotateL(RNode);if(bf==0){RNode->_bf=0;RNodeR->_bf=0;}elseif(bf==1){RNode->_bf=-1;RNodeR->_bf=0;}elseif(bf==-1){RNode->_bf=0;RNodeR->_bf=1;}else{assert(false);}RNodeRL->_bf=0;}

四种旋转看起来情况很多，但判断思路可以归纳成两步：

1. 先看失衡节点哪一侧更高；
2. 再看新增节点位于较高子树的外侧还是内侧。

新增节点在外侧时使用单旋，在内侧时使用双旋。

五、查找

AVL树仍然遵守二叉搜索树的规则，因此查找逻辑不需要改变。

需要注意的是，查找并不是遍历整棵树，而是从根节点开始，根据关键字的大小关系沿一条路径向下查找。

Node*Find(constK&key){Node*cur=_root;while(cur){if(key>cur->_kv.first){cur=cur->_right;}elseif(key<cur->_kv.first){cur=cur->_left;}else{returncur;}}returnnullptr;}

因为AVL树能够把高度维持在O(logN)，所以查找的时间复杂度也稳定在O(logN)。

六、平衡检测

只看中序遍历有序，并不能证明这棵树就是AVL树。中序遍历只能验证二叉搜索树的大小关系，还需要额外验证两个条件：

1. 每个节点左右子树的高度差不能超过1；
2. 根据高度重新计算出的平衡因子，必须和节点中保存的_bf一致。

int_Height(Node*root){if(root==nullptr)return0;intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);returnstd::max(leftHeight,rightHeight)+1;}bool_IsBalanceTree(Node*root){if(root==nullptr)returntrue;intleftHeight=_Height(root->_left);intrightHeight=_Height(root->_right);intdiff=rightHeight-leftHeight;if(std::abs(diff)>=2){std::cout<<root->_kv.first<<"高度差异常"<<std::endl;returnfalse;}if(root->_bf!=diff){std::cout<<root->_kv.first<<"平衡因子异常"<<std::endl;returnfalse;}return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}

测试时不能只准备一种插入顺序。左左、右右、左右和右左四种失衡都要覆盖，再补充一组包含多次旋转的混合数据。

四组最小用例的中序遍历结果都有序，平衡检测都为true；混合插入后的中序结果同样有序，并且查找存在和不存在的关键字也符合预期。

七、总结

AVL树在二叉搜索树的基础上增加了平衡因子，并在插入破坏平衡时通过旋转调整结构。

插入过程中，平衡因子的变化决定了是否继续向上更新：变成0说明子树高度不变，变成1或-1说明高度增加，变成2或-2则需要旋转。

四种旋转虽然结构不同，但核心始终只有两件事：

• 在不破坏二叉搜索树大小关系的前提下重新连接指针；
• 根据旋转前的结构更新平衡因子。

AVL树的关键不是记住四段旋转代码，而是看懂“哪一侧变高、新节点落在内侧还是外侧”。

如果觉得有帮助，可以关注Github项目持续更新