手撕AVL树

引入：为何要有AVL树，二次搜索树有什么不足？

一：AVL树的概念

其满足树中的任意一颗子树的左右子树高度差不超过1

Q：节点旁边的数字代表什么？

A：实现AVL树的方式多种多样，博主采取的是平衡因子法来实现，图中节点旁边的数字即代表该节点的平衡因子大小，平衡因子值 = 该节点的右子树高度-左子树高度，其能反映该树是否为AVL树，平衡因子>1 或 <-1则代表该树不为AVL树，则需要通过一些列的处理，让其再成为AVL树

Q：高度差不超过0，不是更平衡吗

A：某些个数的节点，永远无法达到0的高度差，如2个节点，4个节点，所以最优就是高度差为1

注意：

①：高度指的是该子树的最高高度，例如节点5的右子树高度是3 而不是7->6此路径的高度2

②：博主的_bf表示的是：某个节点的右子树高度-左子树高度的值，某些实现也有可能是左-右，这里以博主自己的右-左来讲解

二：AVL树实现

一个结构只要包含节点，实现的框架都是两个类：这里是节点类和AVL树类(list就是list类)

1：节点类的实现

//节点类
template<class K, class V>
struct AVLTreeNode
{//成员变量AVLTreeNode<K, V>* _left;//左指针AVLTreeNode<K, V>* _right;//右指针AVLTreeNode<K, V>* _parent;//父指针int _bf; //平衡因子(balance factor的缩写) 代表某个节点的右子树高度-左子树高度的值pair<K, V> _kv;//每个节点的kv值//构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr) , _bf(0) , _kv(kv) {}
};

解释：

①：AVL树是对KV模型的搜索二叉树的升级，所以AVL树照样是KV结构的

②：博主还设置了父指针，方便后序的操作

2：AVL类的实现

AVL树的实现很多，一步一步讲解吧~ 先看框架

a：框架

template<class K, class V>
class AVLTree
{//方便使用节点类 只需Node即可typedef AVLTreeNode<K, V> Node;
public://......各种函数private://成员变量_root根节点Node* _root = nullptr;
};

b： 插入函数(重难点)

注意：代码注释中博主有时候会简称parent节点为p节点

插入函数的思路：

找到插入的位置将其插入进去，插入后判断是否还是AVL树，不是则处理，让其恢复为AVL树

插入的情况：

a：插入后还是一颗AVL树

咋找到插入的地方进行插入即可

b：插入后不再是一颗AVL树

根据不再是AVL树的情况，进行对应的处理(旋转处理)，让其恢复为AVL树

由于代码过长 分成以下4步来讲解和展示

①：如何找到插入的位置并插入

②：如何判断插入后是否还是AV树

③：不是AVL树的几种旋转处理

④：展示的总代码

①：如何找到插入的位置并插入

//插入函数bool Insert(const pair<K, V>& kv){//空树情况if (_root == nullptr){_root = new Node(kv);return true;}//开始找位置进行插入Node* parent = nullptr;Node* cur = _root;//从根节点开始找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//AVL树不会存在相同的节点{return false;}}//走到这代表 找到了插入的位置 cur = new Node(kv);//先把该节点准备好//parent节点是找到的插入位置的父节点//所以现在将cur正确的链接到parent的正确方向if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完成 则返回真return true;}

解释：

a：如何找到插入的位置 和 如何插入 和二叉搜索树是一样的，根据你插入的值的k值，来和根节点的k值比较，插入的k大，则往右子树找，反之左子树，如此循环，直到找到插入的位置，且找的途中遇到和插入的k值一样的节点，代表插入失败，因为AVL树不会存在两个相同的节 

b：成功找到插入的位置了，该位置一定原先为nullptr，此时再根绝原先为nullptr的节点和其父节点(代码注释中博主有时候会简称parent节点为p节点)的关系，来对parent节点和插入节点的链接

以上代码只是让插入的节点成功的插入到了该插入的位置，若是二叉搜索树到此也就结束了，但是AVL树插入之后，需要判断其是否还是一颗AVL树，是则不再处理，不是则需要处理

②：如何判断插入后是否还是AV树

Q：如何判断插入节点后，该树是否还是一颗AVL树呢？

