C++ AVL树(旋转)

news/2024/4/17 8:32:25

我们之前学习了搜索二叉树,我们知道普通的搜索二叉树会有特殊情况出现使得二叉树的两枝极其不平衡形成我们通俗说的歪脖子树:

这样的树一定会使得我们的增删查的效率变低;为了避免这种极端的情况出现,在1962年有两位伟大的俄罗斯数学家Adelson-VelskyLandis发明的;它们通过旋转使得我们的树的任意节点的左右子树高度差不超过2;使得搜索二叉树总会是一颗平衡的搜索二叉树;

我们怎么知道我们的左右子树的高度差呢?

AVL树的节点

我们这个时候就需要在搜索二叉树的基础上对我们的节点进行修改了,给我们的节点增加一个平衡因子_balance factor(_bf);

_bf平衡因子

介绍_bf:

_bf是如何计算的呢?创作者规定 _bf=右子树的深度-左子树的深度; 也就是说,我们每次我们插入一个新节点到我们当前节点的左边的时候_bf需要减一,当新节点插入到我们当前节点的右边的时候_bf加一;

template<class K,class V>
struct AVLTreeNode
{typedef AVLTreeNode<K,V> node;node* _left;node* _right;node* _parent;pair<K,V> _data;int _bf;//balance factor平衡因子AVLTreeNode(const pair<K, V>& data):_left(nullptr), _right(nullptr),_parent(nullptr),_data(data),_bf(0){}
};

可以看到,我们的AVL树的成员增加了_bf平衡因子和_parent父亲节点的指针;

有了描述每个节点的条件,要开始组织起来这些节点了,我们需要插入一个个节点;

插入节点

一开始插入节点是与搜索二叉树相同,我们需要先找到节点插入的位置,然后再将新增节点连接到我们的原树的叶子节点的末端,这个时候插入就完成了;

不同的是插入完成后,我们需要更新我们父亲节点的_bf平衡因子;采用上方所说的插入位置在父亲节点左侧时,父亲节点_bf-1,插入在父亲节点右侧时当前节点_bf+1;更新完成父亲节点后向上不断遍历修改父亲的父亲节点;而这个遍历我们又需要分情况遍历;

插入操作(和搜索二叉树中操作相同)
if (_root == nullptr)
{_root = new node(data);return true;
}
node* cur = _root;
node* parent = _root;
while (cur)
{if (data.first < cur->_data.first){parent = cur;cur = cur->_left;}else if (data.first > cur->_data.first){parent = cur;cur = cur->_right;}else{return false;}
}
cur = new node(data);
cur->_parent = parent;
if (data.first < parent->_data.first)
{parent->_left = cur;
}
else
{parent->_right = cur;
}
以上是普通的插入操作,下面需要进行平衡因子更新

更新_bf

情况1:父亲节点的_bf更新为1或-1

如果父节点的_bf为1或者1时就代表我们的父节点的左边或者右边新插入了节点,我们我们当前父节点为根的子树高度增加了,从而我们又会影响到父亲节点的父亲节点;所以我们需要继续所以向上遍历让父亲节点成为新插入的节点,更新父亲节点的父亲节点成为parent(父亲),更新新的父亲的_bf;

 情况2:父亲节点的_bf更新为0

 此时说明我们的父亲节点为根节点的树原本是不平衡的,但是由于我们插入的新节点补齐了这颗树;使得父亲节点的_bf变为了0,这个时候由于父亲节点为根的树高度没有变化;所以父亲节点上层的节点自然也不需要更新_bf所以这个时候可以直接退出遍历了;

情况3:父亲节点的_bf绝对值大于1

这个时候,我们需要进行旋转来降低父节点为根的树高度了

循环向上更新_bf
while (parent)
{if (cur == parent->_left){parent->_bf--;}else{parent->_bf++;}if (parent->_bf == 1 || parent->_bf == -1)//-1or1时需要继续更新平衡因子{cur = parent;parent = parent->_parent;	}else if (parent->_bf == 0)//因子为0是将树补齐了不需要再向上更新了{break;}else if (parent->_bf == 2 || parent->_bf == -2)//2or-2时需要旋转减小树的高度{if (parent->_bf == -2 && parent->_left->_bf == -1)//左子树的左子树高右旋转{RotateR(parent);}else if (parent->_bf == 2 && parent->_right->_bf == 1)//右子树的右子树高左旋转{RotateL(parent);}else if (parent->_bf == -2 && parent->_left->_bf == 1)//左子树的右子树高,先右子树左旋再左子树右旋{RotateLR(parent);}else if (parent->_bf == 2 && parent->_right->_bf == -1)//右子树的左子树高,先左子树右旋再右子树左旋{RotateRL(parent);}else{assert(false);}break;}
}

 旋转

