引入：为何要有AVL树，二次搜索树有什么不足？
二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此产生了AVL树，该结构对二叉树进行了平衡处理，AVL树的时间复杂度永远为O(logn)
下图为二叉搜索树退化为单支树的场景：
一：AVL树的概念
如果一棵二叉搜索树是高度平衡的(树中任意一颗子树的左右子树高度差不超过1)，它就是AVL树。
且一颗AVL树具有以下性质：它的左右子树都是AVL树
这不纯纯废话吗，树中任意一颗子树的左右子树高度差不超过1，那每颗子树不都是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：
p->bf == 0说明：更新前
p->bf为1或-1，插入操作使较矮的一侧子树高度增加，p的左右子树变得平衡。影响：以
p为根节点的这颗树高度不变，因此不会影响更高层祖先节点的平衡因子。操作：终止更新祖先节点的_bf。
情况 2：
p->bf == 1或p->bf == -1说明：更新前
p->bf为0，插入操作使某一侧子树高度增加。影响：
p的子树高度变化，会影响其父节点的平衡因子。操作：继续向上更新祖先节点。
情况 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的bf
if (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：左单旋
新节点插入较高右子树的右侧-->需要 左单旋
如图：
其中的a b c 是一颗子树的抽象图 一开始abc都是高度为h的子树
有同学就要问了，直接举例子不好吗？为什么要用抽象图？
因为例子多到数不过来，用单一的例子反而不能代表全部情况，用抽象图更好
对上图的左单旋再画图讲解：
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的bf
if (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 == 1
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
// 右旋转
// 触发条件：parent->_bf == -2 && cur->_bf == -1
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
// 左右旋转
// 触发条件：parent->_bf == -2 && cur->_bf == 1
else 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 factor
pair<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的bf
if (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 == 1
if (parent->_bf == 2 && cur->_bf == 1)
{
RotateL(parent);
}
// 右旋转
// 触发条件：parent->_bf == -2 && cur->_bf == -1
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
// 左右旋转
// 触发条件：parent->_bf == -2 && cur->_bf == 1
else 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) 插入 AVLTree
t.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树底层是搜索二叉树，不会存在重复数据~~