A：根据插入节点后，该插入节点对于其祖先节点的_bf的值带来的改变来判断

插入对祖先节点的_bf的影响有以下几种：

解释：插入后p节点的_bf变为0，则代表插入前p节点的_bf为-1(只有一个左孩子) 或者 1(图示)，此情况则代表插入节点只会影响p节点的_bf，因为对于p的parent节点来说，p这颗子树高度没变，所以次树还是一颗AVL树，无需处理

解释：插入后p节点的_bf变为1(图示)或者-1(插入到了节点9的左侧)，则代表插入前p节点的_bf为0，此情况则代表插入一个节点后，不仅会影响p还会影响p的parent节点的_bf，此时的p的parent节点的_bf为2或者-2，皆代表不再是一颗AVL树，需要处理了

总结：

AVL树插入操作中平衡因子的更新规则

在AVL树中插入一个新节点时，需要更新相关祖先节点的平衡因子（Balance Factor, BF），并检查更新之后的平衡因子是否违反平衡条件。逻辑如下：

---

1. 受影响的节点

插入新节点后，需要从新节点的父节点开始，逐层向上更新，直到根节点或某个祖先节点的子树高度不再变化。

---

2. 平衡因子更新原则

设当前正在更新的_bf是节点为p，现在插入一个子节点为 c

• 如果 c 是 p 的左孩子：p->bf--（左子树高度增加）。

• 如果 c 是 p 的右孩子：p->bf++（右子树高度增加）。

---

3. 是否继续向上更新？

更新 p 的平衡因子后，根据其更新后的值来决定是否继续回溯更新祖先节点：

1. 情况 1：p->bf == 0

   • 说明：更新前 p->bf 为 1 或 -1，插入操作使较矮的一侧子树高度增加，p 的左右子树变得平衡。

   • 影响：以p为根节点的这颗树高度不变，因此不会影响更高层祖先节点的平衡因子。

   • 操作：终止更新祖先节点的_bf。

2. 情况 2：p->bf == 1 或 p->bf == -1

   • 说明：更新前 p->bf 为 0，插入操作使某一侧子树高度增加。

   • 影响：p 的子树高度变化，会影响其父节点的平衡因子。

   • 操作：继续向上更新祖先节点。

3. 情况 3：p->bf == 2 或 p->bf == -2

   • 说明：p 的平衡因子违反AVL树规则，需要通过处理(旋转操作)重新平衡子树。

---

所以 如何判断插入后是否还是AVL树 的代码如下：

        //插入完成一定会影响parent节点的bf(只是看cur是p的哪一边 bf再++或--)//p的bf三种情况：bf 0; 1/-1;2/-2//0：不会影响parent的祖先的bf 直接break//1/-1：树高度增加 会影响祖先的bf 所以更新完p的bf 再次循环继续更新上面的bf//2/-2：则需要旋转while (parent){//根据插入节点是p的哪一边来更新p的bfif (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//对更新完的p的bf判断if (parent->_bf == 0){break;}//祖先节点依旧需要更新bf  再次循环else if (parent->_bf == 1 || parent->_bf == -1){//向上更新两个变量cur = cur->_parent;parent = parent->_parent;}//来到这代表需要旋转//进入旋转，咋代表cur和parent在之前的循环中已经找到了_bf为2/-1的节点 则对该节点处理else if (parent->_bf == 2 || parent->_bf == -2){//进行旋转处理//旋转处理后 则代表恢复AVL树 break出去break;}

以上只是完成了判断插入的后时候是AVL树，是则不处理，不是则处理，那么不是AVL树的旋转处理是什么？

③：不是AVL树的几种旋转处理

旋转不只是一种，分为四种旋转，两种单旋，两种双旋

也就是说不是AVL树的情况分为四种，每种对应一种旋转来处理~

a：左单旋

对上图的左单旋再画图讲解：

Q：这样操作下来，还符合搜索二叉树吗？b为什么能放在30的右 30又为什么能放在60的左

A：符合。b这颗子树的值都是比60小(其在60的左)且比30大(因为30的右子树都比30大)，所以b可以放在30的右，30能放在60的左(30新增的右子树b，也比60小)

