高阶数据结构——AVL树的实现(详细解答）

目录

1.AVL的概念

2.AVL树的实现

2.1 AVL树的插入

2.1.1 平衡因子的更新

2.1.2 AVL树的插入

2.2 旋转

2.2.1 旋转的原则

2.2.2 右单旋

2.2.3 左单旋

2.2.4 先左后右双旋转

2.2.5 先右后左双旋转（先左后右双旋转模型的镜像）

2.2.6 代码总结

2.3 旋转总结

2.4 AVL树的查找

 2.5 AVL树平衡检测

---

1.AVL的概念

AVL树是最先发明的自平衡二叉查找树，AVL是⼀颗空树，或者具备下列性质的二叉搜索树：它的 左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是⼀颗高度平衡搜索二叉树， 通过控制高度差去控制平衡。

AVL树得名于它的发明者G.M.Adelson-Velsky和E.M.Landis是两个前苏联的科学家，他们在1962 年的论文《Analgorithmfortheorganizationofinformation》中发表了它。

AVL树实现这里我们引入⼀个平衡因子(balancefactor)的概念，每个结点都有⼀个平衡因子，任何 结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1， AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进行观察和控制树是否平衡， 就像⼀个风向标⼀样。

而如果说这个某个节点的平衡因子不是1/-1/0这三个中的一个，说明这个二叉树就不平衡了，需要进一步的将它调节平衡。那么如何调节平衡呢？咱们接下来会讲解的。

AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN ，那么增删查改的效率也可 以控制在O（logN） ，相比二叉搜索树有了本质的提升。

2.AVL树的实现

先来看一下大体的AVL树的结构：

template<class k, class v>
struct AVLTreeNode
{pair<k, v> _kv;AVLTreeNode<k, v>* _left;AVLTreeNode<k, v>* _right;AVLTreeNode<k, v>* _parent;int _bf;AVLTreeNode(const pair<k, v>& kv): _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0){}
};
template<class k,class v>
class AVLTree
{typedef AVLTreeNode<k, v> Node;
public:
private:Node* _root = nullptr;
};

还是老样子，使用模板来AVL树的节点结构以及AVL树的结构。这里还得多定义一个东西，那就是平衡因子（风向标）。

2.1 AVL树的插入

在讲解插入之前，咱们先来讲解一下平衡因子的更新：

2.1.1 平衡因子的更新

更新原则：

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

• 只有子树高度变化才会影响当前结点平衡因子。

• 插入结点，会增加高度，所以新增结点在parent的右子树，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的左子树，还是插入在parent的右子树，你只影响了parent的bf，但是对于parent的父节点的bf，不管你插入在parent的左边还是右边，都是一样的结果）。

• 更新后parent的平衡因子等于2或-2，更新前更新中parent的平衡因子变化为1->2或者-1->-2，说 明更新前parent子树⼀边高⼀边低，新增的插入结点在高的那边，parent所在的子树高的那边更⾼ 了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：1、把 parent子树旋转平衡。2、降低parent子树的高度，恢复到插入结点以前的⾼度。所以旋转后也不 需要继续往上更新，插入结束。

• 不断更新，更新到根，跟的平衡因子是1或-1也停止了。

最坏更新到根节点为止。

2.1.2 AVL树的插入

1. 插入⼀个值按二叉搜索树规则进行插入。

2. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新 从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可 以停止了，具体情况我们下面再详细分析。

3. 更新平衡因子过程中没有出现问题，则插入结束

4. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树 的高度，不会再影响上⼀层，所以插入结束。

这段话中，有一句：从发生不平衡的节点起，沿刚才回溯的路径取那个不平衡节点的下面两层的节点，从而进行判定。这个咱们马上就要讲了。

先看一下，插入部分，以及更新bf部分的代码：

