【数据结构进阶】AVL树
CSDN 2024-08-17 17:35:02 阅读 77
🔥个人主页: Forcible Bug Maker
🔥专栏: C++ || 数据结构
目录
🌈前言🔥AVL树的概念🔥AVL树的自实现==AVL树结点的定义====AVL树需实现的函数接口====AVL树的插入====AVL树的旋转==右单旋左单旋左右双旋右左双旋
==Insert====Find====拷贝构造====Size====析构函数====二叉搜索树的验证==
🌈结语
🌈前言
本篇博客主要内容:AVL树的介绍,以及其底层代码逻辑和实现。
前面对map/multimap/set/multiset进行了简单的介绍,在其文档介绍中发现,这几个容器有个共同点是:其底层都是按照二叉搜索树来实现的,但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N),因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现。
而我们今天所要说的AVL树就是平衡树的一种。
🔥AVL树的概念
二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
一颗AVL树,是具有以下性质的二叉搜索树:
它的左右子树都是AVL树左右子树高度差(简称平衡因子)的绝对值不超过1(1/0/-1)
如果一个二叉搜索树树的高度平衡,那它就是AVL树。如果它有n个结点,其高度可以保持在<code>O(log_2 N),搜索复杂度同样为O(log_2 N)
。
🔥AVL树的自实现
AVL树结点的定义
AVL树的结点包含四个成员变量,一个pair:存储Key和Value;三个指针:指向左孩子结点的指针,指向右孩子结点的指针,指向父结点的指针;最后还有一个_bf,存储当前结点平衡因子的值(反映以当前结点为根的树的平衡状态)。
template<class K, class V>
struct AVLTreeNode
{
AVLTreeNode<K, V>(const std::pair<K, V>& kv)
: _kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{ }
std::pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf; // balance factor
};
AVL树需实现的函数接口
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
// 默认构造
AVLTree() = default;
// 拷贝构造
AVLTree(const AVLTree<K, V>& t);
// AVL树的插入
bool Insert(const std::pair<K,V> kv);
// AVL树的查找
Node* Find(const K& key);
// AVL树的析构
~AVLTree();
// AVL树的验证
bool IsAVLTree();
// 计算结点数
size_t Size();
private:
Node* _root = nullptr;
};
}
AVL树的插入
往AVL树中插入元素,首先按照二叉搜索树的插入方式进行结点的插入。再根据插入元素的位置调整平衡因子,如平衡因子的绝对值大于1(结点左右孩子高度差的绝对值大于1),则需要对树的平衡进行调整(这个调整的过程常被称为旋转)。
在已有的AVL树中插入结点,更新平衡因子遵循以下规律:
插入的cur结点为其父节点parent的左孩子,parent结点的平衡因子-1插入的cur结点为其父节点parent的右孩子,parent结点的平衡因子+1
在父节点parent更新平衡因子之后,是否继续往祖先更新平衡因子,遵循以下规律:
parent平衡因子==0(平衡因子更新前为1/-1)
parent所在子树高度不变,不需继续往上更新。parent的平衡因子==1/-1(平衡因子更新前为0)
parent所在子树高度变化,需要继续往上更新。parent的平衡因子==2/-2(平衡因子更新前为1/-1)
插入结点在高的一边,加剧了parent所在子树的不平衡,旋转处理。
AVL树的旋转
旋转是为了将不平衡的二叉搜索树调整为平衡的二叉搜索树。
主要分四种旋转,两种单旋:右单旋和左单旋;以及两种双旋:左右双旋和右左双旋。
右单旋
当将新结点插入到较高左子树的左侧时(左左:右单旋),进行右单旋。
<code>// 右单旋
void RotateR(Node* parent)
{
// subL可看作图中30,parent可看作图中60
Node* subL = parent->_left;
// subLR可看作图中b
Node* subLR = subL->_right;
// parentParent为parent的父节点
Node* parentParent = parent->_parent;
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
subL->_parent = parentParent;
parent->_left = subLR;
parent->_parent = subL;
if (parentParent == nullptr) {
_root = subL;
}
else {
if (parentParent->_left == parent) {
parentParent->_left = subL;
}
else
parentParent->_right = subL;
}
// 单旋后记得调整平衡因子
subL->_bf = 0;
parent->_bf = 0;
}
左单旋
当将新结点插入到较高右子树的右侧时(右右:左单旋),进行左单旋。
<code>// 左单旋
void RotateL(Node* parent)
{
// subR可看作图中60,parent可看作图中30
Node* subR = parent->_right;
// subRL可看作图中b
Node* subRL = subR->_left;
// parentParent为parent的父结点
Node* parentParent = parent->_parent;
if (subRL)
subRL->_parent = parent;
subR->_left = parent;
subR->_parent = parentParent;
parent->_right = subRL;
parent->_parent = subR;
if (parentParent == nullptr) {
_root = subR;
}
else {
if (parentParent->_left == parent) {
parentParent->_left = subR;
}
else
parentParent->_right = subR;
}
// 单旋结束调整平衡因子
subR->_bf = 0;
parent->_bf = 0;
}
左右双旋
双旋中,主要考虑的因素是平衡因子的调整。
当新结点插入较高左子树的右侧(左右:先左单旋再右单旋),进行左右双旋。
<code>void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
// 根据subLR的平衡因子
// 可以知道结点插入的位置(其 左子树/右子树)
// 从而便于调整subL和parent的平衡因子
int bf = subLR->_bf;
// 左右双旋
RotateL(parent->_left);
RotateR(parent);
// 调整平衡因子
if (bf == 0) {
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == 1) {
subL->_bf = -1;
subLR->_bf = 0;
parent->_bf = 0;
}
else if (bf == -1) {
subL->_bf = 0;
subLR->_bf = 0;
parent->_bf = 1;
}
else assert(false);
}
右左双旋
双旋中,主要考虑的因素是平衡因子的调整。
当新结点插入较高右子树的左侧(右左:先右单旋再左单旋),进行右左双旋。
<code>void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
// 根据subRL的平衡因子
// 可以知道结点插入的位置(其 左子树/右子树)
// 从而便于调整subR和parent的平衡因子
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);
}
Insert
AVL树,插入实现代码:
bool Insert(const std::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;
}
if (parent->_kv.first < kv.first) {
cur = new Node(kv);
parent->_right = cur;
cur->_parent = parent;
}
else {
cur = new Node(kv);
parent->_left = cur;
cur->_parent = parent;
}
// 开始对平衡因子进行更新
// 出现不平衡进行时旋转调整
while (parent) {
if (parent->_right == cur)
parent->_bf++;
else if (parent->_left == cur)
parent->_bf--;
if (parent->_bf == 0)
break;
else if (parent->_bf == 2) {
if (parent->_right->_bf == 1) {
RotateL(parent);
}
else if (parent->_right->_bf == -1) {
RotateRL(parent);
}
break;
}
else if (parent->_bf == -2) {
if (parent->_left->_bf == -1) {
RotateR(parent);
}
else if (parent->_left->_bf == 1) {
RotateLR(parent);
}
break;
}
cur = parent;
parent = parent->_parent;
}
return true;
}
Find
AVL树的查找和二叉搜索树相同:
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 nullptr;
}
拷贝构造
与二叉搜索树相同。
AVLTree(const AVLTree<K, V>& t)
{
_root = _Copy(t._root);
}
Node* _Copy(Node* root)
{
if (root == nullptr)return nullptr;
Node* newRoot = new Node(root->_kv);
newRoot->_left = _Copy(root->_left);
newRoot->_right = _Copy(root->_right);
return newRoot;
}
Size
计算AVL树的结点个数。
size_t Size()
{
return _Size(_root);
}
size_t _Size(Node* root)
{
return root == nullptr ? 0 : _Size(root->_left) + _Size(root->_right) + 1;
}
析构函数
析构也是通过递归实现,释放结点。
~AVLTree()
{
Destroy(_root);
_root = nullptr;
}
void Destroy(Node* root)
{
if (root == nullptr)return;
Destroy(root->_left);
Destroy(root->_right);
delete root;
}
二叉搜索树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制,因此要验证AVL树,可以分两步:
验证其为二叉搜索树
如果中序遍历可得到一个有序的序列,就说明为二叉搜索树验证其为平衡树
每个节点子树高度差的绝对值不超过1节点的平衡因子是否计算正确(右树高度 - 左树高度 == 当前结点平衡因子)
// AVL树的验证
bool IsAVLTree()
{
return _IsAVLTree(_root);
}
bool _IsAVLTree(Node* root)
{
if (root == nullptr)
return true;
int left_bf = _Height(root->_left);
int right_bf = _Height(root->_right);
// 每个节点子树高度差的绝对值不超过1
if (abs(left_bf - right_bf) >= 2) {
return false;
}
// 节点的平衡因子是否计算正确
if (right_bf - left_bf != root->_bf)
return false;
return _IsAVLTree(root->_left)
&& _IsAVLTree(root->_right);
}
🌈结语
AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这样可以保证查询时高效的时间复杂度,即log_2 (N)
。但是如果要对AVL树做一些结构修改的操作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,有可能一直要让旋转持续到根的位置。因此:如果需要一种查询高效且有序的数据结构,而且数据的个数为静态的(即不会改变),可以考虑AVL树,但如果要对其进行大量增删,则不建议使用。
本篇博客介绍了AVL树及其基本实现,感谢大家的支持♥
声明
本文内容仅代表作者观点,或转载于其他网站,本站不以此文作为商业用途
如有涉及侵权,请联系本站进行删除
转载本站原创文章,请注明来源及作者。