将左旋转转换为代码：

    //步骤： //①：给到p的右指针指向原先p的右孩子的左子树//②：p的右子树的的左指针指向p节点void RotateL(Node* parent)//参数的p节点 就是bf为2的节点{Node* subR = parent->_right; //p的右Node* subRL = subR->_left;   //p的右左parent->_right = subRL;//①if (subRL) //避免p的右左为空subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent; //先记录p的父节点 以防p节点不是根节点parent->_parent = subR; //②if (parent == _root)//查看p是否为根节点{//p是根节点 则subR成为新的根接节点//再置一下subR父指针为空_root = subR;subR->_parent = nullptr;}else//p不是根 则p的父亲也需要正确的指向subR(判断原先的p是pp的左右孩子的哪一个){if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}

解释： 看起来仅仅是需要执行步骤中的①② ，但实则会有几个问题：

①：若subRL为空的处理

②：subRL 和 p  的 父指针 需要重新指向父节点

③：30节点也就是左旋转函数的参数parent节点，是根节点和不是根节点的处理

④：修改平衡因子，按照上上图可知，左旋转，会让parent和subR的_bf为0

b：右单旋

右单旋和左单旋大同小异，不再过多赘述了

//①：p的左指针指向p原先的左孩子的右孩子//②：原先的p的左孩子的右指针指向p节点//代码逻辑和左旋转同理 不再赘述void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}

c：左右双旋

AVL在插入节点失去平衡的前提是，是有一颗子树较高(比另一测高1)

所以我们之前：

a右单旋，就是左子树为较高子树，且在该子树的左侧插入

b左单旋，就是右子树为较高子树，且在该子树的右侧插入

那有没有可能 插入较高左子树的右侧 或 较高右子树的左侧？

当然有，所以前者需要左右双旋 后者需要右左双旋

左右双旋示意图：

解释：先以30为旋转节点，对其左单旋，然后再以90为旋转节点，对其右单旋

只看最后一步和第一步的话。也可以理解为：40作根节点，30 60 做40左右孩子，40的左给30的右，40的右给60的左，一定是符合搜索二叉树的

新的问题：插入较高左子树的右测不止一种情况！！

如图所示，共有三种情况：

解释：每种情况虽然都可以用左右双旋恢复成AVL树，但是恢复之后某些节点的_bf值不一样，

如下图所示：

Q：那我们现在知道了不同的情况恢复为AVL树后的节点的_bf不同，那根据什么去判断不同的情况呢？

A：先明白插入一个节点后，是先更新整棵树需要更新_bf的节点，所以我们可以按照插入之后的subRL的_bf，也就是上图中的40节点的_bf值来判断，由图也可知，三种不同的插入情况，也只有subRL的_bf不同了，分别为-1；1；0，-1则对应左右旋转后的subRL的bf为0，subL的bf为0，parent的bf为1，其他两种不在赘述

所以左右旋转的代码如下：

//步骤 ：//①：对p的左节点进行左单旋//②：再对p节点进行右单旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//由于在b树插入 在c树插入 或60本身就是插入的节点入 这三种情况双旋之后的树的bf不同//规律：根据插入节点的bf判断即可if (bf == -1)//代表在b树插入{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//代表在c树插入{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//else if (bf == 0)//代表subLR就是插入节点{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

d：右左双旋

和左右双旋的情况类型，也是分为三种情况，不再赘述

代码如下：

//步骤 ：//①：对p的右节点进行右单旋//②：再对p节点进行左单旋//代码逻辑类似 不再赘述void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

 ④：插入函数的总代码

