前言
在文章的开头之前，容许我叨叨几句：有一说一，我感觉上次这么认真写文章还是6,7月份，当时还是我大二，刚开始我本来计划暑假天天写文章的，但是由于我爱玩（不演了），结果导致我的学习进度直接落下了，并且博客也是一篇没写，现在我开学了，对此我深恶痛心，于是决定恢复博客的更新进展，并且立下目标：九月份写满十篇文章！那么废话不多说，开启我们今天的博客之旅~
1.AVL树的旋转
1.1.友情提示
可能刚看我博客的读者会觉得我上来就讲旋转比较奇怪，这里我解释一下：我之前就写过AVL树的文章，由于当时我的精力不足，于是把一篇文章分成了两篇来书写（总结一句话就是太懒了），所以说如果看不懂的读者可以点开我的主页去查看我之前写的文章。
1.2.旋转的原则
首先旋转肯定是要保证搜索树的规则，也就是左节点比根节点小，右节点比根节点大（忘记的读者，立即推，复习到凌晨两点）。
之后我们需要让旋转的树从不满足变平衡，并且要降低树的高度。旋转一共分为四种，分别是：左单旋，右单旋，左右双旋，右左双旋。下面我将会一一讲解。
2.右单旋
2.1.右单旋的讲解
上图展示的是以10为根的树，它分别有a，b，c三颗高度为h的抽象树（其中h>=0），并且这三兄弟都符合AVL树的要求。10可能是整棵树的根，也可能是⼀个整棵树中局部的⼦树的根。这⾥a/b/c是高度为h的子树，是⼀种概括抽象表⽰，他代表了所有右单旋的场景。
我们先仔细看上图，其中假设我们往a子树插入一个节点，就导致10这个节点的平衡因子变为-2，这样是不符合AVL树的规则的，所以我们需要通过旋转来让树变的再次平衡，旋转的方法是很简单的，假设此时我们用手按住10这个节点，此时我们用手把10按下去，就会导致5变为新的局部根节点（因此此时上面并不一定就是一颗完整的树，还可能是别的树的一部分，之后我们在把原来5节点的右子树放到10节点的左边，经过这样的操作，我们就完成了对于一颗不平衡树的右单旋，经过这样的操作以后，我们就可以把不平衡的树变的平衡，并且如果这是一颗大树的一部分，此时旋转以后不会影响上一层，此时插入结束，这就是AVL树的右单旋操作。下面我用一个简单的例子来为各位更好的解释右单旋操作。
如上图所示，左边是一颗平衡的AVL树，此时我们往1节点的左边插入一个节点，这样就导致10这个节点的平衡因子更新为-2，经过如此操作这棵树就破坏了AVL树的规则，我们必须通过旋转来改变上面树的结构，此时由于是左边太高了，所以我们需要通过往右旋转让树按照AVL树的规则进行树的调整。
此时我们需要让10这个节点作为5这个节点的右子树，并且把原来5这个节点的右子树放到10这个节点的左边，如上所示，此时我们就完成了一次右单旋。此时不难发现，在经过旋转以后，原来的局部根节点的平衡因子和其左孩子的平衡因子都变为0了。
下面我总结了两张关于右单旋的抽象图，各位如果有兴趣的话可以看看下面这个图。
其实右单旋的难度不算很大，下面我来进行代码书写的讲解。
2.2.代码讲解
此时我们把函数名直接写作：RotateR，代表着往右旋转，里面的参数代表着子树的根节点，如下所示：
void RotateR(Node* parent); //里面代表着父节点，就是类似上面例子的10节点 之后我们进行旋转处理：先把父节点(简称为P节点)的左孩子节点（subL）以及左孩子节点的右孩子节点(subLR)表示出来，表示出来以后，我们需要把subLR节点放到P节点的左孩子节点出，并且我们还需判断此时的subLR节点是否存在，如果存在的话，那么让其的父节点变为P节点，此时就完成了subLR的放置，其代码如下所示：
//进行旋转处理
Node* subl = parent->_left; //将来要成为父亲的
Node* sublR = subl->_right;
parent->_left = sublR;
if (sublR)
{
//如果这个结点存在的话，让它的父亲结点成为parent
sublR->_parent = parent;
} 做完上面操作以后，我们就需要进行旋转操作了，此时我们需要显示出P节点的父亲节点（简称为PP节点），表示出PP节点的原因是因为我们之后是重新定义好局部子树的根节点，此时这个根节点的父亲必须是其上层子树的节点，这样可以保证整棵树的结构不被破坏。之后我们需要让subL的右子树节点变为P节点，P节点的父亲节点变为subL；然后我们需要检测PP节点是否为空（因为此时P节点所在的树可能就是一棵完整的树），如果不为空的话，我们需要判断PP节点存的值和subL值的比较，以此来判断subL节点是PP节点的左孩子节点还是右孩子节点；如果为空的话，那么就很简单了，我们仅需让subL的父节点变为空，并且让其成为根节点即可。下面展示代码的书写（最后不要忘记平衡因子的更新）。
//此时需要先把P的父亲结点保存起来
Node* ppnode = parent->_parent;
subl->_right = parent;
parent->_parent = subl;
if (ppnode == nullptr)
{
_root = subl; //证明刚才要调整的parent就是根节点
subl->_parent = ppnode;
}
else
{
if (subl->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subl;
}
else
{
ppnode->_left = subl;
}
subl->_parent = ppnode;
}
//更新一下平衡因子
parent->_bf = 0;
subl->_bf = 0;2.3.完整代码展示
//旋转方法私有化，就不暴露隐私
void RotateR(Node* parent)
{
//进行旋转处理
Node* subl = parent->_left; //将来要成为父亲的
Node* sublR = subl->_right;
parent->_left = sublR;
if (sublR)
{
//如果这个结点存在的话，让它的父亲结点成为parent
sublR->_parent = parent;
}
//此时需要先把P的父亲结点保存起来
Node* ppnode = parent->_parent;
subl->_right = parent;
parent->_parent = subl;
if (ppnode == nullptr)
{
_root = subl; //证明刚才要调整的parent就是根节点
subl->_parent = ppnode;
}
else
{
if (subl->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subl;
}
else
{
ppnode->_left = subl;
}
subl->_parent = ppnode;
}
//更新一下平衡因子
parent->_bf = 0;
subl->_bf = 0;
} 3.左单旋
3.1.左单旋的讲解
左单旋其实和右单旋差不多，无非就是旋转的方向不一致，右单旋是往右边旋转，也就是一只无形的大手把局部根节点压到右边，并且把原来局部根节点的右子树节点放到之前局部根节点的左边，而左单旋恰恰相反，它是一只无形的大手把局部根节点压到左边，并且把原来局部根节点的右节点的左子树放到局部根节点的右边，具体的操作原则如下所示。
3.2.代码讲解
和右单旋一样，此时我们需要定义好左单旋函数的名字已经相对应的参数。
void RotateL(Node* parent) 之后我们需要定义好局部根节点的右节点（subR），以及右节点的左节点（subRL），而且可以提前把PP节点表示出来：
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* ppnode = parent->_parent; 之后我们需要进行旋转操作了，先让P节点的右孩子变为subRL，并且需要判断此时的subRL是否为空，如果不为空的话，让subRL的父节点变为P节点，之后让subR的左孩子变为P节点，并且让P节点的父节点变为subR，之后我们需要判断PP节点是否为空，如果不为空的话，依旧需要比较PP节点存放的Key和subR的Key的大小，由此来确定subR应该是PP节点的左孩子还是右孩子；如果为空的话，那么直接让subR节点变为root节点即可，之后让subR的父节点为空即可（不要忘记平衡因子的更新）。
Node* ppnode = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
//开启最复杂的一集
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (subR->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subR;
}
else
{
ppnode->_left = subR;
}
subR->_parent = ppnode; //这个忘加了，想事要想全，这点我确实是大意了
}
parent->_bf = 0;
subR ->_bf = 0;### 3.3.完整代码
Node* ppnode = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
//开启最复杂的一集
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (subR->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subR;
}
else
{
ppnode->_left = subR;
}
subR->_parent = ppnode; //这个忘加了，想事要想全，这点我确实是大意了
}
parent->_bf = 0;
subR ->_bf = 0;4.左右双旋
4.1.左右双旋的讲解
当我们向某节点（记作A）的左子树（记作B）的右侧插入一个新节点时，就有可能导致如上图一所示的不平衡情况。此时，节点A的平衡因子为+2，其左子树B的平衡因子为-1，明显违反了AVL树的平衡规则。
如果此时仅进行一次右单旋，旋转后会发现：不仅没有恢复树的平衡，反而可能导致整个结构向右倾斜加剧，右子树高度进一步增加。这表明，仅靠单次旋转已无法解决此类不平衡问题。
针对这种“左子树的右侧插入”场景，我们需要采用左右双旋（先左旋后右旋）的方式，分两步调整结构，才能有效地使树恢复平衡。
具体的左右双旋如上所示，可能不少读者看到这么多的内容，直接想：立即推，放弃AVL树！各位，可千万不要这么想，其实左右双旋也是比较简单的，我们就先拿最下面的例子（场景三）为例进行讲解。
此时b的位置是没有节点的，即h==0，当我们往右边插入节点的时候，此时就会导致整棵树不符合AVL树的规则，所以我们需要先进行一次左单旋，以5这个节点为中心进行一次旋转；旋转过后subLR这个节点就代替了subL的位置，并且subL变为了subLR的左孩子，这个时候这个树的整体构造就变成了右单旋处理的情况，我们在进行一次右单旋即可，旋转过后，整棵树就变的符合AVL树的结构了，并且subLR、subL，P节点的平衡因子都更新为0，这是左右双旋我认为最简单的一个场景，下面我们进行复杂场景的讲解。
对于场景2，此时b的位置是有节点的，此时我们往subLR的右孩子处插入一个节点，这个时候P节点的平衡因子变为了-2，不符合AVL树的规则，所以我们需要进行旋转操作，这个时候其实整体还是和上面的场景三是一样的，所以旋转的细节我就不讲述了，我简单的讲述平衡因子的更新，通过上图可以清晰的知道，此时subLR和P节点的平衡因子都被更新为0了，而subL的平衡因子更新为了-1（这里可以生动的体现出编程画图的重要性）。
对于场景一，其中的旋转操作我也是不讲述了，看图就可以清晰的看出来，此时我们仅需关注一下平衡因子如何更新就好，此时的P节点的平衡因子变为了-1，而其余两个节点的平衡因子都变为了0。这便是对于AVL的讲述，下面我们进行代码书写的讲述。
4.2.代码讲解
左右双旋的代码我认为是比较容易的，因为我们之前就实现了两个单旋，所以我们想要实现左右双旋，我们仅需直接复用这两个函数即可，其函数名，参数以及函数复用代码如下：
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
} 之后我们需要进行平衡因子的更新，通过对于上图的观察，相信聪明的你可以知道仅需通过观察subLR的平衡因子就可以知晓如何进行三个节点平衡因子更新。
int bf = subLR->_bf; // 保存原始平衡因子
RotateL(subL);
RotateR(parent);
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if(bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}4.3.完整代码
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; // 保存原始平衡因子
RotateL(subL);
RotateR(parent);
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if(bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
}5.右左双旋
5.1.右左双旋的讲解
右左双旋其实和左右双旋是差不多的，他俩的差别就是旋转的顺序不同，右左双旋一般出现在右子树变的很高，但是新增的节点却在右孩子的左边这种情况，这个时候简单的左单旋是完成不了树的矫正的，我们需要通过右左双旋，即先进行右单旋在进行左单旋的方式进行树的矫正。
如上图所示，此时这个图就形象的展现出了右左双旋的各种场景，因为前面我已经讲述了左右双旋，所以我并不在进行详细的讲解了，如果各位读者有不懂的话，可以主页加我微信询问我（私信我不怎么常看）。我就简单的讲述一下平衡因子的更新了。
场景1：h >= 1时，新增结点插⼊在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因⼦，引发旋转，其中12的平衡因⼦为-1，旋转后10和12平衡因子为0，15平衡因子为1。
场景2：h >= 1时，新增结点插⼊在f子树，f子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，其中12的平衡因子为1，旋转后15和12平衡因子为0，10平衡因子为-1。
场景3：h == 0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新15->10平衡因⼦，引发旋转，其中12的平衡因子为0，旋转后10和12和15平衡因子均为0。
5.2.完整代码
我感觉双旋代码都差不多，所以我直接给出完整代码了，不过友情建议：各位读者最好看着我上面的图自己先尝试代码的书写再来看我写的代码。
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//平衡节点的更新
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}6.AVL树的查找
6.1.讲解
AVL树的查找和普通的二叉搜索树的查找差不多，我们仅需根据平衡二叉树的规则：左孩子比根节点小，右节点比根节点大的特性，进行相关值的查询即可。
6.2.代码
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}7.AVL树的平衡检测
此时读者根据我下面的代码进行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);
} // 测试代码
void TestAVLTree1()
{
AVLTree<int, int> t;
// 常规的测试⽤例
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试⽤例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
t.Insert({ e, e });
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
} // 插⼊⼀堆随机值，测试平衡，顺便测试⼀下⾼度和性能等
void TestAVLTree2()
{
const int N = 100000;
vector<int> v;
v.reserve(N);
srand(time(0));
for (size_t i = 0; i < N; i++)
{
v.push_back(rand()+i);
}
size_t begin2 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
size_t end2 = clock();
cout << "Insert:" << end2 - begin2 << endl;
cout << t.IsBalanceTree() << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
size_t begin1 = clock();
// 确定在的值
/*for (auto e : v)
{
t.Find(e);
}*/
// 随机值
for (size_t i = 0; i < N; i++)
{
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
} 8.AVL树的删除
由于我比较菜（不演了），所以删除我还没有掌握，期待将来的某一天，我可以将其掌握。
9.AVL树的完整代码（很长，有点凑字数嫌疑~）
#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<assert.h>
//这里开始进行AVL树的实现，直接实现一个KV的平衡二叉树
using namespace std;
namespace wang
{
template<class K, class V>
struct AVLTreeNode
{
// 需要parent指针，后续更新平衡因子可以看到
pair<K, V> _kv;
AVLTreeNode<K, V>* _left; //三叉连，左节点
AVLTreeNode<K, V>* _right; //右节点
AVLTreeNode<K, V>* _parent; //父结点
int _bf; // balance factor
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:
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 (kv.first < cur->_kv.first)
{
//比节点的值小，往左边走
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first)
{
parent = cur;
cur = cur->_right;
}
else
{
return false; //不能出现相同的结点
}
}
//找到节点了
cur = new Node(kv);
cur->_parent = parent; // 必须让新节点知道父节点是谁
if (kv.first > parent->_kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
//更新平衡因子
while (parent)
{
if (cur == parent->_right)
{
parent->_bf++; //右边的平衡因子加一
}
else
{
parent->_bf--; //左边的平衡因子减一
}
//开始判断此时的平衡因子是否往上走
if (parent->_bf == 0)
{
//太平衡了，循环结束
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上面进行调整
cur = parent;
parent = parent->_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
{
//不合理了这样就
cerr << "二叉树弄错了中间有一步，还没有进行旋转" << endl;
return false;
}
}
return true;
}
void InOrder()
{
_InOrder(_root);
}
//查找
Node* Find(const K& key)
{
Node* cur = _root; //让根保持原样
while (cur)
{
if (cur->_kv.first > key)
{
cur = cur->_left;
}
else if (cur->_kv.first < key)
{
cur = cur->_right;
}
else
{
return cur;
}
}
//走到这说明没找到
//cout << "没有找到，您可以插入这个结点";
return nullptr;
}
//删比较麻烦，叉掉
int Height()
{
return _Height(_root);
}
int Size()
{
return _Size(_root);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
private:
//旋转方法私有化，就不暴露隐私
void RotateR(Node* parent)
{
//进行旋转处理
Node* subl = parent->_left; //将来要成为父亲的
Node* sublR = subl->_right;
parent->_left = sublR;
if (sublR)
{
//如果这个结点存在的话，让它的父亲结点成为parent
sublR->_parent = parent;
}
//此时需要先把P的父亲结点保存起来
Node* ppnode = parent->_parent;
subl->_right = parent;
parent->_parent = subl;
if (ppnode == nullptr)
{
_root = subl; //证明刚才要调整的parent就是根节点
subl->_parent = ppnode;
}
else
{
if (subl->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subl;
}
else
{
ppnode->_left = subl;
}
subl->_parent = ppnode;
}
//更新一下平衡因子
parent->_bf = 0;
subl->_bf = 0;
}
void RotateL(Node* parent)
{
//左单旋处理
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* ppnode = parent->_parent;
parent->_right = subRL;
if (subRL)
{
subRL->_parent = parent;
}
//开启最复杂的一集
subR->_left = parent;
parent->_parent = subR;
if (ppnode == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (subR->_kv.first > ppnode->_kv.first)
{
ppnode->_right = subR;
}
else
{
ppnode->_left = subR;
}
subR->_parent = ppnode; //这个忘加了，想事要想全，这点我确实是大意了
}
parent->_bf = 0;
subR ->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; // 保存原始平衡因子
RotateL(subL);
RotateR(parent);
if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if(bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
//平衡节点的更新
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 1;
subRL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false);
}
}
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
int _Size(Node* root)
{
if (root == nullptr)
return 0;
return _Size(root->_left) + _Size(root->_right) + 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);
}
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;
}
private:
Node* _root = nullptr;
};
// 测试代码
void TestAVLTree1()
{
AVLTree<int, int> t;
// 常规的测试用例
//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
// 特殊的带有双旋场景的测试用例
int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };
for (auto e : a)
{
if (e == 14)
{
int x = 0;
}
t.Insert({ e, e });
cout << "Insert:" << e << "->";
cout << t.IsBalanceTree() << endl;
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
}
// 插入一堆随机值，测试平衡，顺便测试一下高度和性能等
void TestAVLTree2()
{
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);
}
size_t begin2 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
}
size_t end2 = clock();
cout << t.IsBalanceTree() << endl;
cout << "Insert:" << end2 - begin2 << endl;
cout << "Height:" << t.Height() << endl;
cout << "Size:" << t.Size() << endl;
size_t begin1 = clock();
// 确定在的值
/*for (auto e : v)
{
t.Find(e);
}*/
// 随机值
for (size_t i = 0; i < N; i++)
{
t.Find((rand() + i));
}
size_t end1 = clock();
cout << "Find:" << end1 - begin1 << endl;
}
}
9.小结
芜湖~我终于结束了AVL树的讲解了，我终于在三个月后完成了一篇博客了，我终于不在懈怠了（三连终于），我宣布，从今天开始，我将开始正式的恢复博客的更新，今年也是马上要结束了，我也准备给自己定下一个小小的目标：粉丝突破万粉！希望我在2025年可以达成这个成就，如果文章有错误，可以在评论区直接批评我，毕竟三个月不写博客了，手有点生疏了，错别字应该有不少，那么各位大佬们，我们下一篇文章见啦！
