目录
1.AVL树的概念
二叉搜索树虽然可以提高我们查找数据的效率，但如果插入二叉搜索树的数据是有序或接近有序的，此时二叉搜索树会退化为单支树，在单支树当中查找数据相当于在单链表当中查找数据，效率是很低下的。
因此，两位俄罗斯的数学家G.M.A delson-Velskii和E.M.Landis在1962年发明了解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。
AVL树是最先发明的⾃平衡⼆叉查找树，AVL是⼀颗空树，或者具备下列性质的⼆叉搜索树：它的 左右⼦树都是AVL树，且左右⼦树的⾼度差的绝对值不超过1。AVL树是⼀颗⾼度平衡搜索⼆叉树， 通过控制⾼度差去控制平衡。
这⾥我们引⼊⼀个平衡因⼦(balancefactor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1， AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡， 就像⼀个⻛向标⼀样。
如果一棵二叉搜索树的高度是平衡的，它就是AVL树。如果它有n个结点，其高度可保持O(logN)，搜索时间复杂度也是O(logN)。
注意： 这里所说的二叉搜索树的高度是平衡的是指，树中每个结点左右子树高度之差的绝对值不超过1，因为只有满二叉树才能做到每个结点左右子树高度之差均为0。
2.AVL树的实现
2.1 AVL树结点的定义
我们这里直接实现KV模型的AVL树，为了方便后续的操作，这里将AVL树中的结点定义为三叉链结构，并在每个结点当中引入平衡因子（右子树高度-左子树高度）。除此之外，还需编写一个构造新结点的构造函数，由于新构造结点的左右子树均为空树，于是将新构造结点的平衡因子初始设置为0即可。
template<class K,class V>
class AVTreeNode
{
//三叉链
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
//存储的键值对
pair<K, V> _kv;
//平衡因子(balance factor)
int _bf; //右子树高度-左子树高度
//构造函数
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};2.2 AVL树的插入
AVL树插入结点时有以下三个步骤：
- 按照二叉搜索树的插入方法，找到待插入位置。
- 找到待插入位置后，将待插入结点插入到树中。
- 更新平衡因子，如果出现不平衡，则需要进行旋转。
因为AVL树本身就是一棵二叉搜索树，因此寻找结点的插入位置是非常简单的，按照二叉搜索树的插入规则：
- 待插入结点的key值比当前结点小就插入到该结点的左子树。
- 待插入结点的key值比当前结点大就插入到该结点的右子树。
- 待插入结点的key值与当前结点的key值相等就插入失败。
如此进行下去，直到找到与待插入结点的key值相同的结点判定为插入失败，或者最终走到空树位置进行结点插入。
与二叉搜索树插入结点不同的是，AVL树插入结点后需要更新树中结点的平衡因子，因为插入新结点后可能会影响树中某些结点的平衡因子。
由于一个结点的平衡因子是否需要更新，是取决于该结点的左右子树的高度是否发生了变化，因此插入一个结点后，该结点的祖先结点的平衡因子可能需要更新。
所以我们插入结点后需要倒着往上更新平衡因子，更新规则如下：
新增结点在parent的右边，parent的平衡因子++。
新增结点在parent的左边，parent的平衡因子--。
每更新完一个结点的平衡因子后，都需要进行以下判断：
如果parent的平衡因子等于-1或者1，表明还需要继续往上更新平衡因子。
如果parent的平衡因子等于0，表明无需继续往上更新平衡因子了。
如果parent的平衡因子等于-2或者2，表明此时以parent结点为根结点的子树已经不平衡了，需要进行旋转处理。
而在最坏情况下，我们更新平衡因子时会一路更新到根结点。例如下面这种情况：
说明一下： 由于我们插入结点后需要倒着往上进行平衡因子的更新，所以我们将AVL树结点的结构设置为了三叉链结构，这样我们就可以通过父指针找到其父结点，进而对其平衡因子进行更新。当然，我们也可以不用三叉链结构，可以在插入结点时将路径上的结点存储到一个栈当中，当我们更新平衡因子时也可以通过这个栈来更新祖先结点的平衡因子，但是相对较麻烦。
若是在更新平衡因子的过程当中，出现了平衡因子为-2/2的结点，这时我们需要对以该结点为根结点的树进行旋转处理，而旋转处理分为四种，在进行分类之前我们首先需要进行以下分析：
我们将插入结点称为cur，将其父结点称为parent，那么我们更新平衡因子时第一个更新的就是parent结点的平衡因子，更新完parent结点的平衡因子后，若是需要继续往上进行平衡因子的更新，那么我们必定要执行以下逻辑：
cur = parent;
parent = parent->_parent;
这里我想说明的是：当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
理由如下：
若cur的平衡因子是0，那么cur一定是新增结点，而不是上一次更新平衡因子时的parent，否则在上一次更新平衡因子时，会因为parent的平衡因子为0而停止继续往上更新。
而cur是新增结点的话，其父结点的平衡因子更新后一定是-1/0/1，而不可能是-2/2，因为新增结点最终会插入到一个空树当中，在新增结点插入前，其父结点的状态有以下两种可能：
其父结点是一个左右子树均为空的叶子结点，其平衡因子是0，新增结点插入后其平衡因子更新为-1/1。
其父结点是一个左子树或右子树为空的结点，其平衡因子是-1/1，新增结点插入到其父结点的空子树当中，使得其父结点左右子树当中较矮的一棵子树增高了，新增结点后其平衡因子更新为0。
综上所述，当parent的平衡因子为-2/2时，cur的平衡因子必定是-1/1而不会是0。
根据此结论，我们可以将旋转处理分为以下四类：
- 当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
- 当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
- 当parent的平衡因子为2，cur的平衡因子为-1时，进行右左双旋。
- 当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。
并且，在进行旋转处理后就无需继续往上更新平衡因子了，因为旋转后树的高度变为插入之前了，即树的高度没有发生变化，也就不会影响其父结点的平衡因子了。具体原因请看后面的旋转讲解。
//插入函数
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr) //若AVL树为空树，则插入结点直接作为根结点
{
_root = new Node(kv);
return true;
}
//1、按照二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //待插入结点的key值等于当前结点的key值
{
//插入失败（不允许key值冗余）
return false;
}
}
//2、将待插入结点插入到树中
cur = new Node(kv); //根据所给值构造一个新结点
if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
{
//插入到parent的左边
parent->_left = cur;
cur->_parent = parent;
}
else //新结点的key值大于parent的key值
{
//插入到parent的右边
parent->_right = cur;
cur->_parent = parent;
}
//3、更新平衡因子，如果出现不平衡，则需要进行旋转
while (cur != _root) //最坏一路更新到根结点
{
if (cur == parent->_left) //parent的左子树增高
{
parent->_bf--; //parent的平衡因子--
}
else if (cur == parent->_right) //parent的右子树增高
{
parent->_bf++; //parent的平衡因子++
}
//判断是否更新结束或需要进行旋转
if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
{
break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
}
else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
{
//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
{
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);
}
else
{
assert(false);
}
break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了)
}
else
{
assert(false); //在插入前树的平衡因子就有问题
}
}
return true; //插入成功
}2.3AVL树的旋转
右单旋
当parent的平衡因子为-2，cur的平衡因子为-1时，进行右单旋。
所谓的旋转就是把高的那一边往低的那一边压下去，右单旋就是左高右低的一棵树，把它往右旋转，我们看一下旋转示意图。
我们可以看到，经过右旋之后，我们树的高度相比于插入前并没有发生变化，那么平衡因子也就无需向上继续更新。
右单旋的步骤如下：
让subL的右子树作为parent的左子树。
让parent作为subL的右子树。
让subL作为整个子树的根。
更新平衡因子。
右单旋后满足二叉搜索树的性质：
subL的右子树当中结点的值本身就比parent的值小，因此可以作为parent的左子树。
parent及其右子树当中结点的值本身就比subL的值大，因此可以作为subL的右子树。
代码如下：
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//1、建立subL和parent之间的关系
subL->_right = parent;
parent->_parent = subL;
//2、建立parent和subLR之间的关系
parent->_left = subLR;
if (subLR)//subLR是可能为空的
subLR->_parent = parent;
//3、建立parentParent和subL之间的关系
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else //parent == parentParent->_right
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
//4、更新平衡因子
subL->_bf = parent->_bf = 0;
}
左单旋
当parent的平衡因子为2，cur的平衡因子为1时，进行左单旋。
了解了右单旋，那么左单旋也是类似的。我们直接看旋转示意图。
可以看到，经过左单旋后，树的高度变为插入之前了，树的高度没有发生变化，那么左单旋后无需继续往上更新平衡因子。
左单旋的步骤如下：
让subR的左子树作为parent的右子树。
让parent作为subR的左子树。
让subR作为整个子树的根。
更新平衡因子。
左单旋后满足二叉搜索树的性质：
subR的左子树当中结点的值本身就比parent的值大，因此可以作为parent的右子树。
parent及其左子树当中结点的值本身就比subR的值小，因此可以作为subR的左子树。
代码示例：
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//1、建立subR和parent之间的关系
parent->_parent = subR;
subR->_left = parent;
//2、建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//3、建立parentParent和subR之间的关系
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr; //subR的_parent指向需改变
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else //parent == parentParent->_right
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
//4、更新平衡因子
subR->_bf = parent->_bf = 0;
}
左右双旋
当parent的平衡因子为-2，cur的平衡因子为1时，进行左右双旋。
左右单旋只能解决一边高的问题，有时我们只有一个单旋并不足以解决问题，看下图。
我们插入8之后, a节点的平衡因子就变成了-2,意味着左边高，那么我们需要进行右旋，将c变为a的左子树,a变为b的右子树，发现旋转之后依然不符合AVL树结构。那么这里就需要我们的左右双旋来处理这种情况，上图就是左右双旋的一个特例。
左右双旋示例图：
左右双旋的步骤如下：
以subL为旋转点进行左单旋。
以parent为旋转点进行右单旋。
更新平衡因子。
左右双旋后满足二叉搜索树的性质：
左右双旋后，实际上就是让subLR的左子树和右子树，分别作为subL和parent的右子树和左子树，再让subL和parent分别作为subLR的左右子树，最后让subLR作为整个子树的根（结合图理解）。
1.subLR的左子树当中的结点本身就比subL的值大，因此可以作为subL的右子树。
2.subLR的右子树当中的结点本身就比parent的值小，因此可以作为parent的左子树。
经过步骤1/2后，subL及其子树当中结点的值都就比subLR的值小，而parent及其子树当中结点的值都就比subLR的值大，因此它们可以分别作为subLR的左右子树。
左右双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1、当subLR原始平衡因子是-1时，左右双旋后parent、subL、subLR的平衡因子分别更新为1、0、0。
2、当subLR原始平衡因子是1时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、-1、0。
3、当subLR原始平衡因子是0时，左右双旋后parent、subL、subLR的平衡因子分别更新为0、0、0。
可以看到，经过左右双旋后，树的高度变为插入之前了，因为的高度没有发生变化，所以左右双旋后无需继续往上更新平衡因子。
代码如下：
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1
//1、以subL为旋转点进行左单旋
RotateL(subL);
//2、以parent为旋转点进行右单旋
RotateR(parent);
//3、更新平衡因子
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false); //在旋转前树的平衡因子就有问题
}
}
右左双旋
这里和上面也类似，我们直接看旋转示意图即可理解。
右左双旋的步骤如下：
以subR为旋转点进行右单旋。
以parent为旋转点进行左单旋。
更新平衡因子。
右左双旋后满足二叉搜索树的性质：
右左双旋后，实际上就是让subRL的左子树和右子树，分别作为parent和subR的右子树和左子树，再让parent和subR分别作为subRL的左右子树，最后让subRL作为整个子树的根（结合图理解）。
1.subRL的左子树当中的结点本身就比parent的值大，因此可以作为parent的右子树。
2.subRL的右子树当中的结点本身就比subR的值小，因此可以作为subR的左子树。
经过步骤1/2后，parent及其子树当中结点的值都就比subRL的值小，而subR及其子树当中结点的值都就比subRL的值大，因此它们可以分别作为subRL的左右子树。
右左双旋后，平衡因子的更新随着subLR原始平衡因子的不同分为以下三种情况：
1、当subRL原始平衡因子是1时，左右双旋后parent、subR、subRL的平衡因子分别更新为-1、0、0。
2、当subRL原始平衡因子是-1时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、1、0。
3、当subRL原始平衡因子是0时，左右双旋后parent、subR、subRL的平衡因子分别更新为0、0、0。
可以看到，经过右左双旋后，树的高度变为插入之前了，因为的高度没有发生变化，所以右左双旋后无需继续往上更新平衡因子。
代码如下：
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
//1、以subR为轴进行右单旋
RotateR(subR);
//2、以parent为轴进行左单旋
RotateL(parent);
//3、更新平衡因子
if (bf == 1)
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false); //在旋转前树的平衡因子就有问题
}
}
2.4 AVL树的查找
AVL树的查找函数与二叉搜索树的查找方式一模一样，逻辑如下：
若树为空树，则查找失败，返回nullptr。
若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
若key值等于当前结点的值，则查找成功，返回对应结点。
代码如下：
//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first) //key值小于该结点的值
{
cur = cur->_left; //在该结点的左子树当中查找
}
else if (key > cur->_kv.first) //key值大于该结点的值
{
cur = cur->_right; //在该结点的右子树当中查找
}
else //找到了目标结点
{
return cur; //返回该结点
}
}
return nullptr; //查找失败
}
2.5 AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，也就是说AVL树也是二叉搜索树，因此我们可以先获取二叉树的中序遍历序列，来判断二叉树是否为二叉搜索树。
但中序有序只能证明是二叉搜索树，要证明二叉树是AVL树还需验证二叉树的平衡性，在该过程中我们可以顺便检查每个结点当中平衡因子是否正确。
采用后序遍历，变量步骤如下：
从叶子结点处开始计算每课子树的高度。（每棵子树的高度 = 左右子树中高度的较大值 + 1）
先判断左子树是否是平衡二叉树。
再判断右子树是否是平衡二叉树。
若左右子树均为平衡二叉树，则返回当前子树的高度给上一层，继续判断上一层的子树是否是平衡二叉树，直到判断到根为止。（若判断过程中，某一棵子树不是平衡二叉树，则该树也就不是平衡二叉树了）
int _Height(Node* root)
{
if (root == nullptr)
return 0;
// 左右子树较高树的高度+1
return max(_Height(root->_left), _Height(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);
}
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;
}2.6 AVL树的性能测验
给两段测验代码
// 测试代码
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;
}
/*if (e == 11)
{
int x = 0;
}*/
t.Insert({ e, e });
cout << "Insert:" << e << "->";
cout << t.IsBalanceTree() << endl;
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
cout << "Size:" << t.Size() << 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);
}
cout << "v.size:" << v.size() << endl;
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;
}
六十多万个节点查询只需要506ms，速度是相当的快了。
3. 全部代码
#pragma once
#include <iostream>
#include <assert.h>
#include <vector>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
//三叉链
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
//存储的键值对
pair<K, V> _kv;
//平衡因子(balance factor)
int _bf; //右子树高度-左子树高度
//构造函数
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _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) //若AVL树为空树，则插入结点直接作为根结点
{
_root = new Node(kv);
return true;
}
//1、按照二叉搜索树的插入方法，找到待插入位置
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (kv.first < cur->_kv.first) //待插入结点的key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (kv.first > cur->_kv.first) //待插入结点的key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //待插入结点的key值等于当前结点的key值
{
//插入失败（不允许key值冗余）
return false;
}
}
//2、将待插入结点插入到树中
cur = new Node(kv); //根据所给值构造一个新结点
if (kv.first < parent->_kv.first) //新结点的key值小于parent的key值
{
//插入到parent的左边
parent->_left = cur;
cur->_parent = parent;
}
else //新结点的key值大于parent的key值
{
//插入到parent的右边
parent->_right = cur;
cur->_parent = parent;
}
//3、更新平衡因子，如果出现不平衡，则需要进行旋转
while (cur != _root) //最坏一路更新到根结点
{
if (cur == parent->_left) //parent的左子树增高
{
parent->_bf--; //parent的平衡因子--
}
else if (cur == parent->_right) //parent的右子树增高
{
parent->_bf++; //parent的平衡因子++
}
//判断是否更新结束或需要进行旋转
if (parent->_bf == 0) //更新结束（新增结点把parent左右子树矮的那一边增高了，此时左右高度一致）
{
break; //parent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
}
else if (parent->_bf == -1 || parent->_bf == 1) //需要继续往上更新平衡因子
{
//parent树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == -2 || parent->_bf == 2) //需要进行旋转（此时parent树已经不平衡了）
{
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);
}
else
{
assert(false);
}
break; //旋转后就一定平衡了，无需继续往上更新平衡因子(旋转后树高度变为插入之前了)
}
else
{
assert(false); //在插入前树的平衡因子就有问题
}
}
return true; //插入成功
}
int Height()
{
return _Height(_root);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
void InOrder()
{
_InOrder(_root);
}
int Size()
{
return _Size(_root);
}
//查找函数
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_kv.first) //key值小于该结点的值
{
cur = cur->_left; //在该结点的左子树当中查找
}
else if (key > cur->_kv.first) //key值大于该结点的值
{
cur = cur->_right; //在该结点的右子树当中查找
}
else //找到了目标结点
{
return cur; //返回该结点
}
}
return nullptr; //查找失败
}
private:
//右单旋
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
//1、建立subL和parent之间的关系
subL->_right = parent;
parent->_parent = subL;
//2、建立parent和subLR之间的关系
parent->_left = subLR;
if (subLR)//subLR是可能为空的
subLR->_parent = parent;
//3、建立parentParent和subL之间的关系
if (parentParent == nullptr)
{
_root = subL;
_root->_parent = nullptr;
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subL;
}
else //parent == parentParent->_right
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
//4、更新平衡因子
subL->_bf = parent->_bf = 0;
}
//左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
//1、建立subR和parent之间的关系
parent->_parent = subR;
subR->_left = parent;
//2、建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
//3、建立parentParent和subR之间的关系
if (parentParent == nullptr)
{
_root = subR;
subR->_parent = nullptr; //subR的_parent指向需改变
}
else
{
if (parent == parentParent->_left)
{
parentParent->_left = subR;
}
else //parent == parentParent->_right
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
//4、更新平衡因子
subR->_bf = parent->_bf = 0;
}
//左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf; //subLR不可能为nullptr，因为subL的平衡因子是1
//1、以subL为旋转点进行左单旋
RotateL(subL);
//2、以parent为旋转点进行右单旋
RotateR(parent);
//3、更新平衡因子
if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
else if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 0)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 0;
}
else
{
assert(false); //在旋转前树的平衡因子就有问题
}
}
//右左双旋
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
//1、以subR为轴进行右单旋
RotateR(subR);
//2、以parent为轴进行左单旋
RotateL(parent);
//3、更新平衡因子
if (bf == 1)
{
subRL->_bf = 0;
parent->_bf = -1;
subR->_bf = 0;
}
else if (bf == -1)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 1;
}
else if (bf == 0)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false); //在旋转前树的平衡因子就有问题
}
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
// 左右子树较高树的高度+1
return max(_Height(root->_left), _Height(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);
}
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;
}
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 };
int a[] = { 9060,29915,9111 };
for (auto e : a)
{
if (e == 14)
{
int x = 0;
}
/*if (e == 11)
{
int x = 0;
}*/
t.Insert({ e, e });
cout << "Insert:" << e << "->";
cout << t.IsBalanceTree() << endl;
}
t.InOrder();
cout << t.IsBalanceTree() << endl;
cout << "Size:" << t.Size() << 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);
}
cout << "v.size:" << v.size() << endl;
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;
}
总结：
AVL树是一棵绝对平衡的二叉搜索树，其要求每个结点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 logN。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。
因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但当一个结构经常需要被修改时，AVL树就不太适合了。
本篇博客到此结束，欢迎各位评论区留言~