C++之AVL树的使用以及原理详解

server/2024/9/25 10:28:45/

1.AVL树

1.1AVL树的概念

 1.2AVL树的定义

1.3AVL树的插入

 1.4AVL树的旋转

 1. 右单旋

2. 左单旋

3. 左右双旋

4. 右左双旋

 1.5AVL树的验证

1.6AVL的实现

在之前对map/multimap/set/multiset进行了简单的介绍（C++之map_set的使用-CSDN博客），在其文档介绍中发现，这几个容器有个共同点是：其底层都是按照二叉搜索树来实现的，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现。

1.AVL树

1.1AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。

因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

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

A.它的 左右子树都是AVL树

B.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

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

 1.2AVL树的定义

template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left; //左子树AVLTreeNode<K, V>* _right;//右子树AVLTreeNode<K, V>* _parent;//父节点int _bf; //平衡因子pair<K, V> _kv;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

 AVLTreeNode 中的成员包括：

  • _left：指向左子节点的指针。
  • _right：指向右子节点的指针。
  • _parent：指向父节点的指针。
  • _kv：存储键值对的 pair 对象，其中键的类型为 K，值的类型为 V。
  • _bf：平衡因子，用于表示节点的平衡状态。
  • 对于_bf我们通常用一个树的右子树的高度减去左子树的高度来表示_bf

1.3AVL树的插入

AVL树，具有二叉搜索树的性质，同时还在二叉搜索树的基础上增加了平衡因子bf

AVL树的插入分为下面两步：

1、按搜索树规则插入
2、更新平衡因子

对于插入，分为三种情况：

1.插入该节点之后 父节点的平衡因子变为了0（-1变成0  或者   1变成0），这种情况说明插入节点没有对祖先的平衡因子造成影响，不需要进行处理。

更新后，p->bf == 0p所在的子树高度不变，不会影响爷爷说明更新前，p的bf是1 或者 -1，p的矮的那边插入了节点，左右均衡了，p的高度不变，不会影响爷爷
更新结束

2.插入之后父节点的平衡因子变成了1或者-1，这个时候以父节点的平衡因子是从0 变成1或者-1的，说明以父节点为根节点的树的高度发生了变化，并且高度的变化还有可能会影响祖先 的平衡因子，所以这个时候我们需要向上进行判断 祖先节点的平衡因子。

更新后，p->bf==1/-1，p所在的子树的高度变了，会影响爷爷说明更新前，p的bf是0，p的有一边插入，p变得不均衡，但是不违反规则会影响爷爷p的高度变了，
继续往上更新

3.插入之后父节点的平衡因子变成了2或者-2
更新后，p->bf==2/-2,说明p所在的子树违反了平衡规则，需要进行处理 ->旋转

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;}else{parent->_left = cur;}cur->_parent = parent;while (parent){if(cur == parent->left){parent->_bf--;}else{parent->_bf++;}//pCur插入后，pParent的平衡因子一定需要调整，在插入之前，pParent//的平衡因子分为三种情况：-1，0, 1, 分以下两种情况：//1. 如果pCur插入到pParent的左侧，只需给pParent的平衡因子-1即可//2. 如果pCur插入到pParent的右侧，只需给pParent的平衡因子+1即可if (parent->_bf == 0){break;}else if (parent->_bf == 1 || parent->_bf == -1){cur = 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){RotateLR(parent);}else{RotateRL(parent); //旋转函数的代码看下方}break;}else{// 插入之前AVL树就有问题assert(false);}}return true;}

 1.4AVL树的旋转

如果某个节点的平衡因子因为插入了新的节点变成了2/-2，此时不满足AVL树的规则，那我们就会对该树进行旋转，旋转之后 平衡因子就会回到插入节点之前的 状态，不会对上层产生影响。

 1. 右单旋

新节点插入较高左子树的左侧---左左

上图在插入前，AVL树是平衡的，新节点插入到30的左子树(注意：此处不是左孩子)中，30左子树增加了一层，导致以60为根的二叉树不平衡，要让60平衡，只能将60左子树的高度减少一层，右子树增加一层，

即将左子树往上提，这样60转下来，因为60比30大，只能将其放在30的右子树，而如果30有右子树，右子树根的值一定大于30，小于60，只能将其放在60的左子树，旋转完成后，更新节点的平衡因子即可。在旋转过程中，有以下几种情况需要考虑：

1. 30节点的右孩子可能存在，也可能不存在

2. 60可能是根节点，也可能是子树

如果是根节点，旋转完成后，要更新根节点

如果是子树，可能是某个节点的左子树，也可能是右子树

void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}

2. 左单旋

新节点插入较高右子树的右侧---右右：

void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}

3. 左右双旋

新节点插入较高左子树的右侧---左右：先左单旋再右单旋
 

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新

void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}

4. 右左双旋

 新节点插入较高右子树的左侧---右左：先右单旋再左单旋
 

 

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

1. pParent的平衡因子为2，说明pParent的右子树高，设pParent的右子树的根为pSubR

当pSubR的平衡因子为1时，执行左单旋当pSubR的平衡因子为-1时，执行右左双旋

