二叉搜索树：【C++进阶学习】第五弹——二叉搜索树——二叉树进阶及set和map的铺垫-CSDN博客
目录
前言：
在前面我们学习二叉搜索树的时候，虽然大部分情况下二叉搜索树的效率都是很高的，但是如果是一组相对有序的数字，我们用二叉搜索树来排序就会显得比较麻烦了，因此，AVL树就出现了，下面就让我们一起来学习以下AVL树的相关知识
一、AVL树的概念
AVL树实际上就是特殊的二叉搜索树，是对二叉搜索树的改进，我们在用树形结构来查找或操作数据的时候，一般都是要从树根一层一层往下找，所以树高越低，效率越高，但是二叉搜索树在有些场景下比较麻烦，比如一个相对有序的数组{2，1，3，4，5，6}
这样一个数组如果通过二叉搜索树处理就会显得层数太多，效率很低
所以人们也就有了这样一种思考：我们可不可以通过某种操作让左右子树的高度差不超过1，这样就能极大的提高效率，这就是AVL树的概念
AVL树中任何节点的左右子树的高度差（平衡因子）绝对值不超过1。这意味着树始终保持平衡，避免了二叉搜索树在节点插入或删除后可能出现的退化现象。
二、AVL树的原理与实现
了解了AVL树的基本内容之后，接下来我们就来一步一步学习以下AVL树的原理到底是什么以及如何实现一个AVL树：
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) //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1
{}
};
AVL树的节点操作与二叉搜索树还是比较相似的，都有左子树右子树和父亲节点的叉式结构，比较不同的是加入了一个平衡因子
AVL树的插入
实现AVL树的重点就是解决AVL树的插入问题，而解决插入问题最关键的就是要做到如何让左右子树高度的绝对值适合不大于1，我们是通过合理的旋转来实现的，而且需要旋转的情况也是分为四种的：
RR型：左旋
LL型：右旋
RL型：先右旋，再左旋
LR型：先左旋，再右旋
下面我们来看这样几个例子：
1、RR型（左旋）
2、LL型（右旋）
3、LR型（先左旋，再右旋）
4、RL型（先右旋，再左旋）
操作与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;
cur->_parent = parent;
}
else
{
parent->_left = 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);
break;
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
//右单旋
RotateR(parent);
break;
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
//RL型
RotateRL(parent);
break;
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
//LR型
RotateLR(parent);
break;
}
}
else
{
assert(false);
}
}
return true;
}
AVL树的旋转
void RotateL(Node* parent) //左单旋（RR型）
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
parent->_right = subRL;
subR->_left = parent;
if(subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_parent = subR;
parent->_bf = 0;
subR->_bf = 0;
}
void RotateR(Node* parent) //右单旋（LL型）
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
parent->_left = subLR;
subL->_right = parent;
if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_parent = subL;
subL->_bf = parent->_bf = 0;
}
void RotateRL(Node* parent) //先右单旋，再左单旋（RL型）
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
//subRL自己就是新增点
parent->_bf = subR->_bf = 0;
}
else if (bf == -1)
{
//subRL的左子树上新增
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
//subRL的右子树上新增
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateLR(Node* parent) //先左单旋，再右单旋（LR型）
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
//subLR自己就是新增点
parent->_bf = subL->_bf = 0;
}
else if (bf == -1)
{
//subLR的左子树上新增
parent->_bf = 1;
subLR->_bf = 0;
subL->_bf = 0;
}
else if (bf == 1)
{
//subLR的右子树上新增
parent->_bf = 0;
subLR->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false);
}
}
AVL树的打印
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);
}
AVL树的检查
检查是否为AVL树，一方面我们可以通过打印的结果先来判断一下它是不是二叉搜索树，然后我们可以通过比较左右子树的高度差来判断它是否为AVL树（根据前面可知AVL树左右子树高度差最大为1）
//检查是否为AVL树
bool IsBalance()
{
return _IsBalance(_root);
}
int _High(Node* root)
{
if (root == nullptr)
return 0;
int LeftHigh = _High(root->_left);
int RightHigh = _High(root->_right);
return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int LeftHigh = _High(root->_left);
int RightHigh = _High(root->_right);
if (RightHigh - LeftHigh != root->_bf)
{
cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;
return false;
}
return abs(LeftHigh- RightHigh) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
三、实现AVL树的完整代码
AVLTree.h
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) //平衡因子起始值是0，当左子树插入一个节点时-1，右子树插入一个节点时+1
{}
};
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)
{
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;
cur->_parent = parent;
}
else
{
parent->_left = 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);
break;
}
else if (parent->_bf == -2 && cur->_bf == -1)
{
//右单旋
RotateR(parent);
break;
}
else if (parent->_bf == 2 && cur->_bf == -1)
{
//RL型
RotateRL(parent);
break;
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
//LR型
RotateLR(parent);
break;
}
}
else
{
assert(false);
}
}
return true;
}
void RotateL(Node* parent) //左单旋（RR型）
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
Node* parentParent = parent->_parent;
parent->_right = subRL;
subR->_left = parent;
if(subRL)
subRL->_parent = parent;
if (_root == parent)
{
_root = subR;
subR->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subR;
}
else
{
parentParent->_right = subR;
}
subR->_parent = parentParent;
}
parent->_parent = subR;
parent->_bf = 0;
subR->_bf = 0;
}
void RotateR(Node* parent) //右单旋（LL型）
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* parentParent = parent->_parent;
parent->_left = subLR;
subL->_right = parent;
if (subLR)
{
subLR->_parent = parent;
}
if (_root == parent)
{
_root = subL;
subL->_parent = nullptr;
}
else
{
if (parentParent->_left == parent)
{
parentParent->_left = subL;
}
else
{
parentParent->_right = subL;
}
subL->_parent = parentParent;
}
parent->_parent = subL;
subL->_bf = parent->_bf = 0;
}
void RotateRL(Node* parent) //先右单旋，再左单旋（RL型）
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 0)
{
//subRL自己就是新增点
parent->_bf = subR->_bf = 0;
}
else if (bf == -1)
{
//subRL的左子树上新增
parent->_bf = 0;
subRL->_bf = 0;
subR->_bf = 1;
}
else if (bf == 1)
{
//subRL的右子树上新增
parent->_bf = -1;
subRL->_bf = 0;
subR->_bf = 0;
}
else
{
assert(false);
}
}
void RotateLR(Node* parent) //先左单旋，再右单旋（LR型）
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 0)
{
//subLR自己就是新增点
parent->_bf = subL->_bf = 0;
}
else if (bf == -1)
{
//subLR的左子树上新增
parent->_bf = 1;
subLR->_bf = 0;
subL->_bf = 0;
}
else if (bf == 1)
{
//subLR的右子树上新增
parent->_bf = 0;
subLR->_bf = 0;
subL->_bf = -1;
}
else
{
assert(false);
}
}
//中序打印
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* root)
{
if (root == nullptr)
return;
_Inorder(root->_left);
cout << root->_kv.first << " ";
_Inorder(root->_right);
}
//检查是否为AVL树
bool IsBalance()
{
return _IsBalance(_root);
}
int _High(Node* root)
{
if (root == nullptr)
return 0;
int LeftHigh = _High(root->_left);
int RightHigh = _High(root->_right);
return LeftHigh > RightHigh ? LeftHigh + 1 : RightHigh + 1;
}
bool _IsBalance(Node* root)
{
if (root == nullptr)
return true;
int LeftHigh = _High(root->_left);
int RightHigh = _High(root->_right);
if (RightHigh - LeftHigh != root->_bf)
{
cout << _root->_kv.first << "当前节点平衡因子有问题" << endl;
return false;
}
return abs(LeftHigh- RightHigh) < 2
&& _IsBalance(root->_left)
&& _IsBalance(root->_right);
}
private:
Node* _root = nullptr;
};test.c
//AVL树
#include"AVLTree.h"
int main()
{
int a[] = { 16,3,7,11,9,26,18,14,15 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
}
t.Inorder();
cout << "输出1代表是AVL树，输出0代表不是：" << t.IsBalance() << endl;
return 0;
}
运行结果：
四、总结
AVL树的理解和实现总体来说还是比较难的，思路一定要搞清楚，代码实现上尽力而为
感谢各位大佬观看，创作不易，还请各位大佬点一个小小的赞！！！
标签：Node,bf,进阶,parent,C++,else,AVL,left,cur From： https://blog.csdn.net/2301_80220607/article/details/140446473