这个操作就是AVL最精华的部分了;我们知道是当树左右两边高度相差超高1的时候就需要旋转了;旋转主要是靠画图理解;

我们需要注意的是我们旋转的树是一般是子树(父节点为根时为整棵树);

而旋转又分为四种旋转情况:

为了方便描述我们将当前树的根节点同一叫根节点;

单旋

情况1:根节点_bf为-2根节点左节点_bf为-1时(右单旋)

当根节点_bf为-2时说明我们这棵树的左子树高度要比右子树高2个节点的高度,根左节点的_bf为-1又说明我们左子树的左子树比左子树的右子树高1个节点的高度,也就是如下图:

我们需要进行单旋,因为是左树高,所以需要进行右旋转,将根节点旋转为左节点的右节点

右单旋
void RotateR(node* parent)
{node* subl = parent->_left;node* sublr = subl->_right;parent->_left = sublr;if (sublr)sublr->_parent = parent;node* ppnode = parent->_parent;subl->_right = parent;parent->_parent = subl;if (ppnode == nullptr){_root = subl;_root->_parent = nullptr;}else{subl->_parent = ppnode;if (ppnode->_left == parent){ppnode->_left = subl;}else{ppnode->_right = subl;}}parent->_bf = subl->_bf = 0;return;
}

 情况2:根节点_bf为2根节点右节点_bf为1时(左单旋)

这种情况就是情况1的对立边,这次是右树的右子树高,我们需要进行左单旋;

左单旋
void RotateL(node* parent)
{node* subr = parent->_right;node* subrl = subr->_left;parent->_right = subrl;if (subrl)subrl->_parent = parent;node* ppnode = parent->_parent;subr->_left = parent;parent->_parent = subr;if (ppnode == nullptr){_root = subr;_root->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subr;}else{ppnode->_right = subr;}subr->_parent = ppnode;}parent->_bf = subr->_bf = 0;
}

 单旋之后我们的parent和左节点的_pf都为0;

双旋

情况3:根节点_pf为-2根节点的左节点_pf为1(左右双旋)

这种情况就是我们的根节点左树高,但左数中的右树高,我们需要进行双旋:

如何左右双旋如图:

 

值得注意的是双旋我们的_bf是需要更新的;我们需要通过sublr的_bf来判断更新值

 代码实现

void RotateLR(node* parent)
{node* subl = parent->_left;node* sublr = subl->_right;int flag = sublr->_bf;RotateL(subl);//左旋右子树(树中树)RotateR(parent);//右旋左子树//更新平衡因子if (flag == 1)//插入位置为树中树的右树{parent->_bf = 0;subl->_bf = -1;sublr->_bf = 0;}else if (flag == -1){parent->_bf = 1;subl->_bf = 0;sublr->_bf = 0;}else if (flag == 0){parent->_bf = 0;subl->_bf = 0;sublr->_bf = 0;}else{assert(false);}
}

情况4:根节点_pf为2根节点的右节点_pf为-1(右左双旋)

此情况就是不同与单旋时的单一枝高,而是一枝中的另一枝高;

 

 同样的我们旋转之后更新我们的_bf;

代码实现

void RotateRL(node* parent)
{node* subr = parent->_right;node* subrl = subr->_left;int flag = subrl->_bf;RotateR(subr);//右旋左子树(树中树)RotateL(parent);//左旋右子树//更新平衡因子if (flag == 1)//插入位置为树中树的右树{parent->_bf = -1;subr->_bf = 0;subrl->_bf = 0;}else if (flag == -1){parent->_bf = 0;subr->_bf = 1;subrl->_bf = 0;}else if (flag == 0){parent->_bf = 0;subr->_bf = 0;subrl->_bf = 0;}else{assert(false);}
}

 当上面的旋转和更新_bf都完成的时候,这棵树我们插入就一定是我们的AVL树了;

为了验证我们的树是否真的成为了AVL树我们需要通过检查算法来比较每个节点的_bf是否正确