bool Insert(const pair<k, v>& kv)
{if (_root == nullptr){Node* kk = new Node(kv);_root = kk;return true;}else{Node* parent = nullptr;Node* cur = _root;//循环找要插入的cur节点的位置while(cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else if(parent->_kv.first>kv.first){parent->_left = cur;}cur->_parent = parent;//最后别忘了更新cur的父节点//这儿只是插入，一个一个的找应该插入的位置，虽然这里parent为倒第二个高度位置//cur为倒第一个高度位置，但是不慌，下面的更新bf，会找出不符合的parent//从而实现更新parent，所以现在不需要担心parent的位置//更新bfwhile (parent){//先对插入的节点的位置的分析，从而判断应该加bf，还是减去bfif (cur == parent->_left){parent->_bf--;}else if (cur == parent->_right){parent->_bf++;}//现在进行更新parent位置的更新，看看哪个地方不符合bf的数值if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;//继续去找不符合bf数值的parent的位置}else if(parent->_bf==2||parent->_bf==-2){//现在问题有点棘手，需要进行旋转平衡二叉树}else{assert(false);//总共就这几种情况，如果说parent->_bf不在这几种情况中//大概率是出错了，直接断言报错即可。}}}return true;
}

这就是插入部分的大体的代码，那么有一些注意事项，我也全部放在了代码中，大家自行阅读。

2.2 旋转

2.2.1 旋转的原则

1. 保持搜索树的规则

2. 让旋转的树从不满足变平衡，其次降低旋转树的高度 旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。 说明：下面的图中，有些结点我们给的是具体值，如10和5等结点，这里是为了方便讲解，实际中是什 么值都可以，只要大小关系符合搜索树的性质即可。 

2.2.2 右单旋

OK，咱们先来讲右单旋，右单旋，这个右，顾名思义，就是左边太高了（这个高，指的是树的高度太高了，大家可以理解为深，所以为了方便大家理解，在这里，树的高，我称为深，而对于视觉上的高，我称为高）。那么右边太高了，咱们是不是得把右边的往下压一压，这样才可以实现右单旋。

• 本图展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要 求。10可能是整棵树的根，也可能是⼀个整棵树中局部的子树的根。这里a/b/c是高度为h的子树， 是一种概括抽象表示，他代表了所有右单旋的场景。

• 在a子树中插入⼀个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平 衡因子从-1变成-2，10为根的树左右高度差超过1，违反平衡规则。10为根的树左边太高了，需要 往右边旋转，控制两棵树的平衡。

• 旋转核心步骤，因为5<b子树的值<10，将b变成10的左子树，10变成5的右子树，5变成这棵树新的根（以5为旋转轴，让10顺时针旋转成为5的右子树），符合搜索树的规则，控制了平衡，同时这棵的⾼度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树的⼀个局部子树，旋转后不会再影响上⼀层，插入结束了。

那么咱们来看插入的代码：

//右单旋
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;//只要定义需要移动的的节点即可parent->_left = subLR;if (subLR)//如果该节点为空，那么就不需要连接了,也就是不需要更新父节点的位置了。{subLR->_parent = parent;}//这里得先提前记录一下原来的没动位置之前的parent的父节点，因为到了后面//parent的位置别修改了，则这个parentParent就找不到了Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;//父节点的位置也别忘了更新if (parent==_root)//判断parent是否为根节点{subL = _root;subL->_parent = nullptr;}else{if (parent == parentParent->_left)//如果parent不是根节点，就//判断一下原来parent是parentParent的左边还是右边，之后再连接。{parentParent->_left = subL;}else if (parent == parentParent->_right){parentParent->_right = subL;}subL->_parent = parentParent;//别忘了更新父节点的位置}parent->_bf = subL->_bf = 0;//最后别忘了更新parent与sunL的bf。
}

代码请配套上面的那个图片看，以及，咱们可以发现：这个右单旋parent与subL是不是同号呀。 

OK，下面来说另外一个问题，咱们图中的a，b，c，是啥呀？是一种抽象的表述。就是，这个a里面可能还有很多的自平衡二叉树，b里可能也有很多，c里可能也有很多。但是呢，不管你有多少的这个自平衡二叉树，只要你的某个节点的bf不对，那么你都要修改，而且修改模型，（就是修改的模型办法），都是这一种情况。所以，也可以理解为对底层的封装。下面的节点是怎样的，我不关心，因为不管下面的节点是多是少，就算没有，在插入节点后引发了某个节点的bf异常，我还是按这个方法进行旋转控制平衡就可以了。

那么既然都说到这里了，就来看一下，a，b，c的各个不同的情况的总结吧。

 

 

以上就是h等于0，1，2的场景的a，b，c的不同形态，你会发现，殊途同归，最终，还是按照那一种方法进行旋转的。 

2.2.3 左单旋

顾名思义，左边旋转，说明左边比较高，而右边比较深，所以要把左边给压一压，这样才可以实现平衡。

• 本图展示的是10为根的树，有a/b/c抽象为三棵高度为h的子树(h>=0)，a/b/c均符合AVL树的要 求。10可能是整棵树的根，也可能是⼀个整棵树中局部的子树的根。这⾥a/b/c是高度为h的子树， 是⼀种概括抽象表示。

• 在a子树中插入⼀个新结点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致10的平 衡因子从1变成2，10为根的树左右高度差超过1，违反平衡规则。10为根的树右边太高了，需要往 左边旋转，控制两棵树的平衡。