//插入函数bool Insert(const pair<K, V>& kv){//空树情况if (_root == nullptr){_root = new Node(kv);return true;}//开始找位置进行插入Node* parent = nullptr;Node* cur = _root;//从根节点开始找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//AVL树不会存在相同的节点{return false;}}//走到这代表 找到了插入的位置 cur = new Node(kv);//先把该节点准备好//parent节点在之前是cur的父节点 也就是空节点的父亲//所以现在能将cur正确的链接到parent的正确方向if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完成一定会影响parent节点的bf(只是看cur是p的哪一边 bf再++或--)//p的bf三种情况：bf 0 1/-1 2/-2//0：不会影响parent的祖先的bf 直接break//1/-1：树高度增加 会影响祖先的bf 所以更新完p的bf 再次循环继续更新上面的bf//2/-2：则需要旋转while (parent){//第一次更新p的bfif (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//对更新完的p的bf判断if (parent->_bf == 0){break;}//祖先节点依旧需要更新bf  再次循环else if (parent->_bf == 1 || parent->_bf == -1){cur = cur->_parent;parent = parent->_parent;}//需要旋转//进入旋转，咋代表cur和parent 之前已经循环找了 需要旋转的p节点//(该p节点的bf 2/-2)else if (parent->_bf == 2 || parent->_bf == -2){// 左旋转// 触发条件：p->bf为2 cur->_bf == 1if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}// 右旋转// 触发条件：parent->_bf == -2 && cur->_bf == -1else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}// 左右旋转// 触发条件：parent->_bf == -2 && cur->_bf == 1else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//除此之外右左旋转else{RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);//标记“不应执行到此处”}}//插入完成 则返回真return true;}//左旋转//新节点插入较高右子树的右侧---简称右右//代表从次树的_root节点看右子树高1 且插入的节点在右子树的右侧//步骤： //①：给到p的右指针指向原先p的右孩子的左子树//②：p的右子树的的左指针指向p节点void RotateL(Node* parent)//参数的p节点 就是bf为2的节点{Node* subR = parent->_right; //p的右Node* subRL = subR->_left;   //p的右左parent->_right = subRL;//①if (subRL) //避免p的右左为空subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent; //先记录p的父节点 以防p节点不是根节点parent->_parent = subR; //②if (parent == _root)//查看p是否为根节点{//p是根节点 则subR成为新的根接节点//再置一下subR父指针为空_root = subR;subR->_parent = nullptr;}else//p不是根 则p的父亲也需要正确的指向subR(判断原先的p是pp的左右孩子的哪一个){if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}//右旋转//新节点插入较高左子树的左侧 简称左左//代表从次树的_root节点看左子树高1 且插入的节点在左子树的左侧//步骤： //①：p的左指针指向p原先的左孩子的右孩子//②：原先的p的左孩子的右指针指向p节点//代码逻辑和左旋转同理 不再赘述void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}//左右旋转->先左单旋再右单旋//新节点插入较高左子树的右侧//步骤 ：//①：对p的左节点进行左单旋//②：再对p节点进行右单旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//由于在b树插入 在c树插入 或60本身就是插入的节点入 这三种情况双旋之后的树的bf不同//规律：根据插入节点的bf判断即可if (bf == -1)//代表在b树插入{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//代表在c树插入{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//else if (bf == 0)//代表subLR就是插入节点{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}//右左旋转//新节点插入较高右子树的左侧---右左：先右单旋再左单旋//步骤 ：//①：对p的右节点进行右单旋//②：再对p节点进行左单旋//代码逻辑类似 不再赘述void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}

c：中序函数

和二叉搜索树类似，不再赘述

void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << "[" << root->_bf << "]" << endl;_InOrder(root->_right);}//中序遍历void InOrder(){_InOrder(_root);}

d：查找函数

和二叉搜索树类似，不再赘述

//查找函数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 NULL;}

e：IsBalence()函数(判断平衡函数)

我们写了以上这么多的函数实现，能证明其是一颗AVL树吗？？？

Q：我们中序遍历是升序，不就是AVL树吗

A： 中序遍历是升序，只能说明是二叉搜索树！

Q：打印一下每个节点的_bf值，没有一个_bf值大于1或者小于-1，不就行了？

A：万一bf本身就是错的呢，你怎么保证你的bf一定是对的？

Q：层序遍历打印，然后自己画二叉树？

A：你怎么知道打印出来的一串值，从哪里分割？怎么画二叉树？

正确答案：写一个IsBalence()函数(判断平衡函数)！来解决

该函数内部，会递归调用Height()函数去算每颗子树的高度差，顺便将此高度差和我们自己的_bf值对比一下，验证一下我们的准确性！

