前言
之前我们讲解了二叉搜索树以及两种应用模型，key和key/value，但是二叉搜索树极端场景下会退化为单支树，所以二叉搜索树增删查改的时间复杂度是O(N)，进而引入了二叉平衡搜索树，进一步提高了搜索树的效率，那我们就来深入的研究一下AVL树
一、AVL树的概念
AVL树是最先发明的自平衡二叉查找树，AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1，AVL树是一颗高度平衡的搜索二叉树， 通过控制高度差去控制平衡。AVL树实现我们引入一个平衡因子的概念，每个结点都有一个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子都必须等于0/1/-1，AVL树并不是必须要平衡因子，也可以通过其他方式控制平衡，但是有了平衡因子可以更方便观察和控制树是否平衡。而且平衡因子的计算也可以左子树-右子树，我们在这里采用的是右子树-左子树。AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在logN ，那么增删查改的效率也可以控制在O(logN) ，相比二叉搜索树有了本质的提升。有些小伙伴在这里会有疑问，为什么AVL树是高度平衡搜索二叉树，要求高度差不超过1，而不是高度差是0呢？0不是最佳的平衡状态吗？通过画图分析我们发现，当偶数个节点的时候，无论如何也做不到高度差为0，只有奇数个节点的时候才能做到，所以是高度差不超过1就算是平衡状态了。
左图中，每一颗子树的平衡因子都满足要求，是一颗AVL树，右图中，10这个节点的平衡因子是2，需要通过旋转来变平衡，关于旋转在下面会详细讲，这里只是举个例子
二、AVL树的实现
2.1 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;
};基本框架就跟之前的二叉搜索树是一样的，这里直接用了一个key/value的模型，用pair这个结构把它们存了起来，然后用了三叉链，还有一个父亲的指针，后面的旋转可以看到，这个父亲的价值是非常大的，但是我们也是要记得来维护父亲这个指针的，还增加了平衡因子(balance factor)，默认新增节点的平衡因子是0。
2.2 AVL树的插入
2.2.1 AVL树插入的大概逻辑
1、首先要按照搜索树的规则去插入值，不能只关注平衡但是违背了搜索树的规则，那AVL树就没意义了。
2、 插入节点后，树的高度可能会发生变化，那部分祖先节点的平衡因子可能会比变，所以需要从新增节点->根节点这条路径上更新平衡因子，可能调整到中途就结束了，可能要一直调整到根节点。
3、如果更新过程中，平衡因子没有出现问题，插入就结束。
4.如果更新过程中，出现了不平衡，就需要对不平衡的子树进行旋转，让这颗子树变平衡，同时降低这颗子树的高度，不会再影响上一层，插入结束。
2.2.2 平衡因子的变化
更新规则：
1、平衡因子 = 右子树的高度 - 左子树的高度。
2、只有子树高度变化才会影响当前结点平衡因子。
3、插入结点，会增加高度，所以新增结点在父亲的右子树，父亲的平衡因子就++，新增结点在父亲的左子树，父亲平衡因子就--。
4、父亲所在子树的高度是否变化决定了是否要继续往上更新，在下面分类讨论了父亲的平衡因子变化的情况。
平衡因子更新的停止条件：
1、更新后父亲的平衡因子等于0，更新前父亲的平衡因子为-1 或者 1，说明更新前父亲子树一边高一边低，新增的结点插入在低的那边，插入后父亲所在的子树高度不变，不会影响父亲的父亲结点的平衡因子，更新结束。
2、更新后父亲的平衡因子等于1 或 -1，更新前父亲的平衡因子为0 ，说明更新前父亲子树两边一样高，新增的插入结点后，父亲所在的子树一边高一边低，父亲所在的子树符合平衡要求，但是高度增加了1，会影响父亲的父亲结点的平衡因子，所以要继续向上更新。
3、更新后父亲的平衡因子等于2 或 -2，更新前父亲的平衡因子为1 或者 -1，说明更新前父亲子树一边高一边低，新增的插入结点在高的那边，父亲所在的子树高的那边更高了，破坏了平衡，父亲所在的子树不符合平衡要求，需要旋转处理，而旋转后就变平衡了，所以旋转后也不需要继续往上更新，插入结束。
4、不断更新，更新到根，跟的平衡因子是1或-1也停止了。
2.2.3 插入代码的框架
前面的找要插入的位置和二叉搜索树是一样的，平衡因子的更新就按照我们分类讨论的四种情况来写就可以
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
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent; // 维护三叉链，父亲也要连上
// 维护平衡因子
while (parent)
{
// 更新平衡因子
if (parent->_left == cur)
{
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)
{
// 不平衡了，旋转，旋转完更新结束
break;
}
else
{
assert(false); // 处理意外情况，平衡因子不是这三种情况
}
}
return true;
}2.3 旋转
2.3.1 旋转的原则
1、保持搜索树的规则2、让旋转的树从不平衡变平衡，并且降低树的高度旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋，我们会一种一种来讲
2.3.2 右单旋
本图展示的是5为根的树，有a/b/c三棵高度为h的抽象的子树(h>=0)，它们均符合AVL树的要求。5可能是整棵树的根，也可能是一个整棵树中局部的子树的根。
a/b/c是抽象的子树，它可以代表任意情况，待会我们会来分析。
在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致5的平衡因子从-1变成-2，5为根的树左右高度差超过1，违反平衡规则。5为根的树左边太高了，需要往右边旋转，控制两棵树的平衡。旋转的步骤，因为3 < b子树的值 < 5，将b变成5的左子树，b,c,5都比3大，将5变成3的右子树，3变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到了插入之前的h+2，符合旋转原则。旋转后不会再影响上一层，插入结束了。
现在来看一下如果h是真实的树是什么样子的
当 h == 2 的时候，会有x/y/z三种情况，b和c可以是x/y/z中的任意一种，a必须是x，如果a是y/z的话，那插入后y/z的高度就要1，那a自身就要旋转，只有当a是x的时候，插入后高度加1，a不需要旋转，会继续向上更新，诱发5作为旋转点进行右单旋。那b/c都是x/y/z三种情况，a只有1种情况，但是a有4个插入位置，那总情况就是3*3*1*4 = 36种。
由于 h == 3 的时候节点个数较多，画出来会比较乱，所以在这里用抽象图来代替，然后来分析，首先x就代表高度为3的满二叉树的AVL树，y代表着一个组合，四个叶子节点可以任意保留一个/保留两个/保留三个，都是满足高度为3的AVL树的。那y就一共有C(4, 1) + C(4, 2) + C(4, 3) = 14种，b和c可以是x/y中的任意一种，那就是各有15种。a的情况跟情况三是类似的，要求插入新节点后，a自身不旋转，要一直向上更新，诱发5作为旋转点进行右单旋，a如果是x，插入位置有8个，a如果是y，4个叶子节点保留任意3个，有4种情况，每种情况的插入位置必须是在有两个节点那边的任意一个位置，每种任意保留三个节点的插入情况就有4种，那总共就是15*15*(8+4*4) = 5400种。
以上两张图是讲解，为什么只能插入在两个节点的那边，一个节点的那边为什么不能插入，原因是a自己就会旋转。以及4种任意保留3个节点，每一种情况又有4个插入位置，共计16种情况的详细图。
当 h == 3 的时候就已经有5400种了，那 h == 4, h == 5的时候情况就会更加多，分析不过来，但是通过这四种情况我们可以知道无论h是几，旋转思路是不变的，所以我们不用管这些子树是什么样的。
2.3.3 右单旋代码实现
通过抽象图我们可以看到，当cur的平衡因子是-1， parent的平衡因子是-2的时候，就要右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright; // 核心操作1
curright->_parent = parent; // 链接父亲
cur->_right = parent; // 核心操作2
parent->_parent = cur; // 链接父亲
parent->_bf = cur->_bf = 0; // 调整平衡因子
}两个核心操作是parent的左指向cur的右，cur的右指向parent，然后处理父亲，要链接回去，旋转完成后，parent和cur的平衡因子都是0。
但是写到这里我们只写完了一半，我们来看看哪里还有问题
当情况一，h == 0的时候，curright是空，那curright->_parent = parent就会出现空指针解引用，所以应该判断一下curright为空才可以。
我们前面说过，现在处理的这棵树可能是整颗树的根，也有可能是局部的子树，现在这颗子树的根由parent变成了cur，所以需要处理，parent->_parent已经指向cur了，所以应该在改变这个指向前记录一下parent->_parent，否则这颗局部子树的连接就断开了，然后要判断一下，如果这个节点的左指向parent，那现在让它的左指向cur，如果节点的右指向parent，那现在让它的右指向cur，如果parent就是根，那现在就让cur做根
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright; // 核心操作1
if(curright)
curright->_parent = parent; // 链接父亲
cur->_right = parent; // 核心操作2
Node* parentParent = parent->_parent; // 先记录节点
parent->_parent = cur; // 链接父亲
if (parent == _root) // 如果parent是根，那现在cur就是根
{
_root = cur;
cur->_parent = nullptr;
}
else // 局部子树的情况，要与上面的节点链接
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
}
else
{
parentParent->_right = cur;
}
cur->_parent = parentParent;
}
parent->_bf = cur->_bf = 0; // 调整平衡因子
}这就是完整的右单旋的代码实现
2.3.4 左单旋
本图展示的是5为根的树，有a/b/c三棵高度为h的抽象的子树(h>=0)，它们均符合AVL树的要求。5可能是整棵树的根，也可能是一个整棵树中局部的子树的根。
a/b/c是抽象的子树，它可以代表任意情况。
在a子树中插入一个新节点，导致a子树的高度从h变成h+1，不断向上更新平衡因子，导致5的平衡因子从1变成2，5为根的树左右高度差超过1，违反平衡规则。5为根的树右边太高了，需要往左边旋转，控制两棵树的平衡。旋转的步骤，因为5 < b子树的值 < 10，将b变成5的右子树，b,c,5都比10大小，将5变成10的左子树，10变成这棵树新的根，符合搜索树的规则，控制了平衡，同时这棵树的高度恢复到了插入之前的h+2，符合旋转原则。旋转后不会再影响上一层，插入结束了。
2.3.5 左单旋代码实现
通过抽象图我们可以看到，当cur的平衡因子是1， parent的平衡因子是2的时候，就要左单旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft; // 核心操作1
if (curleft)
curleft->_parent = parent; // 链接父亲
cur->_left = parent; // 核心操作2
Node* parentParent = parent->_parent; // 先记录节点
parent->_parent = cur; // 链接父亲
if (parent == _root) // 如果parent是根，那现在cur就是根
{
_root = cur;
cur->_parent = nullptr;
}
else // 局部子树的情况，要与上面的节点链接
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
}
else
{
parentParent->_right = cur;
}
cur->_parent = parentParent;
}
parent->_bf = cur->_bf = 0; // 调整平衡因子
}
两个核心操作是parent的右指向cur的左，cur的左指向parent，然后处理父亲，要链接回去，旋转完成后，parent和cur的平衡因子都是0，且需要处理parent是整颗树的根还是局部子树的根，要让新的根cur跟上面的节点连接上。
2.3.6 左右双旋
当左边高时，如果插入位置不是在a子树，而是在b子树，b子树高度从h变成h+1，引发旋转，右单旋无法解决问题，右单旋后，树依旧不平衡。这是因为右单旋解决的是纯粹的左边高，但是插入在b子树中，10为根的子树不再是单纯的左边高，对于10是左边高，但是对于5是右边高，这时就需要用两次旋转才能解决，以5为旋转点将进行一个左单旋，以10为旋转点进行一个右单旋，这棵树就平衡了。
由此我们可以看出，首先先进行左单旋，就是要变成纯粹的左边高，再进行右单旋，调整平衡，但是双旋并不是调用单旋就好，插入位置决定了旋转后的平衡因子应该怎么变。
2.3.6.1 左右双旋平衡因子调整
依然以抽象图为例，因为要在b子树插入一个节点诱发旋转，为了方便观察，我们把b子树展开为8和两颗高度为h-1的e、f子树，那就会有三种插入的情况
通过上面的三张图我们可以看到，当插入节点的位置不同的时候，旋转后平衡因子的变化就不同。
总结：
情况一：h >= 1时，新增结点插入在e子树，e子树高度从h-1并为h并不断更新8->5->10平衡因子，引发旋转，旋转前curright的平衡因子为-1，旋转后curright和cur平衡因子为0，parent平衡因子为1。
情况二：h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新8->5->10平衡因子，引发旋转，旋转前curright的平衡因子为1，旋转后curright和parent平衡因子为0，cur平衡因子为-1。情况三：h == 0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新5->10平衡因子，引发旋转，旋转前curright的平衡因子为0，旋转后curright、parent和cur平衡因子均为0。
2.3.7 左右双旋代码实现
当cur的平衡因子是1， parent的平衡因子是-2的时候，就要左右双旋，按照我们刚刚分析的逻辑去更新平衡因子即可
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf; // 提前记录平衡因子
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else
{
assert(false); // 处理意外情况
}
}在调用单旋之前，应该先记录一下curright的平衡因子，因为单旋后会被改成0，bf == 0的这种情况其实是不需要写的，因为单旋后这三个节点的平衡因子都会被改成0，不需要特殊处理，但是为了代码的可读性我们在这里写出来了，如果bf不是0/1/-1，那就是平衡因子出了问题，用断言来处理一下。
2.3.8 右左双旋
跟左右双旋的原理是一样的，纯粹的右边高才可以用左单旋处理，否则就要用两次旋转，我们直接来分析平衡因子的变化情况。
2.3.8.1 右左双旋平衡因子调整
依然以抽象图为例，因为要在b子树插入一个节点诱发旋转，为了方便观察，我们把b子树展开为12和两颗高度为h-1的e、f子树，那就会有三种插入的情况
通过上面的三张图我们可以看到，当插入节点的位置不同的时候，旋转后平衡因子的变化就不同。
总结：
情况一：h >= 1时，新增结点插入在e子树，e子树高度从h-1变为h并不断更新12->15->10平衡因子，引发旋转，旋转前curleft的平衡因子为-1，旋转后cur和curleft平衡因子为0，cur平衡因子为1。
情况二：h >= 1时，新增结点插入在f子树，f子树高度从h-1变为h并不断更新 12->15->10 平衡因子，引发旋转，旋转前 curleft 的平衡因子为1，旋转后curleft和cur平衡因子为0，parent平衡因子为-1。情况三：h == 0时，a/b/c都是空树，b自己就是⼀个新增结点，不断更新15->10平衡因子，引发旋转，旋转前curleft的平衡因子为0，旋转后curleft、parent和cur平衡因子均为0。
2.3.9 右左双旋代码实现
当cur的平衡因子是-1， parent的平衡因子是2的时候，就要左右双旋，按照我们刚刚分析的逻辑去更新平衡因子即可。
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf; // 提前记录平衡因子
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
else
{
assert(false); // 处理特殊情况
}
}2.4 AVL树的查找
bool 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 true;
}
}
return false;
}2.5 AVL树的中序遍历
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}2.6 AVL树的节点个数
int size()
{
return _size(_root);
}
int _size(Node* root)
{
if (root == nullptr)
return 0;
return _size(root->_left) + _size(root->_right) + 1;
}2.7 AVL树的高度
int Height()
{
return _Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int retleft = _Height(root->_left);
int retright = _Height(root->_right);
return retleft > retright ? retleft + 1 : retright + 1;
}2.8 AVL树的验证
验证方式是我们先计算左右子树的高度，看一下高度差是不是超过了1，如果左右子树的高度差都超过了1，那肯定不平衡了，没有超过1的话，就看一下右子树高度 - 左子树高度是不是等于平衡因子，不相等平衡因子就有问题，相等平衡因子就没问题，然后再去递归左，递归右，去验证。
int Height()
{
return _Height(_root);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int retleft = _Height(root->_left);
int retright = _Height(root->_right);
return retleft > retright ? retleft + 1 : retright + 1;
}
bool isBalance()
{
return _isBalance(_root);
}
bool _isBalance(Node* root)
{
if (root == nullptr) // 空树也是AVL树
return true;
int retleft = _Height(root->_left);
int retright = _Height(root->_right);
int bf = retright - retleft;
if (abs(retleft - retright) > 1) // 左右子树高度差满不满足要求
{
cout << "高度异常" << endl;
return false;
}
if (bf != root->_bf) // 看平衡因子
{
cout << "平衡因子异常" << endl;
return false;
}
return _isBalance(root->_left) && _isBalance(root->_right); // 继续递归看左右子树
}Height是求树的高度的函数，因为需要把这个函数提供给外面，而又因为递归要有参数，所以就要套一层给自己内部使用，isBalance是检测是否是AVL树的函数，里面求树的高度直接调用了_Height，然后看子树的高度差以及当前节点的平衡因子是否符合AVL树的要求。
2.9 AVL树完整代码
struct AVLTreeNode
{
pair<K, V> _kv;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _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:
bool insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
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
{
parent->_left = cur;
}
cur->_parent = parent;
// 更新平衡因子
while (parent)
{
if (parent->_left == cur)
{
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 (cur->_bf == -1 && parent->_bf == -2) // 右单旋
{
RotateR(parent);
}
else if (cur->_bf == 1 && parent->_bf == 2) // 左单旋
{
RotateL(parent);
}
else if (cur->_bf == 1 && parent->_bf == -2) // 左右双旋
{
RotateLR(parent);
}
else if (cur->_bf == -1 && parent->_bf == 2) // 右左双旋
{
RotateRL(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
parent->_left = curright; // 核心操作1
if(curright)
curright->_parent = parent; // 链接父亲
cur->_right = parent; // 核心操作2
Node* parentParent = parent->_parent; // 先记录节点
parent->_parent = cur; // 链接父亲
if (parent == _root) // 如果parent根，那现在cur就是根
{
_root = cur;
cur->_parent = nullptr;
}
else // 局部子树的情况，要与上面的节点连接
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
}
else
{
parentParent->_right = cur;
}
cur->_parent = parentParent;
}
parent->_bf = cur->_bf = 0; // 调整平衡因子
}
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
parent->_right = curleft; // 核心操作1
if (curleft)
curleft->_parent = parent; // 链接父亲
cur->_left = parent; // 核心操作2
Node* parentParent = parent->_parent; // 先记录节点
parent->_parent = cur; // 链接父亲
if (parent == _root) // 如果parent根，那现在cur就是根
{
_root = cur;
cur->_parent = nullptr;
}
else // 局部子树的情况，要与上面的节点连接
{
if (parentParent->_left == parent)
{
parentParent->_left = cur;
}
else
{
parentParent->_right = cur;
}
cur->_parent = parentParent;
}
parent->_bf = cur->_bf = 0; // 调整平衡因子
}
void RotateLR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
int bf = curright->_bf; // 提前记录平衡因子
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else
{
assert(false); // 处理意外情况
}
}
void RotateRL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
int bf = curleft->_bf; // 提前记录平衡因子
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
else
{
assert(false); // 处理意外情况
}
}
bool 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 true;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
int Height()
{
return _Height(_root);
}
int size()
{
return _size(_root);
}
bool isBalance()
{
return _isBalance(_root);
}
private:
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << " ";
_InOrder(root->_right);
}
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int retleft = _Height(root->_left);
int retright = _Height(root->_right);
return retleft > retright ? retleft + 1 : retright + 1;
}
int _size(Node* root)
{
if (root == nullptr)
return 0;
return _size(root->_left) + _size(root->_right) + 1;
}
bool _isBalance(Node* root)
{
if (root == nullptr) // 空树也是AVL树
return true;
int retleft = _Height(root->_left);
int retright = _Height(root->_right);
int bf = retright - retleft;
if (abs(retleft - retright) > 1) // 左右子树高度差满不满足要求
{
cout << "高度异常" << endl;
return false;
}
if (bf != root->_bf) // 看平衡因子
{
cout << "平衡因子异常" << endl;
return false;
}
return _isBalance(root->_left) && _isBalance(root->_right); // 继续递归看左右子树
}
private:
Node* _root = nullptr;
};总结
AVL树是较难的数据结构，它的效率也是比二叉搜索树有提高的，而且学了AVL的旋转后我们再学习红黑树的成本就下降了很多，如果大家有哪里没有看懂的，可以再自己画图结合去理解一下，对于这种数据结构来说，一定是画图最关键，我们把逻辑都分析清楚了后会发现其实代码并不难写，重要的是画图分析的过程，那本篇文章到这里就结束了，如果大家觉得小编写的不错，可以给三连支持下！！！