• 旋转核心步骤，，因为10<b子树的值<15，将b变成10的右子树，10变成15的左子树，15变成这棵树新的根（以15为旋转轴，让10逆时针方向旋转成为15的左子树)，符合搜索树的规则，控制了平衡，同时这棵的高度恢复到了插入之前的h+2，符合旋转原则。如果插入之前10整棵树的⼀个局部子树，旋转后不会再影响上一层，插入结束了。

OK，其实左单旋的模型就是右单旋模型的一个镜像，这里也有抽象表示，但是其意义与右单旋的模型一致，前面已经讲过了。那么，咱们来看代码：

//左单旋
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}Node* parentParent = parent->_parent;subR->_left = parent;parent->_parent = subR;if (parent == _root){subR = _root;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else if (parent == parentParent->_right){parentParent->_right = subR;}subR->_parent = parentParent;}subR->_bf = parent->_bf = 0;
}

这个代码与右单旋很像很像，所以也不多赘述，还有就是，这个的parent与subR是不是也是同号呀。

2.2.4 先左后右双旋转

 

先观察这两个图片，先看第一种，看着熟悉不，没错，就是左边深，（右单旋），但是！，咱们的右单旋的模型的插入，是插入在哪里的呀？是插入在a位置的，就是纯粹的一边深（左边深），但是这个不是，这个图是插入在了b这个位置，已经不是纯粹的左边深了，属于左边深的右边深！那么对于这种情况，咱们如果说还用纯粹的一个右单旋来解决的话，你看看可以不？肯定不可以！所以，需要进行两次旋转。即对于5来说，右边深，需要进行左单旋，对于10来说，左边深，需要进行右单旋。那么此时，咱们的问题就解决了不是吗？

OK，咱们先来看图片，听我一点一点的细细的分析：

 

 我们将a/b/c子树抽象为高度h的AVL 子树进行分析，另外我们需要把b子树的细节进⼀步展开为8和左子树高度为h-1的e和f子树，因为 我们要对b的父亲5为旋转点进行左单旋，左单旋需要动b树中的左子树。b子树中新增结点的位置 不同，平衡因子更新的细节也不同，通过观察8的平衡因子不同，这里我们要分三个场景讨论。

• 场景1：h>=1时，8的bf为-1，新增结点插⼊在e子树，e子树高度从h-1并为h并不断更新8->5->10平衡因子， 引发旋转，其中8的平衡因子为-1，旋转后8和5平衡因子为0，10平衡因子为1。

• 场景2：h>=1时，8的bf为1，新增结点插⼊在f子树，f子树高度从h-1变为h并不断更新8->5->10平衡因子，引 发旋转，其中8的平衡因子为1，旋转后8和10平衡因⼦为0，5平衡因子为-1。

• 场景3：h==0时，8的bf为0，a/b/c都是空树，b自己就是⼀个新增结点，不断更新5->10平衡因子，引发旋 转，其中8的平衡因子为0，旋转后8和10和5平衡因子均为0。

旋转也是挺好旋转的，其实就行进行两个单个的旋转而已：现以8为旋转轴，以逆时针顺序将5旋转到8的左子树。后以8为旋转轴，以顺时针顺序将10旋转到8的右子树。

大家可以发现，这个的parent与subR是不是异号呀。

还有就是，这个先左后右旋转模型，不就是右单旋模型的插入地方改了一下嘛？

OK，咱们来看代码吧：

//左右双旋转，即左子树中的右子树，所以先旋转深的左子树，之后旋转深的右边的
void RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;//定义这个的目的是，通过判断这个bf，判断这个插入，插在了哪里，是左边//还是右边，还是没有插入，分三种情况写出RotateL(subL);RotateR(parent);if (bf == -1)//左边插入{parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1)//右边插入{parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else if (bf == 0)//没有插入{parent->_bf = subL->_bf = subLR->_bf = 0;}else{assert(false);//最后bf的情况以上都没有，肯定是false了，直接断言一下即可}
}

2.2.5 先右后左双旋转（先左后右双旋转模型的镜像）

• 跟左右双旋类似，下面我们将a/b/c子树抽象为高度h的AVL子树进行分析，另外我们需要把b子树的 细节进⼀步展开为12和左子树⾼度为h-1的e和f子树，因为我们要对b的父亲15为旋转点进行右单 旋，右单旋需要动b树中的右子树（那么就需要知道b树的具体结构）。b子树中新增结点的位置不同，平衡因子更新的细节也不同，通 过观察12的平衡因子不同，这⾥我们要分三个场景讨论。

