【C++】17.AVL树

🕗 发布于 2024-07-22 15:56 c++ 开发语言

一、AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树
左右子树高度之差（右子树-左子树）(简称平衡因子)的绝对值不超过1 (-1/0/1)

在这里插入图片描述
如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在 $O(log_2 n)$ ，搜索时间复杂度O( $log_2 n$ )。

二、AVL树的定义

template<class K,class V>
struct AVLTreeNode
{
struct AVLTreeNode* _left;//左孩子
struct AVLTreeNode* _right;//右孩子
struct AVLTreeNode* _parent;//父节点
int _bf;//平衡因子：右子树高度-左子树高度
pair<K, V> _kv;

AVLTreeNode(pair<K,V> kv=pair<K,V>())
:_left(nullptr),
_right(nullptr),
_parent(nullptr),
_bf(0),
_kv(kv)
{}
};

三、AVL树的插入

AVL树就是在二叉搜索树的基础上引入了平衡因子，因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步：

1. 按照二叉搜索树的方式插入新节点
1. 调整节点的平衡因子

通过画图分析我们知道插入节点可能会导致父节点的平衡因子发生改变：

插入在左子树上，平衡因子- -；插入在右子树上，平衡因子++

而更新完平衡因子后又有如下情况：

parent的平衡因子为0
说明更新前 parent 的平衡因子是 1 或 -1 ，而新的节点插入在矮的那边，parent 所在子树高度不变，不需要继续向上更新
parent的平衡因子为±1
说明更新前 parent 的平衡因子是 0 ，新节点无论插入在哪一边， parent 所在子树高度都会发生改变，都需要继续向上检查是否需要更新
parent的平衡因子为±2
说明更新之前 parent 的平衡因子是 1 或 -1 ，新节点插入在本身就高的那一边，进一步导致了 parent 所在子树的不平衡，表示需要旋转以适应规则

bool Insert(pair<K, V> kv)
{
//寻找新结点插入位置
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}

Node* cur = _root;
while (cur)
{
if (kv.first < cur->_kv.first)
cur = cur->_left;
else if (kv.first > cur->_kv.first)
cur = cur->_right;
else
return false;
}

//插入新结点
Node* parent = cur->_parent;
cur = new Node(kv);
cur->_parent = parent;
if (cur = parent->_left)
parent->_left = cur;
else
parent->_right = cur;

//更新平衡因子
while (parent)
{
//插入右边就++，插入左边就--
if (cur = parent->_left)
parent->_bf--;
else
parent->_bf++;

//平衡因子此时为0，就说明原来是±1，插入之后平衡因子变为0了
if (parent->_bf == 0)
{
break;
}
//平衡因子此时为±1，需要判断祖先是否需要更新
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
//平衡因此此时为±2，说明插入的新节点加剧了不平衡，因此需要旋转
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 if (parent->_bf == -2 && cur->_bf == 1)
RotateLR(parent);
else
assert(0);
break;
}
//平衡因子为其他值说明上述逻辑有错误
else
{
assert(0);
}
}
return true;
}

四、AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

4.1 左单旋

在这里插入图片描述
结论：当parent节点的平衡因子为1，parent->_parent节点的平衡因子为2时需要向左单旋。

void RotateL(Node* parent)
{
Node* parentR = parent->_right;
Node* parentRL = parentR->_left;

Node* parentParent = parent->_parent;//保存父节点的父节点

//重新链接
parent->_right = parentRL;
if (parentRL)
parentRL->_parent = parent;

parentR->_left = parent;
parent->_parent = parentR;

//判断父节点是否为根节点
if (parentParent == nullptr)
{
_root = parentR;
parentR->_parent = nullptr;
}
else
{
parentR->_parent = parentParent;
if (parent == parentParent->_left)
parentParent->_left = parentR;
else
parentParent->_right = parentR;
}

parent->_bf = parentR->_bf = 0;//更新平衡因子
}

4.2 右单旋

在这里插入图片描述
结论：当parent节点的平衡因子为-1，parent->_parent节点的平衡因子为-2时需要向右单旋。

void RotateR(Node* parent)
{
Node* parentL = parent->_left;
Node* parentLR = parentL->_right;

Node* parentParent = parent->_parent;//保存父节点的父节点

//重新链接
parent->_left = parentLR;
if (parentLR)
parentLR->_parent = parent;

parentL->_right = parent;
parent->_parent = parentL;

if (parentParent == nullptr)
{
_root = parentL;
parentL->_parent = nullptr;
}
else
{
parentL->_parent = parentParent;
if (parent == parentParent->_left)
parentParent->_left = parentL;
else
parentParent->_right = parentL;
}

parent->_bf = parentL->_bf = 0;
}

4.3 左右双旋

在这里插入图片描述
结论：当parent节点的平衡因子为1，parent->_parent节点的平衡因子为-2时需要左右双旋