代码：

    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;}//高度函数int Height(){return _Height(_root);}bool _IsBalance(Node* root) {if (root == nullptr) {return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);// 检查当前节点是否平衡（左右子树高度差不超过1）if (abs(rightHeight - leftHeight) >= 2) {cout << root->_kv.first << " 不平衡" << endl;return false;}// 检查平衡因子是否正确（bf应等于右子树高度减左子树高度）if (rightHeight - leftHeight != root->_bf) {cout << root->_kv.first << " 平衡因子异常" << endl;return false;}// 递归检查左右子树return _IsBalance(root->_left) && _IsBalance(root->_right);}//是否平衡判断函数 bool IsBalance() //这是我们在类外调用的函数{int height = 0;return _IsBalance(_root, height);}

解释：该函数虽然达到了我们的要求，但是其并不是一个优秀的函数，其进行了大量的重复运算

对于一棵树，_IsBalance 会从根节点开始，逐层递归计算高度，导致子节点的高度被重复计算多次。例如，根节点的左右子树高度会被计算一次，而它们的子节点又会在各自的递归中被重复计算。

更优秀的判断平衡函数：

//更优秀的平衡函数bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}//是否平衡判断函数bool IsBalance(){int height = 0;return _IsBalance(_root, height);}

 解释：该函数没有重复运算

抽象图如下： 

由上上图可知：

在递归过程中，通过 int& height 参数传递子树高度，避免重复计算。

计算高度和平衡性检查在一次后序遍历（左→右→根）中完成，时间复杂度降至 O(n)。

f：节点个数函数

过于简单不再赘述

//计算树的节点个数size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}

没有实现删除，因为删除校招不考 考得一般是手撕旋转

三：AVL树代码

#pragma once
#include<assert.h>
#include<vector>//节点类
template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorpair<K, V> _kv;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr) //指向父节点的之怎, _bf(0) //平衡因子, _kv(kv) //pair类型的对象  存储k值和v值{}
};
//AVL类
template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public://插入函数bool Insert(const pair<K, V>& kv){//空树情况if (_root == nullptr){_root = new Node(kv);return true;}//开始找位置进行插入Node* parent = nullptr;Node* cur = _root;//从根节点开始找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//AVL树不会存在相同的节点{return false;}}//走到这代表 找到了插入的位置 cur = new Node(kv);//先把该节点准备好//parent节点在之前是cur的父节点 也就是空节点的父亲//所以现在能将cur正确的链接到parent的正确方向if (parent->_kv.first < kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;//插入完成一定会影响parent节点的bf(只是看cur是p的哪一边 bf再++或--)//p的bf三种情况：bf 0 1/-1 2/-2//0：不会影响parent的祖先的bf 直接break//1/-1：树高度增加 会影响祖先的bf 所以更新完p的bf 再次循环继续更新上面的bf//2/-2：则需要旋转while (parent){//第一次更新p的bfif (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}//对更新完的p的bf判断if (parent->_bf == 0){break;}//祖先节点依旧需要更新bf  再次循环else if (parent->_bf == 1 || parent->_bf == -1){cur = cur->_parent;parent = parent->_parent;}//需要旋转//进入旋转，咋代表cur和parent 之前已经循环找了 需要旋转的p节点//(该p节点的bf 2/-2)else if (parent->_bf == 2 || parent->_bf == -2){// 左旋转// 触发条件：p->bf为2 cur->_bf == 1if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}// 右旋转// 触发条件：parent->_bf == -2 && cur->_bf == -1else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}// 左右旋转// 触发条件：parent->_bf == -2 && cur->_bf == 1else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}//除此之外右左旋转else{RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);//标记“不应执行到此处”}}//插入完成 则返回真return true;}//左旋转//新节点插入较高右子树的右侧---简称右右//代表从次树的_root节点看右子树高1 且插入的节点在右子树的右侧//步骤： //①：给到p的右指针指向原先p的右孩子的左子树//②：p的右子树的的左指针指向p节点void RotateL(Node* parent)//参数的p节点 就是bf为2的节点{Node* subR = parent->_right; //p的右Node* subRL = subR->_left;   //p的右左parent->_right = subRL;//①if (subRL) //避免p的右左为空subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent; //先记录p的父节点 以防p节点不是根节点parent->_parent = subR; //②if (parent == _root)//查看p是否为根节点{//p是根节点 则subR成为新的根接节点//再置一下subR父指针为空_root = subR;subR->_parent = nullptr;}else//p不是根 则p的父亲也需要正确的指向subR(判断原先的p是pp的左右孩子的哪一个){if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}//右旋转//新节点插入较高左子树的左侧 简称左左//代表从次树的_root节点看左子树高1 且插入的节点在左子树的左侧//步骤： //①：p的左指针指向p原先的左孩子的右孩子//②：原先的p的左孩子的右指针指向p节点//代码逻辑和左旋转同理 不再赘述void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}//左右旋转->先左单旋再右单旋//新节点插入较高左子树的右侧//步骤 ：//①：对p的左节点进行左单旋//②：再对p节点进行右单旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);//由于在b树插入 在c树插入 或60本身就是插入的节点入 这三种情况双旋之后的树的bf不同//规律：根据插入节点的bf判断即可if (bf == -1)//代表在b树插入{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1)//代表在c树插入{subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}//else if (bf == 0)//代表subLR就是插入节点{subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}//右左旋转//新节点插入较高右子树的左侧---右左：先右单旋再左单旋//步骤 ：//①：对p的右节点进行右单旋//②：再对p节点进行左单旋//代码逻辑类似 不再赘述void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << "[" << root->_bf << "]" << endl;_InOrder(root->_right);}//中序遍历void InOrder(){_InOrder(_root);}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;}//高度函数int Height(){return _Height(_root);}//bool _IsBalance(Node* root) {//	if (root == nullptr) {//		return true;//	}//	int leftHeight = Height(root->_left);//	int rightHeight = Height(root->_right);//	// 检查当前节点是否平衡（左右子树高度差不超过1）//	if (abs(rightHeight - leftHeight) >= 2) {//		cout << root->_kv.first << " 不平衡" << endl;//		return false;//	}//	// 检查平衡因子是否正确（bf应等于右子树高度减左子树高度）//	if (rightHeight - leftHeight != root->_bf) {//		cout << root->_kv.first << " 平衡因子异常" << endl;//		return false;//	}//	// 递归检查左右子树//	return _IsBalance(root->_left) && _IsBalance(root->_right);//}//更优秀的平衡函数bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}//是否平衡判断函数bool IsBalance(){int height = 0;return _IsBalance(_root, height);}//计算树的节点个数size_t Size(){return _Size(_root);}size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}//查找函数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 NULL;}
private://成员变量_root根节点Node* _root = nullptr;
};