• 场景1：h>=1时，12的bf为-1，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因 子，引发旋转，其中12的平衡因子为-1，旋转后10和12平衡因子为0，15平衡因子为1。

• 场景2：h>=1时，12的bf为1，新增结点插入在f子树，f子树⾼度从h-1变为h并不断更新12->15->10平衡因子， 引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。

• 场景3：h==0时，12的bf为0，a/b/c都是空树，b自己就是⼀个新增结点，不断更新15->10平衡因子，引发旋 转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0 。

那么大家看着这个模型熟悉不？肯定熟悉，咱们的左单旋不就是这个模型吗？但是！但是！不同！，因为左单旋的模型的插入是插入在a的，就是纯粹的一边深（右边深），但是这个是插在了b上，就是右边深的左边深，所以要先进行右单旋，再进行左单旋，其实就是两次简单的旋转而已。

先以12为旋转轴，用顺时针的方向将15旋转成为12的右子树。再以12为旋转轴，用逆时针的方向将10旋转成为12的左子树。

//右左双旋
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == -1){subR->_bf = 1;parent->_bf = 0;subRL->_bf = 0;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}else{assert(false);}
}

那么通过这个也可以发现，其实，parent与subR是异号的。

2.2.6 代码总结

OK，那么来说，bf不正常阶段的代码咱们已经全部实现，现在就放到那个if判断语句中，下面就看全部的插入代码吧：

bool Insert(const pair<k, v>& kv)
{if (_root == nullptr){Node* kk = new Node(kv);_root = kk;return true;}else{Node* parent = nullptr;Node* cur = _root;//循环找要插入的cur节点的位置while(cur){if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(kv);if (parent->_kv.first < kv.first){parent->_right = cur;}else if(parent->_kv.first>kv.first){parent->_left = cur;}cur->_parent = parent;//最后别忘了更新cur的父节点//这儿只是插入，一个一个的找应该插入的位置，虽然这里parent为倒第二个高度位置//cur为倒第一个高度位置，但是不慌，下面的更新bf，会找出不符合的parent//从而实现更新parent，所以现在不需要担心parent的位置//更新bfwhile (parent){//先对插入的节点的位置的分析，从而判断应该加bf，还是减去bfif (cur == parent->_left){parent->_bf--;}else if (cur == parent->_right){parent->_bf++;}//现在进行更新parent位置的更新，看看哪个地方不符合bf的数值if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = parent;parent = parent->_parent;//继续去找不符合bf数值的parent的位置}else if(parent->_bf==2||parent->_bf==-2){//现在问题有点棘手，需要进行旋转平衡二叉树// 单旋就是纯粹的左边高或者右边高// 双旋就是不是纯粹一边高，比如：右子树高，右子树里面又是左子树高// 不平衡，旋转处理一下if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}break;}else{assert(false);//总共就这几种情况，如果说parent->_bf不在这几种情况中//大概率是出错了，直接断言报错即可。}}}return true;
}

下面来看一副从空树开始建立的自平衡二叉树的过程吧：

 

2.3 旋转总结

其实，旋转总共就4中模型，并且，殊途同归，不管下面的节点怎样，始终都是这四种模型。

1.先左后右双旋转模型就是右单旋模型的插入地方改了一下。先右后左双旋转模型就是左单旋模型的插入地方改了一下。 

 2.如果parent的bf为2，说明右子树深，左边高：

2.1 如果subR的bf为1，（同号）说明插入的节点插入在了subR的右边，就是纯粹的一边深了，只需要调用右单旋即可。

2.2 如果subR的bf为-1，（异号）说明插入的节点插入在了subR的左边，那就不是纯粹的一边深了，属于右边深的左边深，应该先进行右单旋，再进行左单旋。

 3.如果parent的bf为-2，说明左子树深，右边高：

2.1 如果subL的bf为1，（异号）说明插入的节点插入在了subL的右边，那就不是纯粹的一边深了，属于左边深的右边深，应该先进行左单旋，再进行右单旋。

2.2 如果subL的bf为-1，（同号）说明插入的节点插入在了subL的左边，那就是纯粹的一边深，只需要进行一个左单旋即可。

2.4 AVL树的查找

 Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return nullptr;}
//搜索效率为O（logN）

 2.5 AVL树平衡检测

我们实现的AVL树是否合格，我们通过检查左右子树高度差的的程序进行反向验证，同时检查⼀下结点 的平衡因子更新是否出现了问题。

int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}
bool _IsBalanceTree(Node* root){// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << "高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);}

还有一个AVL树的删除，在这里作者就不做过多的阐述了，大家有兴趣的可以自行去研究。

OK，本篇完..................