void RotateLR(Node* parent)
{
Node* parentL = parent->_left;
Node* parentLR = parentL->_right;
int bf = parentLR->_bf;

RotateL(parentL);
RotateR(parent);

if (bf == 0)
{
parent->_bf = 0;
parentL->_bf = 0;
parentLR->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = 0;
parentL->_bf = -1;
parentLR->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 1;
parentL->_bf = 0;
parentLR->_bf = 0;
}
else
assert(0);
}

4.4 右左双旋

在这里插入图片描述
结论：当parent节点的平衡因子为-1，parent->_parent节点的平衡因子为2时需要右左双旋

void RotateRL(Node* parent)
{
Node* parentR = parent->_right;
Node* parentRL = parentR->_left;
int bf = parentRL->_bf;

RotateR(parentR);
RotateL(parent);

if (bf == 0)
{
parent->_bf = 0;
parentR->_bf = 0;
parentRL->_bf = 0;
}
else if (bf == 1)
{
parent->_bf = -1;
parentR->_bf = 0;
parentRL->_bf = 0;
}
else if (bf == -1)
{
parent->_bf = 0;
parentR->_bf = 1;
parentRL->_bf = 0;
}
else
assert(0);
}

总结：
假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑:

parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为parentR,
当parentR的平衡因子为1时，执行左单旋
当parentR的平衡因子为-1时，执行右左双旋

parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为parentL,
当parentL的平衡因子为-1是，执行右单旋
当parentL的平衡因子为1时，执行左右双旋

旋转完成后，原pParent为根的子树个高度降低，已经平衡，不需要再向上更新。

五、AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

验证其是否为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
验证其是否为平衡树
- 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
- 节点的平衡因子是否计算正确

bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}

int Height(Node* root)
{
if (root == nullptr)
return 0;
int left = Height(root->_left);
int right = Height(root->_right);

return left > right ? left + 1 : right + 1;
}

bool _IsBalanceTree(Node* root)
{
if (root == nullptr)
return true;

int LeftHeight = Height(root->_left);
int RightHeight = Height(root->_right);

int diff = RightHeight- LeftHeight ;
if (diff != root->_bf || abs(LeftHeight - RightHeight) > 1)
return false;
return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}

六、AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即 $log_2 (N)$ 。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合。

原文地址：https://blog.csdn.net/2301_80258336/article/details/140593416

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：String/StringBuffer/StringBuilder 区别（详解）
下一篇：哪个开源Wiki系统最好用？2024年6款优质推荐

【图灵完备 Turing Complete】游戏经验攻略分享 Part.6 处理器架构2 & 函数
FIN
阅读更多2024-09-22
[SDX35+WCN6856]SDX35 开启class/gpio子系统配置操作说明
WCN6856 器件是一款高度集成的片上系统（SoC）支持 802.11ax Wi-Fi 和蓝牙（BT） 5.3。这WCN6856 支持在 2.4 GHz 和 5 GHz 上同时运行5GHz 或
阅读更多2024-09-22
如何使用IIC外设（硬件IIC）
在使用软件进行 IIC 通信时，需要用程序代码控制IO口按照通信协议的要求做出动作，程序代码是比较繁琐的；在使用芯片自带的 IIC 外设，即硬件 IIC 进行通信时，我们可以直接调用并配置相关的库函数
阅读更多2024-09-22
YOLOV8& OpenCV + usb 相机实时识别
【代码】YOLOV8& OpenCV + usb 相机实时识别。
阅读更多2024-09-22
Vue.js与Flask/Django后端配合
前后端分离的核心思想是将Web应用的前端界面与后端服务分离开发、部署和维护。在这种架构下，前端主要负责用户界面的渲染和交互逻辑，而后端则负责处理业务逻辑、数据库交互等。两者通过API（通常是RESTf
阅读更多2024-09-22
2024“华为杯”中国研究生数学建模竞赛（A题）深度剖析_数学建模完整过程+详细思路+代码全解析
目标是优化风力涡轮机的功率调度，使其在给定的实时风速数据下，最小化涡轮机关键组件（如塔架和主轴）的疲劳损伤。问题的挑战在于，考虑通信延迟和测量噪声的同时，要确保功率输出与风速变化的响应快速且准确。
阅读更多2024-09-22
【C++前缀和状态压缩】2588. 统计美丽子数组数目|1696
给你一个下标从 0 开始的整数数组nums 。每次操作中，你可以：选择两个满足 0
阅读更多2024-09-22
如何在qtcreator debugger上运行gdb命令
在main.cpp文件的第7行加入条件断点，条件为i==5。在main.cpp文件的第5行加入断点。
阅读更多2024-09-22
【LLM学习之路】9月16日第六天
可以取平均也可以求和参数解析input （N，*） N是batchsize，星号代表可以是任意维度不是输入的参数，只是描述数据target 形状要同上。
阅读更多2024-09-22
VCNet论文阅读笔记
背景：因果推断（casual inference）在智能营销、药物治疗、决策上有广泛的应用，比如优惠券对用户购买意愿的影响、药品多大程度改善或治愈疾病、某项政策提高多少就业率等。（即，预估一种干预因素
阅读更多2024-09-22