void _print(node* root)
{if (root == nullptr)return;_print(root->_left);cout << root->_data.first << " ";_print(root->_right);
}bool judgeBalance()
{return _judgeBalance(_root);
}bool _judgeBalance(node*root)
{if (root == nullptr)return true;int hl = getDeep(root->_left);//hightLeftint hr = getDeep(root->_right);//hightRightint judge = hr - hl;if (judge != root->_bf){cout << root->_data.first << "这个节点的_pf没处理好" << endl;return false;}return _judgeBalance(root->_left) && _judgeBalance(root->_right);
}void testAVLTree1()
{AVLTree<int, int>t;srand(time(0));for (int i = 0; i < 100; i++){int x = rand();t.insert(make_pair(x, x));}t.print();cout << t.judgeBalance() << endl;
}

此时我们的树就是一颗完全正确的AVL树 ;

我们只实现了AVL树的插入算法,删除算法还没有学习;

这是我的完整的AVL树代码:

C++代码/AVL树 · future/my_road - 码云 - 开源中国 (gitee.com)


https://www.xjx100.cn/news/3366209.html

相关文章

Windows搭建Lychee图片管理系统结合内网穿透实现公网访问本地图床

文章目录 1.前言2. Lychee网站搭建2.1. Lychee下载和安装2.2 Lychee网页测试2.3 cpolar的安装和注册 3.本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4.公网访问测试5.结语 1.前言 图床作为图片集中存放的服务网站&#xff0c;可以看做是云存储的一部分&#xff0c;既可…

zabbix绑定钉钉进行通知,网页端添加JavaScript,无脑式操作

文章目录 前言一、编辑zabbix告警JavaScript脚本二、代码如下:编辑消息模板,自定义markdown格式的消息。总结前言 随着人工智能的不断发展,zabbix监控这门技术也越来越重要,一下进入正题。 一、编辑zabbix告警JavaScript脚本 没有没接可以新增媒介 其中URL是你的机器人地…

基于LSB(最低有效位)的图像水印算法,Matlab实现

博主简介&#xff1a; 专注、专一于Matlab图像处理学习、交流&#xff0c;matlab图像代码代做/项目合作可以联系&#xff08;QQ:3249726188&#xff09; 个人主页&#xff1a;Matlab_ImagePro-CSDN博客 原则&#xff1a;代码均由本人编写完成&#xff0c;非中介&#xff0c;提供…

llama.cpp运行qwen0.5B

编译llama.cp 参考 下载模型 05b模型下载 转化模型 创建虚拟环境 conda create --prefixD:\miniconda3\envs\llamacpp python3.10 conda activate D:\miniconda3\envs\llamacpp安装所需要的包 cd G:\Cpp\llama.cpp-master pip install -r requirements.txt python conver…

软件赋能新型工业化,数智培育新质生产力——第二届软件创新发展大会蓄势待发

我国正在加快培育新质生产力&#xff0c;赋能新型工业化&#xff0c;软件作为新质生产力的基石与引擎&#xff0c;发展机遇空前。武汉是中国软件产业的重要一极&#xff0c;以其独特的地理优势和坚实的产业基础&#xff0c;正逐渐成为国内外瞩目的软件产业集聚发展高地。 武汉发…

从零到一:基于 K3s 快速搭建本地化 kubeflow AI 机器学习平台

背景 Kubeflow 是一种开源的 Kubernetes 原生框架&#xff0c;可用于开发、管理和运行机器学习工作负载&#xff0c;支持诸如 PyTorch、TensorFlow 等众多优秀的机器学习框架&#xff0c;本文介绍如何在 Mac 上搭建本地化的 kubeflow 机器学习平台。 注意&#xff1a;本文以 …

即将截稿 CCF-A多媒体顶会ACM MM‘24 北京时间4月9日提交摘要

会议之眼 快讯 第32届ACM MM (ACM MULTIMEDIA)即国际多媒体会议将于 2024 年 10月28 -日11月1日在澳大利亚墨尔本隆重举行&#xff01;MM是由ACM&#xff08;Association for Computing Machinery&#xff0c;计算机协会&#xff09;主办的国际性学术会议&#xff0c;是计算机…

统筹学问题

七桥问题 凡是由偶点组成的连通图&#xff0c;一定可以一笔画成。画时可以把任一偶点为起点&#xff0c;最后一定能以这个点为终点画完此图。凡是只有两个奇点的连通图(其余都为偶点)&#xff0c;一定可以一笔画成。画时必须把一个奇点为起点&#xff0c;另一个奇点为终点。其…