> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。> 目标：能直接手撕AVL树。
> 毒鸡汤：放弃自己，相信别人，这就是失败的原因。
> 望小伙伴们点赞????收藏✨加关注哟????????
????前言
相信大家肯定听过在C++大名鼎鼎的两颗树，这两颗树分别是AVL树和红黑树，学过的小伙伴听到都是瑟瑟发抖，像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大，正所谓难度越大动力就越大，那本篇我们学习这两棵树的一颗树--AVL树。
⭐主体
学习AVL树咱们按照下面的图解：
????AVL树的概念
在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。
AVL树的定义
- 一棵空的树是AVL树
- 如果T是一棵非空的二叉树，T(L)和T(R)分别是其左子树高和右子树高，那么当T满足以下条件时，T是一棵AVL树，|h(L)-h(R)|<=1，其中h(L)和h(R)分别是T(L)和T(R)的高（简称平衡因子）
AVL树的状态：
AVL树的特性：
- 一棵n个元素的AVL树，其高度是O(logn)
- 对于每一个n，n>=0，都存在一棵AVL树
- 对一棵n元素的AVL搜索树，在O(高度)=O(logn)的时间内可以完成查找
- 将一个新元素插入一棵n元素的AVL搜索树中，可以得到一棵n+1个元素的AVL树，而且插入用时为O(logn)
- 一个元素从一棵n元素的AVL搜索树中删除，可以得到一棵n-1个元素的AVL树，而且删除用时为O(logn)
????AVL树的结点
- 按照 KV 模型来构造 AVL 树，需要把结点定义为 三叉链结构（左、右、父）。
- 构造函数，由于新构造结点的左右子树均为空树，所以将新构造结点的平衡因子初始设置为 0 。
代码示例：
// 创建AVL树的结点
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left; // 左子树
AVLTreeNode<K, V>* _right; // 右子树
AVLTreeNode<K, V>* _parent;// 父亲结点
pair<K, V> _kv; // 存储的键值对
int _bf; // 平衡因子（右子树高度 - 左子树高度）
// 构造函数
AVLTreeNode(const pair<K, V>& kv)
:_left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _kv(kv)
, _bf(0)
{}
};????AVL树的插入
其实AVL树插入操作，本质上比二叉搜索树的插入操作多了一个平衡操作：
- 按照二叉搜索树的方式，找到待插入的位置，然后将新结点插入到该位置。
- 调整节点的平衡因子，如果出现不平衡，则需要进行旋转。
当 AVL 树插入一个新结点以后，需要更新插入结点的祖先的平衡因子，因为新结点（也就是叶子结点）的平衡因子为 0，但是它影响的是它的父亲，它父亲的父亲…，所以要更新到祖先结点。
上面的图就需要改变父亲爷爷的平衡因子，我们知道，树的状态有很多，无法穷举，但是我们也有规律可寻，这个规律就在于我们的平衡因子，所以我总结如下：
- 如果新增结点插入在 parent 的右边，只需要给 parent 的平衡因子 +1 即可
- 如果新增结点插入在 parent 的左边，只需要给 parent 的平衡因子 -1 即可
当 parent 的平衡因子更新完以后，可能出现三种情况：0，正负 1，正负 2。
（1）parent 的平衡因子为 0
如果parent的平衡因子是0：说明之前parent的平衡因子是1或-1，说明之前parent一边高、一边低；这次插入之后填入矮的那边，parent所在的子树高度不变，不需要继续往上更新。如图：
（2）如果 parent 的平衡因子为正负 1
如果parent的平衡因子是1或者-1：说明之前parent的平衡因子是0，两边一样高，插入之后一边更高，parent所在的子树高度发生变化，继续往上更新。
①parent为1
②parent为 -1
（3）如果 parent 的平衡因子为正负 2
平衡因子是2或-2，说明之前parent的平衡因子是1或-1，现在插入严重不平衡，违反规则，需要进行旋转处理
- 如果parent的平衡因子是2，cur的平衡因子是1时，说明右边的右边比较高，我们需要进行左单旋
- 如果parent的平衡因子是-2，cur的平衡因子是-1时，说明左边的左边比较高，我们需要进行右单旋
- 如果parent的平衡因子是-2，cur的平衡因子是1时，我们需要进行左右双旋
- 如果parent的平衡因子是2，cur的平衡因子是-1时，我们需要进行右左双旋
这里我们就举一个栗子：
代码实现：
public:
// 插入函数
bool Insert(const pair<K, V>& kv)
{
// 如果AVL树是空树，把插入节点直接作为根节点
if (_root == nullptr)
{
_root = new Node(kv);
_root->_bf = 0;
return true;
}
// 1.按照二叉搜索树的规则插入
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first) // 待插入节点的key值大于当前节点的key值
{
// 往右子树走
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first) // 待插入节点的key值小于当前节点的key值
{
// 往左子树走
parent = cur;
cur = cur->_left;
}
else // 待插入节点的key值等于当前节点的key值
{
return false; // 插入失败，返回false
}
}
// 2.当循环结束，说明cur找到了空的位置，那么就插入
cur = new Node(kv); // 构造一个新节点
if (parent->_kv.first < kv.first) // 如果新节点的key值大于当前parent节点的key值
{
// 就把新节点链接到parent的右边
parent->_right = cur;
}
else // 如果新节点的key值小于当前parent节点的key值
{
// 就把新节点链接到parent的左边
parent->_left = cur;
}
cur->_parent = parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链)
// 3.更新平衡因子,如果出现不平衡,则需要进行旋转
while (parent) // 最远要更新到根节点去
{
if (cur == parent->_right) // 如果cur插在parent的右边，说明parent的右子树增高
{
parent->_bf++; // 那么parent的平衡因子要++
}
else // 如果cur插在parent的左边，说明parent的左子树增高
{
parent->_bf--; // 那么parent的平衡因子要--
}
// 判断是否更新结束，或者是否需要进行旋转
if (parent->_bf == 0) // 如果parent的bf等于0，说明左右子树高度一致，就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了）
{
// 高度不变,更新结束
break;
}
else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新平衡因子(插入节点导致某一边变高了，说明parent所在的子树高度改变了)
{
// 子树的高度变了，就要继续往上更新祖先
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 说明插入节点导致本来高的一边又变高了，子树不平衡了，那么此时需要做旋转处理
{
// 旋转的四种处理方式
// 1.左单旋
// 2.右单旋
// 3.左右双旋
// 4.右左双旋
// 旋转完成，跳出
break;
}
else
{
// 如果程序走到了这里，说明在插入节点之前AVL树就存在不平衡的子树，也就是存在平衡因子 >= 2的节点
// 所以这里加一个断言进行处理
assert(false);
}
}
// 插入成功，返回true
return true;
}
????AVL树的旋转
在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，采用不同的旋转方法。
AVL树的旋转分为四种：
- 左单旋（LL）
- 右单旋（RR）
- 左右双旋（LR）
- 右左双旋（RL）
旋转规则：
- 让这颗子树左右高度差不超过1
- 旋转过程中继续保持它是搜索树
- 更新调整孩子节点的平衡因子
- 让这颗子树的高度根插入前保持一致
????左单旋
左单旋的步骤如下：
- 先让 subR 的左子树（subRL）作为 parent 的右子树。
- 然后让 parent 作为 subR 的左子树。
- 接下来让 subR 作为整个子树的根。
- 最后更新平衡因子
我们就以下面的抽象图来看看左单旋如何实现：
代码示例：
// 左单旋（右边高需要左单旋）
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* ppNode = parent->_parent; // 先保存parent的parent
// 1.建立parent和subRL之间的关系
parent->_right = subRL;
if (subRL) // 如果subRL节点不为空，那么要更新它的parent
{
subRL->_parent = parent;
}
// 2.建立subR和parent之间的关系
subR->_left = parent;
parent->_parent = subR;
// 3.建立ppNode和subR之间的关系（分情况讨论parent是整颗树的根，还是局部子树）
if (parent == _root) // 当parent是根节点时
{
_root = subR; // subR就变成了新的根节点
_root->_parent = nullptr; // 根节点的的parent为空
}
else // 当parent是整个树的局部子树时
{
if (parent == ppNode->_left) // 如果parent在ppNode的左边
{
ppNode->_left = subR; // 那么subR就是parent的左子树
}
else // 如果parent在ppNode的右边
{
ppNode->_right = subR; // 那么subR就是parent的右子树
}
subR->_parent = ppNode; // subR的parent还要指向ppNode
}
// 更新平衡因子
parent->_bf = 0;
subR->_bf = 0;
}
????右单旋
右单旋的步骤如下：
- 先让 subL 的右子树（subLR）作为 parent 的左子树。
- 然后让 parent 作为 subL 的右子树。
- 接下来让 subL 作为整个子树的根。
- 最后更新平衡因子。
我们就以下面的抽象图来看看右单旋如何实现：
代码示例：
// 右单旋（左边高就右单旋）
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode = parent->_parent;
// 1.建立parent和subLR之间的关系
parent->_left = subLR;
if (subLR) // 如果subLR节点不为空，那么要更新它的parent
{
subLR->_parent = parent;
}
// 2.建立subL和parent之间的关系
subL->_right = parent;
parent->_parent = subL;
// 3.建立ppNode和subL之间的关系（分情况讨论parent是整颗树的根，还是局部子树）
if (parent == _root) // 当parent是根节点时
{
_root = subL; // subL就变成了新的根节点
_root->_parent = nullptr; // 根节点的的parent为空
}
else // 当parent是整个树的局部子树时
{
if (parent == ppNode->_left) // 如果parent在ppNode的左边
{
ppNode->_left = subL; // 那么subL就是parent的左子树
}
else // 如果parent在ppNode的右边
{
ppNode->_right = subL; // 那么subL就是parent的右子树
}
subL->_parent = ppNode; // subR的parent还要指向ppNode
}
// 更新平衡因子
parent->_bf = 0;
subL->_bf = 0;
}
????左右单旋
左右单旋的步骤如下：
- 先以 subL 为旋转点进行左单旋。
- 然后以 parent 为旋转点进行右单旋。
- 最后再更新平衡因子。
我们就以下面的抽象图来看看左右单旋如何实现：
再次分类讨论：
（1）当 subLR 原始平衡因子是 -1 时，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 1、0、0
（2）当 subLR 原始平衡因子是 1 时，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、-1、0
（3）当 subLR 原始平衡因子是 0 时（说明 subLR 为新增结点），左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、0、0
代码示例：
// 左右双旋（先左单旋，再右单旋）
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
// 1.先以subL为旋转点进行左单旋
RotateL(parent->_left);
// 2.再以parent为旋转点进行右单旋
RotateR(parent);
// 3.更新平衡因子
if (bf == 0)
{
parent->_bf = 0;
subL->_bf = 0;
subLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
subL->_bf = -1;
subLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
subL->_bf = 0;
subLR->_bf = 0;
}
else
{
// 如果走到了这里，说明subLR的平衡因子在旋转前就有问题
assert(false);
}
}
????右左单旋
右左单旋的步骤如下：
- 先以 subR 为旋转点进行右单旋。
- 然后以 parent 为旋转点进行左单旋。
- 最后再更新平衡因子。
我们就以下面的抽象图来看看右左单旋如何实现：
再次分类讨论：
（1）当 subRL 原始平衡因子是 1 时，左右双旋后 parent、subR、subRL 的平衡因子分别更新为 -1、0、0
（2）当 subRL 原始平衡因子是 -1 时，左右双旋后 parent、subR、subRL 的平衡因子分别更新为 0、1、0
（3）当 subRL 原始平衡因子是 0 时（说明 subRL为新增结点），左右双旋后 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(parent->_right);
// 2.再以parent为旋转点进行左单旋
RotateL(parent);
// 3.更新平衡因子
if (bf == 0)
{
subRL->_bf = 0;
parent->_bf = 0;
subR->_bf = 0;
}
else 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
{
// 如果走到了这里，说明subRL的平衡因子在旋转前就有问题
assert(false);
}
}
????AVL树的删除
这里的删除过于复杂，我这里就直接上代码了，如果对这里感兴趣的小伙伴们可以查阅资料。
// 删除函数
bool Erase(const K& key)
{
//用于遍历二叉树
Node* parent = nullptr;
Node* cur = _root;
//用于标记实际的删除结点及其父结点
Node* delParentPos = nullptr;
Node* delPos = nullptr;
while (cur)
{
if (key < cur->_kv.first) //所给key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (key > cur->_kv.first) //所给key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //找到了待删除结点
{
if (cur->_left == nullptr) //待删除结点的左子树为空
{
if (cur == _root) //待删除结点是根结点
{
_root = _root->_right; //让根结点的右子树作为新的根结点
if (_root)
_root->_parent = nullptr;
delete cur; //删除原根结点
return true; //根结点无祖先结点，无需进行平衡因子的更新操作
}
else
{
delParentPos = parent; //标记实际删除结点的父结点
delPos = cur; //标记实际删除的结点
}
break; //删除结点有祖先结点，需更新平衡因子
}
else if (cur->_right == nullptr) //待删除结点的右子树为空
{
if (cur == _root) //待删除结点是根结点
{
_root = _root->_left; //让根结点的左子树作为新的根结点
if (_root)
_root->_parent = nullptr;
delete cur; //删除原根结点
return true; //根结点无祖先结点，无需进行平衡因子的更新操作
}
else
{
delParentPos = parent; //标记实际删除结点的父结点
delPos = cur; //标记实际删除的结点
}
break; //删除结点有祖先结点，需更新平衡因子
}
else //待删除结点的左右子树均不为空
{
//替换法删除
//寻找待删除结点右子树当中key值最小的结点作为实际删除结点
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key
cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value
delParentPos = minParent; //标记实际删除结点的父结点
delPos = minRight; //标记实际删除的结点
break; //删除结点有祖先结点，需更新平衡因子
}
}
}
if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点
{
return false;
}
//记录待删除结点及其父结点（用于后续实际删除）
Node* del = delPos;
Node* delP = delParentPos;
//更新平衡因子
while (delPos != _root) //最坏一路更新到根结点
{
if (delPos == delParentPos->_left) //delParentPos的左子树高度降低
{
delParentPos->_bf++; //delParentPos的平衡因子++
}
else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低
{
delParentPos->_bf--; //delParentPos的平衡因子--
}
//判断是否更新结束或需要进行旋转
if (delParentPos->_bf == 0)//需要继续往上更新平衡因子
{
//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
}
else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束
{
break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
}
else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了）
{
if (delParentPos->_bf == -2)
{
if (delParentPos->_left->_bf == -1)
{
Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
RotateR(delParentPos); //右单旋
delParentPos = tmp; //更新根结点
}
else if (delParentPos->_left->_bf == 1)
{
Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点
RotateLR(delParentPos); //左右双旋
delParentPos = tmp; //更新根结点
}
else //delParentPos->_left->_bf == 0
{
Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
RotateR(delParentPos); //右单旋
delParentPos = tmp; //更新根结点
//平衡因子调整
delParentPos->_bf = 1;
delParentPos->_right->_bf = -1;
break; //更正
}
}
else //delParentPos->_bf == 2
{
if (delParentPos->_right->_bf == -1)
{
Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点
RotateRL(delParentPos); //右左双旋
delParentPos = tmp; //更新根结点
}
else if (delParentPos->_right->_bf == 1)
{
Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
RotateL(delParentPos); //左单旋
delParentPos = tmp; //更新根结点
}
else //delParentPos->_right->_bf == 0
{
Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
RotateL(delParentPos); //左单旋
delParentPos = tmp; //更新根结点
//平衡因子调整
delParentPos->_bf = -1;
delParentPos->_left->_bf = 1;
break; //更正
}
}
//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
//break; //error
}
else
{
assert(false); //在删除前树的平衡因子就有问题
}
}
//进行实际删除
if (del->_left == nullptr) //实际删除结点的左子树为空
{
if (del == delP->_left) //实际删除结点是其父结点的左孩子
{
delP->_left = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
else //实际删除结点是其父结点的右孩子
{
delP->_right = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
}
else //实际删除结点的右子树为空
{
if (del == delP->_left) //实际删除结点是其父结点的左孩子
{
delP->_left = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
else //实际删除结点是其父结点的右孩子
{
delP->_right = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
}
delete del; //实际删除结点
return true;
}
????AVL树的遍历
中序是递归遍历（左 根 右），由于涉及到传参，所以需要写一个子函数。
代码实现：
// 中序遍历
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);
}????AVL树的查找
查找步骤：
- 若 key 值小于当前结点的值，则应该在该结点的左子树当中进行查找。
- 若 key 值大于当前结点的值，则应该在该结点的右子树当中进行查找。
- 若 key 值等于当前结点的值，则查找成功，返回对应结点。
代码实现：
// 查找元素
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;
}????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;
}
int Height()
{
return _Height(_root);
}????AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分为下面两步：
（1）验证其为二叉搜索树
- 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
void _InOrder(Node* root)
{
if (root == nullptr)
return;
_InOrder(root->_left);
cout << root->_kv.first << ":" << root->_kv.second << endl;
_InOrder(root->_right);
}
（2）验证其为平衡树
- 每个节点子树高度差的绝对值不超过 1（注意节点中如果没有平衡因子）
- 节点的平衡因子是否计算正确
????AVL树的高度
//求高度
int Height(Node* root)
{
if (root == nullptr)
return 0;
int lh = Height(root->_left);
int rh = Height(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
//判断平衡
bool IsBalance(Node* root)
{
if (root == nullptr)
{
return true;
}
int leftHeight = Height(root->_left);
int rightHeight = Height(root->_right);
if (rightHeight - leftHeight != root->_bf)
{
cout << root->_kv.first << "平衡因子异常" << endl;
return false;
}
return abs(rightHeight - leftHeight) < 2
&& IsBalance(root->_left)
&& IsBalance(root->_right);
}
????AVL树优缺点
优点：
- 平衡二叉树的优点不言而喻，相对于二叉排序树（BST）而言，平衡二叉树避免了二叉排序树可能出现的最极端情况（斜树）问题，其平均查找的时间复杂度为 O ( l o g N ) O(logN)O(logN)
缺点：
- 平衡二叉树为了保持平衡，动态进行插入和删除操作的代价也会增加。因此出现了后来的红黑树
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即O ( l o g N ) O(logN)O(logN)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但一个结构经常修改，就不太适合。
????整体代码
#include <iostream>
#include <assert.h>
#include<vector>
#include <time.h>
using namespace std;
// 创建AVL树的结点
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>* _left; // 左子树
AVLTreeNode<K, V>* _right; // 右子树
AVLTreeNode<K, V>* _parent;// 父亲结点
pair<K, V> _kv; // 存储的键值对
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) // 如果没有结点
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur) // 采用循环查找要插入的结点
{
if (cur->_kv.first < kv.first) // 插入的元素大于cur就走右子树
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first < kv.first) // 插入的元素小于cur就走左子树
{
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;
// 循环判断插入结点的平衡因子和AVL树是否正确
while (parent)
{
// 判断插入的节点在父亲的右边还是左边
if (cur == parent->_left) // 在左边就父亲平衡因子减一
parent->_bf--;
else // 在右边就父亲平衡因子加一
parent->_bf++;
if (parent->_bf == 0) // 如果父亲的平衡因子为 0 该树就是健康的不用改变
break;
else if (parent->_bf == 1 || parent->_bf == -1) // 这时需要向上调整每个节点的平衡因子
{
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2) // 需要旋转处理
{
// 旋转处理
if (parent->_bf == 2 && cur->_bf == 1) // 左单旋
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋
{
RotateLR(parent);
}
else // 右左双旋
{
RotateRL(parent);
}
break;
}
else
{
// 插入之前AVL树就有问题
assert(false);
}
}
}
// 左单旋
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
Node* ppnode = parent->_parent;
parent->_parent = subR;
if (parent == _root)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = subR;
}
else
{
ppnode->_right = subR;
}
subR->_parent = ppnode;
}
parent->_bf = 0;
subR->_bf = 0;
}
// 右单旋
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;
}
// 左右双旋
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == -1)
{
subLR->_bf = 0;
subL->_bf = 0;
parent->_bf = 1;
}
else if (bf == 1)
{
subLR->_bf = 0;
subL->_bf = -1;
parent->_bf = 0;
}
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;
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, 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(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left)
+ _Size(root->_right) + 1;
}
size_t Size()
{
return _Size(_root);
}
// 查找元素
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;
}
// 删除函数
bool Erase(const K& key)
{
//用于遍历二叉树
Node* parent = nullptr;
Node* cur = _root;
//用于标记实际的删除结点及其父结点
Node* delParentPos = nullptr;
Node* delPos = nullptr;
while (cur)
{
if (key < cur->_kv.first) //所给key值小于当前结点的key值
{
//往该结点的左子树走
parent = cur;
cur = cur->_left;
}
else if (key > cur->_kv.first) //所给key值大于当前结点的key值
{
//往该结点的右子树走
parent = cur;
cur = cur->_right;
}
else //找到了待删除结点
{
if (cur->_left == nullptr) //待删除结点的左子树为空
{
if (cur == _root) //待删除结点是根结点
{
_root = _root->_right; //让根结点的右子树作为新的根结点
if (_root)
_root->_parent = nullptr;
delete cur; //删除原根结点
return true; //根结点无祖先结点，无需进行平衡因子的更新操作
}
else
{
delParentPos = parent; //标记实际删除结点的父结点
delPos = cur; //标记实际删除的结点
}
break; //删除结点有祖先结点，需更新平衡因子
}
else if (cur->_right == nullptr) //待删除结点的右子树为空
{
if (cur == _root) //待删除结点是根结点
{
_root = _root->_left; //让根结点的左子树作为新的根结点
if (_root)
_root->_parent = nullptr;
delete cur; //删除原根结点
return true; //根结点无祖先结点，无需进行平衡因子的更新操作
}
else
{
delParentPos = parent; //标记实际删除结点的父结点
delPos = cur; //标记实际删除的结点
}
break; //删除结点有祖先结点，需更新平衡因子
}
else //待删除结点的左右子树均不为空
{
//替换法删除
//寻找待删除结点右子树当中key值最小的结点作为实际删除结点
Node* minParent = cur;
Node* minRight = cur->_right;
while (minRight->_left)
{
minParent = minRight;
minRight = minRight->_left;
}
cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的key
cur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的value
delParentPos = minParent; //标记实际删除结点的父结点
delPos = minRight; //标记实际删除的结点
break; //删除结点有祖先结点，需更新平衡因子
}
}
}
if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点
{
return false;
}
//记录待删除结点及其父结点（用于后续实际删除）
Node* del = delPos;
Node* delP = delParentPos;
//更新平衡因子
while (delPos != _root) //最坏一路更新到根结点
{
if (delPos == delParentPos->_left) //delParentPos的左子树高度降低
{
delParentPos->_bf++; //delParentPos的平衡因子++
}
else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低
{
delParentPos->_bf--; //delParentPos的平衡因子--
}
//判断是否更新结束或需要进行旋转
if (delParentPos->_bf == 0)//需要继续往上更新平衡因子
{
//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
}
else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束
{
break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子
}
else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了）
{
if (delParentPos->_bf == -2)
{
if (delParentPos->_left->_bf == -1)
{
Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
RotateR(delParentPos); //右单旋
delParentPos = tmp; //更新根结点
}
else if (delParentPos->_left->_bf == 1)
{
Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点
RotateLR(delParentPos); //左右双旋
delParentPos = tmp; //更新根结点
}
else //delParentPos->_left->_bf == 0
{
Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点
RotateR(delParentPos); //右单旋
delParentPos = tmp; //更新根结点
//平衡因子调整
delParentPos->_bf = 1;
delParentPos->_right->_bf = -1;
break; //更正
}
}
else //delParentPos->_bf == 2
{
if (delParentPos->_right->_bf == -1)
{
Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点
RotateRL(delParentPos); //右左双旋
delParentPos = tmp; //更新根结点
}
else if (delParentPos->_right->_bf == 1)
{
Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
RotateL(delParentPos); //左单旋
delParentPos = tmp; //更新根结点
}
else //delParentPos->_right->_bf == 0
{
Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点
RotateL(delParentPos); //左单旋
delParentPos = tmp; //更新根结点
//平衡因子调整
delParentPos->_bf = -1;
delParentPos->_left->_bf = 1;
break; //更正
}
}
//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子
delPos = delParentPos;
delParentPos = delParentPos->_parent;
//break; //error
}
else
{
assert(false); //在删除前树的平衡因子就有问题
}
}
//进行实际删除
if (del->_left == nullptr) //实际删除结点的左子树为空
{
if (del == delP->_left) //实际删除结点是其父结点的左孩子
{
delP->_left = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
else //实际删除结点是其父结点的右孩子
{
delP->_right = del->_right;
if (del->_right)
del->_right->_parent = parent;
}
}
else //实际删除结点的右子树为空
{
if (del == delP->_left) //实际删除结点是其父结点的左孩子
{
delP->_left = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
else //实际删除结点是其父结点的右孩子
{
delP->_right = del->_left;
if (del->_left)
del->_left->_parent = parent;
}
}
delete del; //实际删除结点
return true;
}
private:
Node* _root = nullptr;
};
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)
{
if (e == 14)
{
int x = 0;
}
t.Insert(make_pair(e, e));
cout << e << "->" << t.IsBalance() << endl;
}
t.InOrder();
cout << t.IsBalance() << 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.back() << endl;
}
size_t begin2 = clock();
AVLTree<int, int> t;
for (auto e : v)
{
t.Insert(make_pair(e, e));
//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
}
size_t end2 = clock();
cout << "Insert:" << end2 - begin2 << endl;
cout << t.IsBalance() << 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;
}
????结束语
今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力????????????，回见。
