会旋转的树,你见过吗?
🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨ 🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中) 🐻推荐专栏1: 🍔🍟🌯C语言初阶 🐻推荐专栏2: 🍔🍟🌯C语言进阶 🔑个人信条: 🌵知行合一 🍉本篇简介:>:AVL树的实现，旋转的详细分析，抽象图，具体图分步骤讲解，保姆级教学。 金句分享: ✨人生若只如初见，✨ ✨何事秋风悲画扇。✨
前言
前面我们学习了二叉搜索树,二叉搜索树如果左右子树高度相差不大,那么效率还是可观的,比如:满二叉搜索树的查询效率为 O(logn).
但是,如果插入的数据是有序的,或者大部分有序,则会导致 “二叉搜索树” 退化为类似于链表的结构.
那链表查询数据的时间复杂度牛牛就不用多说了吧.答案: O(n)
示例:
目录
- 前言
- 一、AVL树的介绍
- 二、AVL树的模拟实现
- 🍭结点类
- 🍔AVL树的框架:
- 2.1 "插入"操作(重点)
- ①:右旋
- (1) 右旋具体图:
- (2)右旋抽象图:
- ②左旋:
- (1)左旋具体图:
- (2)左旋抽象图
- ③右左双旋
- （1）右左双旋具体图
- （2）右左双旋抽象图
- ④左右双旋
- （1）左右双旋具体图
- （2）左右双旋抽象图
- "插入"操作的代码实现:
- 2.2 中序遍历:
- 2.3 AVL树的"高度"
- 2.4 验证AVL树
- 结语
一、AVL树的介绍
AVL树是一种自"平衡二叉搜索树"，它的每个节点存储一个关键字，具有以下特点：
- 每个节点的左右子树高度差至多为1，也就是说，
AVL树的任何一个节点的左右子树高度差不超过1。 - 对于任意一个节点，其左子树和右子树都是一个
AVL树。 -
AVL树中的每个节点都能保证左子树中的所有节点小于当前节点的关键字，右子树中的所有节点大于当前节点的关键字。(也就是满足二叉搜索树的性质)
如果我们定义 平衡因子=右子树的高度-左子树的高度 则树中每个结点的平衡因子的绝对值 不超过1 即可以为( 1 0 -1三种) 1:表示右子树比左子树高. 0:表示左子树和右子树一样高. -1:表示左子树比右子树高.
每当向AVL树中插入、删除节点时，AVL树会自动地进行旋转操作将树变为平衡状态，从而保证了AVL树的平衡性。
会旋转的树才够强,AVL树的查询数据的时间复杂度总是控制在 O(logn)量级.
二、AVL树的模拟实现
补充知识点:
在c++中 pair类是一个模板类,用于将两个值组成一个单元,也就是我们称为的键值对.
template<class T1, class T2>
struct pair {
typedef T1 first_type;
typedef T2 second_type;
T1 first; // 第一个元素
T2 second; // 第二个元素
// 默认构造函数
pair() : first(T1()), second(T2()) {}
// 初始化构造函数
pair(const T1& x, const T2& y) : first(x), second(y) {}
};🍭结点类
没错,AVL树是三叉树,为了方便旋转,我们需要多存储一个指针域(_parent) ,指向父节点.
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; // balance factor平衡因子
//构造
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};🍔AVL树的框架:
// AVL树的结构
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K,V> Node;
public:
AVLTree()
: _root(nullptr)
{}
// 在AVL树中插入值为data的节点
bool Insert(const pair<K, V>& kv);
void InOrder();
// AVL树的验证
bool IsAVLTree(){
return _IsAVLTree(_root);
}
private:
// 根据AVL树的概念验证proot是否为有效的AVL树
bool _IsAVLTree(Node* root);
size_t _Height(Node* root);
void _InOrder(Node* root);
// 右单旋
void RotateR(Node* parent);
// 左单旋
void RotateL(Node* parent);
// 右左双旋
void RotateRL(Node* parent);
// 左右双旋
void RotateLR(Node* parent);
private:
Node* _root;
};2.1 "插入"操作(重点)
注意: 本篇实现的AVL树,平衡因子是右子树高度—左子树高度.
故: 当新增结点在父亲结点的左边时,左子树的高度+1,则平衡因子-1. 当新增结点在父亲结点的右边时,右子树的高度+1,则平衡因子+1.
子树的平衡因子变化,可能会影响祖先路径上的结点,需要继续向上更新.
(1) 当新增结点后,父节点的平衡因子变成0,则插入结束.
(2) 当新增结点后,父节点的平衡因子变成1或者-1,则需要向上更新.
(3)当新增结点后,父节点的平衡因子变成2或者-2需要旋转.
①:右旋
当继续向上更新到父节点是平衡因子-2时,则需要右旋. 因为左边比右边高,需要旋转到右边.使其平衡.
(1) 右旋具体图:
关键步骤:
使
cur成为新的父节点cur的右孩子,成为parent的左孩子parent成为cur的右孩子
(2)右旋抽象图:
更新平衡因子:
从抽象图可以看出,右旋旋转后,平衡因子cur parent都可以无脑设置为0.
代码实现:
//右旋
template<class K,class V>
void AVLTree<K,V>::RotateR(Node* parent)
{
Node* ppnode = parent->_parent;
Node* cur = parent->_left;
Node* cur_right = cur->_right;
//cur的右子树变成parent的左子树
if (cur_right) { //cur_right 可能不存在
parent->_left = cur_right;
cur_right->_parent = parent;//保持三叉连
}
else {
parent->_left = nullptr;
}
//parent变成cur的右子树
cur->_right = parent;
parent->_parent = cur;//保持三叉连
if (ppnode) {
cur->_parent = ppnode;
if (ppnode->_left == parent) { //如果是上面的左子树
ppnode->_left = cur;
}
else {
ppnode->_right = cur; //如果是上面的右子树
}
}
else { //如果ppnode是nullptr,则代表parent为root
_root = cur;
cur->_parent = nullptr;
}
parent->_bf = 0;
cur->_bf = 0;
}②左旋:
当继续向上更新到父节点平衡因子是2时,则需要左旋.
因为右边比左边高,需要旋转到左边,使其平衡.
(1)左旋具体图:
关键步骤:
使
cur成为新的父节点cur的左孩子,成为parent的右孩子parent成为cur的左孩子
(2)左旋抽象图
更新平衡因子:
从抽象图可以看出,左旋旋转后,平衡因子cur parent都可以无脑设置为0.
代码实现:
//左旋
template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)
{
Node* ppnode = parent->_parent;
Node* cur = parent->_right;
Node* cur_left = cur->_left;
//cur的右子树变成parent的左子树
if (cur_left) { //cur_right 可能不存在
parent->_right = cur_left;
cur_left->_parent = parent;//保持三叉连
}
else {
parent->_right = nullptr;
}
//parent变成cur的左子树
cur->_left = parent;
parent->_parent = cur;//保持三叉连
if (ppnode) {
cur->_parent = ppnode;
if (ppnode->_left == parent) { //如果是上面的左子树
ppnode->_left = cur;
}
else {
ppnode->_right = cur; //如果是上面的右子树
}
}
else { //如果ppnode是nullptr,则代表parent为root
_root = cur;
cur->_parent = nullptr;
}
//更新平衡因子
parent->_bf = 0;
cur->_bf = 0;
}③右左双旋
当cur->_bf 的值是-1，并且parent->_bf 的值是 2，如下图15结点，22结点，18结点这般成折线状。
（1）右左双旋具体图
（2）右左双旋抽象图
对于双旋，重点在于如何更新平衡因子。
双旋的重点！！！：
代码实现:
// 右左双旋
template<class K, class V>
void AVLTree<K, V>::RotateRL(Node* parent) {
Node* cur = parent->_right;
Node* cur_left = cur->_left;
RotateR(cur); //以parent的right作为新的parent进行右单旋
RotateL(parent);
//更新平衡因子(最重要)
if (cur_left->_bf == 0) { //情况1
parent->_bf = 0;
cur_left->_bf = 0;
cur->_bf = 0;
}
else if(cur_left->_bf == 1) { //情况3
parent->_bf = -1;
cur_left->_bf = 0;
cur->_bf = 0;
}
else if (cur_left->_bf == -1) { //情况2
parent->_bf = 0;
cur_left->_bf = 0;
cur->_bf = 1;
}
else {
assert(false);
}
}④左右双旋
与左右双旋类似，这里不过多介绍了，注意更新平衡因子！！！
（1）左右双旋具体图
（2）左右双旋抽象图
template<class K, class V>
void AVLTree<K, V>::RotateLR(Node* parent) {
Node* cur = parent->_left;
Node* cur_right = cur->_right;
RotateR(cur); //以parent的right作为新的parent进行右单旋
RotateL(parent);
//更新平衡因子(最重要)
if (cur_right->_bf == 0) {
parent->_bf = 0;
cur_right->_bf = 0;
cur->_bf = 0;
}
else if (cur_right->_bf == 1) {
parent->_bf = 0;
cur_right->_bf = 0;
cur->_bf = -1;
}
else if (cur_right->_bf == -1) {
parent->_bf = 1;
cur_right->_bf = 0;
cur->_bf = 0;
}
else {
assert(false);
}
}"插入"操作的代码实现:
template<class K,class V>
bool AVLTree<K,V>::Insert(const pair<K, V>& kv)
{
if (_root == nullptr) {
_root = new Node(kv);
return true;
}
Node* cur = _root, * parent = nullptr;
//寻找插入位置
while (cur) {
parent = cur;
if (_root->_kv.first > kv.first) {
cur = cur->_left;
}
else if (_root->_kv.first < kv.first) {
cur = cur->_right;
}
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) { //如果是插入在左边,平衡因子-1
parent->_bf--;
}
else if(parent->_right == cur) { //如果是插入在右边,//平衡因子+1
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);
}
}
}
return true;
}2.2 中序遍历:
由于中序遍历需要传参 参数为根节点，而根节点是私有成员变量，所以这里用再套一层函数的方法，是一个不错的设计。
template<class K, class V>
void AVLTree<K, V>::_InOrder(Node* root)
{
if (root == nullptr)return;
_InOrder(root->_left);
cout << root->_kv.first << "->" << root->_kv.second << endl;
_InOrder(root->_right);
}
template<class K, class V>
void AVLTree<K, V>::InOrder()
{
if (_root == nullptr)
{
cout << "空树" << endl;
return;
}
_InOrder(_root);
}2.3 AVL树的"高度"
同求二叉树的高度没有啥区别。
需要注意的是： 1处和2处，需要记录左右子树的根否则后面的都需要重新大量的重复计算。
template<class K, class V>
size_t AVLTree<K, V>::_Height(Node* root)
{
if (root == nullptr)
return 0;
int leftHeight = _Height(root->_left); //1
int rightHeight = _Height(root->_right); //2
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}2.4 验证AVL树
判断每棵树的平衡因子是否=右子树-左子树的高度即可。
template<class K, class V>
bool AVLTree<K, V>::_IsAVLTree(Node* root) {
if (root == nullptr)
return true;
int leftHight = _Height(root->_left);
int rightHight = _Height(root->_right);
if (rightHight - leftHight != root->_bf)
{
cout << "平衡因子异常:" << root->_kv.first << "->" << root->_bf << endl;
return false;
}
return abs(rightHight - leftHight) < 2
&& _IsAVLTree(root->_left)
&& _IsAVLTree(root->_right);
}结语
AVL树的平衡性使得它的插入、删除和查找操作的时间复杂度都是O(logn)，与红黑树相当。然而，由于AVL树在每次插入或删除时都需要进行平衡调整，所以它的常数比红黑树稍大，因此在实际应用中，红黑树更为常用。
后续会更新红黑树的介绍，很多人认为红黑树是比AVL树还要优秀的结构，不想要了解一下吗？ 还请保持关注哦！
腾讯云开发者