2. pParent的平衡因子为-2，说明pParent的左子树高，设pParent的左子树的根为pSubL

当pSubL的平衡因子为-1是，执行右单旋当pSubL的平衡因子为1时，执行左右双旋

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

 1.5AVL树的验证

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

1. 验证其为二叉搜索树

如果中序遍历可得到一个有序的序列，就说明为二叉搜索树

2. 验证其为平衡树

每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)

节点的平衡因子是否计算正确

 

int _Height(PNode pRoot);
bool _IsBalanceTree(PNode pRoot)
{
// 空树也是AVL树
if (nullptr == pRoot) return true;
// 计算pRoot节点的平衡因子：即pRoot左右子树的高度差
int leftHeight = _Height(pRoot->_pLeft);
int rightHeight = _Height(pRoot->_pRight);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者
// pRoot平衡因子的绝对值超过1，则一定不是AVL树
if (diff != pRoot->_bf || (diff > 1 || diff < -1))
return false;
// pRoot的左和右如果都是AVL树，则该树一定是AVL树
return _IsBalanceTree(pRoot->_pLeft) && _IsBalanceTree(pRoot-
>_pRight);
}

1.6AVL的实现

template<class K, class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // balance factorpair<K, V> _kv;AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _bf(0), _kv(kv){}
};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;}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 = 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){RotateLR(parent);}else{RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}void RotateR(Node* parent) {Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}private:Node* _root = nullptr;
};


http://www.ppmy.cn/server/16640.html

相关文章

【计算机网络】成功解决 ARP项添加失败：请求的操作需要提升

【计算机网络】成功解决 ARP项添加失败：请求的操作需要提升

最近在用Wireshark做实验时候&#xff0c;需要清空本机ARP表和DNS缓存&#xff0c;所以在cmd窗口输入以下命令&#xff0c; 结果发生了错误&#xff1a;ARP项添加失败&#xff1a;请求的操作需要提升 一开始我还以为是操作的命令升级了&#xff0c;但是后面发现其实只是给的权…
阅读更多...
为什么分类问题不能使用mse损失函数，更容易理解版本

为什么分类问题不能使用mse损失函数，更容易理解版本

分类问题通常不适合使用均方误差&#xff08;Mean Squared Error&#xff0c;MSE&#xff09;损失函数&#xff0c;原因如下&#xff1a; 1.输出差异&#xff1a; 输出差异的度量不同&#xff1a;MSE损失函数是基于预测值和真实值之间的差异的平方和进行计算的&#xff0c;适…
阅读更多...
1小时学会SpringBoot3+Vue3前后端分离开发

1小时学会SpringBoot3+Vue3前后端分离开发

首发于Enaium的个人博客 引言 大家可能刚学会Java和Vue之后都会想下一步是什么&#xff1f;那么就先把SpringBoot和Vue结合起来&#xff0c;做一个前后端分离的项目吧。 准备工作 首先你需要懂得Java和Vue的基础知识&#xff0c;环境这里就不多说了&#xff0c;直接开始。 …
阅读更多...
DAC音频解码芯片DP7398立体声数模转换芯片

DAC音频解码芯片DP7398立体声数模转换芯片

DP7398 Pin TO Pin CS4398和CS43122&#xff0c;同轴光纤DAC解码&#xff0c;支持HIFI播放器。 产品介绍 DP7398 是一个立体声 24 位/1 92kHz 数模转换芯片。 该 D/A 系统包括数字去加重、半分贝步长音量控制、 ATAP I 通道混频、可选择的快速和慢速数字插补滤波器和过采样多位…
阅读更多...
【第六章】STM32 - 软件I2C读取MPU6050

【第六章】STM32 - 软件I2C读取MPU6050

关联&#xff1a; STM32总结超全笔记【秋招自用】https://blog.csdn.net/Xiaoxuexxxxx/article/details/137509422?csdn_share_tail%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22137509422%22%2C%22source%22%3A%22Xiaoxuexxxxx%22%7D 【MPU…
阅读更多...
Android kotlin 协程异步async与await介绍与使用

Android kotlin 协程异步async与await介绍与使用

一、介绍 在kotlin语言中&#xff0c;协程是一个处理耗时的操作&#xff0c;但是很多人都知道同步和异步&#xff0c;但是不知道该如何正确的使用&#xff0c;如果处理不好&#xff0c;看似异步&#xff0c;其实在runBloacking模块中使用的结果是同步的。 针对如何同步和如何异…
阅读更多...
linux 系统文件目录颜色及特殊权限对应的颜色

linux 系统文件目录颜色及特殊权限对应的颜色

什么决定文件目录的颜色和背景&#xff1f; 颜色 说明 栗子 权限白色表示普通文件 蓝色表示目录 绿色表示可执行文件 浅蓝色链接文件 黄色表示设备文件 红色 表示压缩文件 红色闪烁表示链接的文件有问题 灰色 表示其它文件 可以用字符表示文件的类型&am…
阅读更多...
Rust序列化和反序列化

Rust序列化和反序列化

Rust 编写python 模块 必备库 docker 启动 nginx 服务 NGINX 反向代理配置
阅读更多...
最新文章

Copyright @ 2022~2023