四：AVL树代码的测试

①：平衡函数的测试

void TestAVLTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : a){cout << e << "->" << t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}

运行结果：

完美~ 

②：代码总体的测试 一百万个数据

void TestAVLTree2()
{//将一百万个数放进v数组中const int N = 1000000;vector<int> v;v.reserve(N);//先预开辟一下srand(time(0));//for (size_t i = 0; i < N; i++){v.push_back(rand() + i);// 生成随机数并插入到 v 末尾； rand() 的范围有限（通常 0~32767），而 + i 可以扩展范围，降低重复概率。//cout << v.back() << endl;// 可取消注释以打印每个数}size_t begin2 = clock();//记录起始时间 begin2 AVLTree<int, int> t;for (auto e : v){//每个元素 e 作为 (key, value) 插入 AVLTreet.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();//记录结束时间 end2//插入 100 万个元素的总 CPU 时间（时钟周期）。cout << "Insert:" << end2 - begin2 << endl;cout << "是否平衡:" << t.IsBalance() << endl;// 检查是否平衡cout << "Height:" << t.Height() << endl; // 输出树的高度cout << "Size:" << t.Size() << endl;// 输出树的节点数size_t begin1 = clock();//记录起始时间begin1// 在AVL树中查找所有已存在的值for (auto e : v){t.Find(e);}// 查找随机值（可能不存在）for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();//记录结束时间end1//end1 - begin1: 执行 200 万次查找（100 万成功 + 100 万随机）的 CPU 时间。cout << "Find:" << end1 - begin1 << endl;
}

运行结果：

Debug版本：

Release版本：

能看出，AVL树是一个十分优秀的结构！

为什么插入一百万数据 ，最终size只有六十三万，因为随机数有重复数据，AVL树底层是搜索二叉树，不会存在重复数据~~