『C++成长记』会旋转的二叉搜索树——AVLTree
🔥博客主页：小王又困了
📚系列专栏：C++
🌟人之为学，不日近则日退
❤️感谢大家点赞👍收藏⭐评论✍️
目录
一、AVL 树的概念
二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
- 它的左右子树都是AVL树
- 左右子树高度之差(简称平衡因子)的绝对值不超过1
小Tips：如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O(log2n)，搜索时间复杂度为 O(log2n)。平衡二叉搜索树中平衡并不是说要让平衡因子始终保持 0，这是做不到的，以两个结点为例，根节点的平衡因子只可能是 1 或者 -1，不可能是 0。
二、AVL 树结点的定义
template<class K,class V>
struct AVLTreeNode
{
pair<K, V> _kv;//存储key和value
AVLTreeNode<K, V>* _left;//指向左孩子
AVLTreeNode<K, V>* _right;//指向右孩子
AVLTreeNode<K, V>* _parent;//指向父亲结点
int _bf;//平衡因子
AVLTreeNode(cosnt pair<K, V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,parent(nullptr)
,bf(0)
{}
};
三、AVL树的框架
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
private:
Node* _root = nullptr;
};
四、AVL树的插入
AVL 树就是在二叉搜索树的基础上引入平衡因子，因此 AVL 树也可以看成是二叉搜索树。那么 AVL 树的插入过程可以分为两步：
-
按照二叉搜索树的方式插入新节点。
-
调整结点的平衡因子。
小Tips：新节点插入后，AVL 树的平衡性可能会遭到破坏，此时就需要更新平衡因子，并检测是否 破坏了 AVL 树的平衡性，如果平衡因子违反平衡树的性质，需要对其进行旋转处理。
📒4.1平衡因子的更新
假设新插入的结点为 Cur，那么 Cur 的平衡因子一定是 0，因为它的左后孩子都是 nullptr 。 Cur 插入后，双亲结点 Parent 的平衡因子一定需要调整，在插入之前，Parent 的平衡因子分为三种情况：-1、0、1。对 Parent 平衡因子的调整分为以下两种情况：
- 如果 Cur 插入到 Parent 的左侧，只需给 Parent 的平衡因子-1即可
- 如果 Cur 插入到 Parent 的右侧，只需给 Parent 的平衡因子+1即可
此时：Parent 的平衡因子可能有三种情况：0，±1， ±2
- 如果 Parent 的平衡因子为 0 ，说明插入前 Parent 的平衡因子一定为 ±1 ，即左右孩子中一定有一个是 nullptr，并且新结点就插入在为空的一侧，插入后平衡因子被调更新为 0 ，整棵树的高度不变，满足 AVL 树的性质，插入成功。
- 如果 Parent 的平衡因子是 ±1，说明插入前 Parent 的平衡因子一定是 0 ，即插入前 Parent 的左右孩子都为 nullptr，插入节点后后平衡因子被更新为 ±1，此时以 Parent 为跟的树的高度增加了，需要继续沿着祖先结点向上更新，直到某一个祖先节点的平衡因子变成了 0 ，此时更新结束，插入成功。
- 如果 Parent 的平衡因子为 ±2 ，则 Parent 的平衡因子违反了平衡树的性质，需要对其进行旋转处理。
📒4.2AVLTree的旋转
如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构， 使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：
🗒️4.2.1左单旋
新结点插入在较高右子树的右侧---右右，即parent 的平衡因子是 2 ，cur 的平衡因子是 1 ，此时就需要左单旋。
小Tips：首先在旋转的过程中要保证这棵树是搜索树，其次经过旋转后，这棵树应该变成平衡树，且降低这个子树的高度。如上图：新节点插入到60的右子树，60的右子树增加了一层，导致以30为根的二叉树不平衡，要将30右子树的高度减少一层，左子树增加一层。60的左子树中的值一定是大于30，小于60的，让subRL做30的右子树，30做60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：
- 60节点的左孩子可能存在，也可能不存在
- 60可能是根节点，也可能是子树。如果是根节点，旋转完成后，要更新根节点；如果是子树，可能是某个节点的左子树，也可能是右子树
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//处理subRL
parent->_right = subRL;
if (subRL)//判断左孩子是否存在
subRL->_parent = parent;
Node* parentP = parent->_parent;
//处理parent
subR->_left = parent;
parent->_parent = subR;
//处理subR
if (parentP == nullptr)//parent是根
{
_root = subR;
subR->_parent = nullptr;
}
else//parent是子树
{
if (parentP_left == parent)
parentP_left = subR;
else
parentP_right = subR;
subR->_parent = parentP;
}
parent->_bf = subR->_bf = 0;//更新平衡因子
}🗒️4.2.2右单旋
新结点插入在较高左子树的左侧---左左，即parent 的平衡因子是 -2 ，cur 的平衡因子是 -1 ，此时就需要右单旋。
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//处理subLR
parent->_left = subLR;
if (subLR)//判断左孩子是否存在
subLR->_parent = parent;
Node* parentP = parent->_parent;
//处理parent
subL->_right = parent;
parent->_parent = subL;
//处理subL
if (parentP == nullptr)//parent是根
{
_root = subL;
subL->_parent = nullptr;
}
else//parent是子树
{
if (parentP_left == parent)
parentP_left = subL;
else
parentP_right = subL;
subL->_parent = parentP;
}
parent->_bf = subR->_bf = 0;//更新平衡因子
}🗒️4.2.3先右单旋再左单旋
新节点插入较高右子树的左侧---右左：即 parent 的平衡因子是 2 ，cur 的平衡因子是 -1 。此时就需要先以 cur 为旋转点进行一个右单旋，然后再以 parent 为旋转点进行一个左单旋。
🗒️4.2.4先左单旋再右单旋
新节点插入较高左子树的右侧---左右：即 parent 的平衡因子是 −2 ，cur 的平衡因子是 1 。此时就需要先以 cur 为旋转点进行一个左单旋，然后再以 parent 为旋转点进行一个右单旋。
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subR->_right;
int bf = subLR->_bf;
RotateL(parent->_left);//先右单旋
RotateR(parent);//再左单旋
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = -1;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 1;
}
else
{
assert(false);
}
}AVL 树插入完整代码
public:
bool insert(cosnt 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 (kv.first < parent->_kv.first)
parent->_left = cur;
else
parent->_right = cur;
cur->_parent = parent;
//更新平衡因子
while (parent)
{
if (cur == parent->_left)
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)
{
RotateL(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
RotateR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
RotateRL(parent);
}
else
{
RotateLR(parent);
}
break;
}
else
{
assert(false);
}
}
return true;
}
private:
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
//处理subRL
parent->_right = subRL;
if (subRL)//判断左孩子是否存在
subRL->_parent = parent;
Node* parentP = parent->_parent;
//处理parent
subR->_left = parent;
parent->_parent = subR;
//处理subR
if (parentP == nullptr)//parent是根
{
_root = subR;
subR->_parent = nullptr;
}
else//parent是子树
{
if (parentP_left == parent)
parentP_left = subR;
else
parentP_right = subR;
subR->_parent = parentP;
}
parent->_bf = subR->_bf = 0;//更新平衡因子
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
//处理subLR
parent->_left = subLR;
if (subLR)//判断左孩子是否存在
subLR->_parent = parent;
Node* parentP = parent->_parent;
//处理parent
subL->_right = parent;
parent->_parent = subL;
//处理subL
if (parentP == nullptr)//parent是根
{
_root = subL;
subL->_parent = nullptr;
}
else//parent是子树
{
if (parentP_left == parent)
parentP_left = subL;
else
parentP_right = subL;
subL->_parent = parentP;
}
parent->_bf = subR->_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 RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subR->_right;
int bf = subLR->_bf;
RotateL(parent->_left);//先右单旋
RotateR(parent);//再左单旋
if (bf == 0)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1)
{
subR->_bf = -1;
subRL->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1)
{
subR->_bf = 0;
subRL->_bf = 0;
parent->_bf = 1;
}
else
{
assert(false);
}
}📒4.3AVL 树的验证
AVL 树是在二叉搜索树的基础上加入了平衡的限制，因此要验证 AVL 树，可以分为两步：
- 验证其为二叉搜索树。如果中序遍历可以得到一个有序的序列，就说明为二叉搜索树。
- 验证其为平衡树。每个结点左右子树高度差的绝对值不超过 1 11。其次检查结点的平衡因子是否计算正确。
五、AVL树的性能
AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即$og2N 。但是如果要对 AVL 树做一些结构修改的操 作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时， 有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数 据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。
🎁结语：
本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位读者三连支持。文章有问题可以在评论区留言，博主一定认真认真修改，以后写出更好的文章。你们的支持就是博主最大的动力。
Agent 垂直技术社区，欢迎活跃、内容共建。
更多推荐
25
0- 0
已为社区贡献4条内容
所有评论(0)