数据结构：AVL树的旋转（高度平衡树）

1、AVL树简介

 AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为1，所以它也被称为高度平衡树。增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis，他们在1962年的论文《An algorithm for the organization of information》中发表了它。

  • 它的子树都是AVL树
  • 左右子树高度插（平衡因子）的绝对值不超过1

AVL树还是一个搜索二叉树，只不过因为普通的搜索二叉树有可能变成单只树，这样就使查找效率非常的低。我们就给普通的搜索二叉树增加了一个平衡因子来使AVL左右子树的高度差的绝对值不超过1

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;                                 // balance factorAVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv);bool IsBalance();void InOrder();void Height();private:void RotateL(Node* parent);              //左旋转void RotateR(Node* parent);              //右旋转void RotateRL(Node* parent);             //右左旋转void RotateLR(Node* parent);             //左右旋转bool _IsBalance(Node* root);void _InOrder(Node* root);int _Height(Node* root);Node* _root = nullptr;
};

2、AVL树的插入

  • AVL树的插入前面和搜索二叉树的插入一模一样，只不过我们要注意平衡因子
  • 因为AVL树保持平衡是要平衡因子的绝对值不超过1，而插入会使平衡因子改变，所以我们也要要相应的旋转，使平衡因子的绝对值不超过一，我们又有几种情况
  1. 假如以pParent为根的子树不平衡，即pParent的平衡因子为2或者-2，分以下情况考虑
  2. parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋。当subR的平衡因子为-1时，执行右左双旋
  3. parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋。当subL的平衡因子为1时，执行左右双旋
  4. 旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新
template<class K, class V>
bool AVLTree<K, V>::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->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 1 || parent->_bf == -1){// 继续更新parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 0){break;}else if (parent->_bf == 2 || parent->_bf == -2){// 需要旋转处理 -- 1、让这颗子树平衡 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 if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}

2.1、左单旋

  1. subRL变成parent的右子树 
  2. parent变成subR的左子树
  3. subR变成新根
  4. 更新平衡因子
template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;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->_bf = subR->_bf = 0;
}

2.2、右单旋

60为parent，30为subL，b为subLR 

  1. subLR变成parent的左子树 
  2. parent变成subL的右子树
  3. subL变成新根
  4. 更新平衡因子
template<class K, class V>
void AVLTree<K, V>::RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}subL->_bf = parent->_bf = 0;
}

2.3、左右双旋 

先对30进行左单旋，先对90右单旋

template<class K, class V>
void AVLTree<K, V>::RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}
}

2.3、右左双旋 

先对90进行右单旋，先对30左单旋 

template<class K, class V>
void AVLTree<K, V>::RotateRL(Node* parent)
{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 = subRL->_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);}
}

 3、AVL树的性能

AVL树是带有平衡条件的二叉查找树，一般是用平衡因子差值判断是否平衡并通过旋转来实现平衡，左右子树树高不超过1，和红黑树相比，它是严格的平衡二叉树，平衡条件必须满足（所有节点的左右子树高度差不超过1）。不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的(即不会改变)，可以考虑AVL树，但一个结构经常修改，就不太适合

4、实现

#include<assert.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;                                 // balance factorAVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template<class K, class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:bool Insert(const pair<K, V>& kv);bool IsBalance();void InOrder();void Height();private:void RotateL(Node* parent);              //左旋转void RotateR(Node* parent);              //右旋转void RotateRL(Node* parent);             //右左旋转void RotateLR(Node* parent);             //左右旋转bool _IsBalance(Node* root);void _InOrder(Node* root);int _Height(Node* root);Node* _root = nullptr;
};template<class K, class V>
bool AVLTree<K, V>::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->_left = cur;}else{parent->_right = cur;}cur->_parent = parent;// 更新平衡因子while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_bf--;}if (parent->_bf == 1 || parent->_bf == -1){// 继续更新parent = parent->_parent;cur = cur->_parent;}else if (parent->_bf == 0){break;}else if (parent->_bf == 2 || parent->_bf == -2){// 需要旋转处理 -- 1、让这颗子树平衡 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 if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}template<class K, class V>
void AVLTree<K, V>::RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;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->_bf = subR->_bf = 0;
}template<class K, class V>
void AVLTree<K, V>::RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;subL->_right = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}subL->_bf = parent->_bf = 0;
}template<class K, class V>
void AVLTree<K, V>::RotateRL(Node* parent)
{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 = subRL->_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);}
}template<class K, class V>
void AVLTree<K, V>::RotateLR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = subL->_bf = subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subLR->_bf = 0;subL->_bf = 0;}else if (bf == 1){parent->_bf = 0;subLR->_bf = 0;subL->_bf = -1;}else{assert(false);}
}template<class K, class V>
void AVLTree<K, V>::InOrder()
{_InOrder(_root);cout << endl;
}template<class K, class V>
void AVLTree<K, V>::_InOrder(Node* root)
{if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << " ";_InOrder(root->_right);
}template<class K, class V>
bool AVLTree<K, V>::IsBalance()
{return _IsBalance(_root);
}template<class K, class V>
int AVLTree<K, V>::_Height(Node* root)
{if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}template<class K, class V>
void AVLTree<K, V>::Height()
{cout << _Height(_root) << endl;
}template<class K, class V>
bool AVLTree<K,V>::_IsBalance(Node* root)
{if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& _IsBalance(root->_left)&& _IsBalance(root->_right);
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/187806.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Vuex：模块化Module :VCA模式

Vuex：模块化Module :VCA模式

VCA中不支持辅助函数&#xff0c;因为辅助函数中是用this.$store&#xff0c;而VCA中没有绑定this的 由于使用单一状态树&#xff0c;应用的所有状态会集中到一个比较大的对象。当应用变得非常复杂时&#xff0c;store 对象就有可能变得相当臃肿。 这句话的意思是&#xff0c;…
阅读更多...
初识Linux：目录路径

初识Linux：目录路径

目录 提示&#xff1a;以下指令均在Xshell 7 中进行 一、基本指令&#xff1a; 二、文件 文件内容文件属性 三、ls 指令拓展 1、 ls -l &#xff1a; 2、ls -la&#xff1a; 3、ls [目录名] &#xff1a; 4、ls -ld [目录名]&#xff1a; 四、Linux中的文件和…
阅读更多...
SpringBoot 使用EasyExcel 导出Excel报表（单元格合并）

SpringBoot 使用EasyExcel 导出Excel报表（单元格合并）

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、导入依赖二、代码1. 导出简单的Excel2. 代码控制导出报表的格式 总结 前言 SpringBoot 使用Alibaba提供的EasyExcel导出Excel报表。 本文中涉及的业务逻辑…
阅读更多...
asp.net校园招聘管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

asp.net校园招聘管理系统VS开发sqlserver数据库web结构c#编程Microsoft Visual Studio

一、源码特点 asp.net 校园招聘管理系统是一套完善的web设计管理系统&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为vs2010&#xff0c;数据库为sqlserver2008&#xff0c;使用c#语言开发 应用技术&#xff1a;asp.net c#s…
阅读更多...
IP行业API助力于网络分析和数据挖掘

IP行业API助力于网络分析和数据挖掘

引言 在当今数字化时代&#xff0c;数据成为了企业、科研机构和政府决策者的重要资源&#xff0c;而IP行业API则成为了数据分析及挖掘的工具之一。IP行业API是一种能够查询IP地址所属的行业分类信息的应用程序接口&#xff0c;它能够提供在网络分析、用户行为分析及大数据挖掘…
阅读更多...
LeetCode 面试题 16.20. T9键盘

LeetCode 面试题 16.20. T9键盘

文章目录 一、题目二、C# 题解 一、题目 在老式手机上&#xff0c;用户通过数字键盘输入&#xff0c;手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列&#xff0c;实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射…
阅读更多...
农业大棚智能化改造升级与远程视频监管方案，助力智慧农业建设发展

农业大棚智能化改造升级与远程视频监管方案，助力智慧农业建设发展

一、需求分析 随着现代化技术的发展&#xff0c;农业大棚的智慧化也成为当前备受关注的智慧农业发展手段。利用先进的信息化手段来对农业大棚进行管理&#xff0c;采集和掌握作物的生长状况、作业监督、生态环境等信息数据&#xff0c;实现精准操作、精细管理&#xff0c;远程…
阅读更多...
美格智能5G RedCap模组顺利完成中国联通5G物联网OPENLAB开放实验室认证

美格智能5G RedCap模组顺利完成中国联通5G物联网OPENLAB开放实验室认证

近日&#xff0c;美格智能5G RedCap模组SRM813Q顺利通过中国联通5G物联网OPENLAB开放实验室端到端的测试验收&#xff0c;并获得OPENLAB实验室的认证证书。这标志着该模组产品各项性能均已符合RedCap商用标准&#xff0c;为5G RedCap规模商用奠定了坚实基础。 中国联通5G物联网…
阅读更多...
Kubernetes平台部署Grafana Loki Promtail系统

Kubernetes平台部署Grafana Loki Promtail系统

部署结构图&#xff1a; Loki 是主服务&#xff0c;负责存储日志和处理查询promtail 是代理&#xff0c;负责收集日志并将其发送给 lokiGrafana 用于 UI 展示 只要在应用程序服务器上安装promtail来收集日志然后发送给Loki存储&#xff0c;就可以在Grafana UI界面通过添加Lok…
阅读更多...
Python基础教程：类--继承和方法的重写

Python基础教程：类--继承和方法的重写

嗨喽&#xff0c;大家好呀~这里是爱看美女的茜茜呐 什么是继承 继承就是让类与类之间产生父子关系&#xff0c;子类可以拥有父类的静态属性和方法 继承就是可以获取到另一个类中的静态属性和普通方法&#xff08;并非所有成员&#xff09; 在python中&#xff0c;新建的类可…
阅读更多...
导轨式安装压力应变桥信号处理差分信号输入转换变送器0-10mV/0-20mV/0-±10mV/0-±20mV转0-5V/0-10V/4-20mA

导轨式安装压力应变桥信号处理差分信号输入转换变送器0-10mV/0-20mV/0-±10mV/0-±20mV转0-5V/0-10V/4-20mA

主要特性 DIN11 IPO 压力应变桥信号处理系列隔离放大器是一种将差分输入信号隔离放大、转换成按比例输出的直流信号导轨安装变送模块。产品广泛应用在电力、远程监控、仪器仪表、医疗设备、工业自控等行业。此系列模块内部嵌入了一个高效微功率的电源&#xff0c;向输入端和输…
阅读更多...
Visual Studio2022安装教程【图文详解】(大一小白)编译软件

Visual Studio2022安装教程【图文详解】(大一小白)编译软件

工欲善其事&#xff0c;必先利其器。想要学好编程&#xff0c;首先要把手中的工具利用好&#xff0c;今天小编教一下大家如何下载安装并使用史上最强大的编译器--Visual Studio&#x1f357; 一.Visual Studio下载及安装 https://visualstudio.microsoft.com/ 打开文件 点击.ex…
阅读更多...
基于ubuntu 22, jdk 8x64搭建图数据库环境 hugegraph--google镜像chatgpt

基于ubuntu 22, jdk 8x64搭建图数据库环境 hugegraph--google镜像chatgpt

基于ubuntu 22, jdk 8x64搭建图数据库环境 hugegraph download 环境 uname -a #Linux whiltez 5.15.0-46-generic #49-Ubuntu SMP Thu Aug 4 18:03:25 UTC 2022 x86_64 x86_64 x86_64 GNU/Linuxwhich javac #/adoptopen-jdk8u332-b09/bin/javac which java #/adoptopen-jdk8u33…
阅读更多...
对于线程的收尾

对于线程的收尾

一)对于synchronized的锁策略: synchronzed是一个自适应的锁&#xff0c;应该根据具体情况来决定选取那种锁策略&#xff1b; 1)synchronized既是一个乐观锁又是一个悲观锁&#xff0c;一开始是一个乐观锁&#xff0c;但是如果发现锁冲突的概率比较高&#xff0c;就会自动转化成…
阅读更多...
主题模型LDA教程：一致性得分coherence score方法对比（umass、c_v、uci）

主题模型LDA教程：一致性得分coherence score方法对比（umass、c_v、uci）

文章目录 主题建模潜在迪利克雷分配&#xff08;LDA&#xff09;一致性得分 coherence score1. CV 一致性得分2. UMass 一致性得分3. UCI 一致性得分4. Word2vec 一致性得分5. 选择最佳一致性得分 主题建模 主题建模是一种机器学习和自然语言处理技术&#xff0c;用于确定文档…
阅读更多...
Linux驱动开发——USB设备驱动

Linux驱动开发——USB设备驱动

目录 一、 USB 协议简介 二、 Linux USB 驱动 三、 USB 设备驱动实例 一、 USB 协议简介 USB(Universal Serial Bus&#xff0c;通用串行总线)正如它的名字一样&#xff0c;是用来连接PC外设的一种通用串行总线&#xff0c;即插即用和易扩展是它最大的特点。所谓即插即用&am…
阅读更多...
Edge浏览器新建标签页如何更改为指定网址

Edge浏览器新建标签页如何更改为指定网址

Edge浏览器新建标签页如何更改为指定网址&#xff1f; 启动时新建标签页 不是说启动时&#xff0c;而是加号新建标签页时候 启动时 新建标签页 New Tab Changer 可以了 如果没有需要应用商店下载 参考文章
阅读更多...
Clickhouse 学习笔记（6）—— ClickHouse 分片集群

Clickhouse 学习笔记（6）—— ClickHouse 分片集群

前置知识&#xff1a; Clickhouse学习笔记&#xff08;5&#xff09;—— ClickHouse 副本-CSDN博客 与副本对比&#xff1a; 副本虽然能够提高数据的可用性&#xff0c;降低丢失风险&#xff0c;但是每台服务器实际上必须容纳全量数据&#xff0c;对数据的横向扩容没有解决 …
阅读更多...
工厂设备报修的流程是怎样的？维修流程要如何优化？

工厂设备报修的流程是怎样的？维修流程要如何优化？

在当今高度自动化的生产环境中&#xff0c;工厂设备的正常运行无疑对于企业的生产效率和经济效益具有至关重要的影响。然而&#xff0c;设备故障是生产过程中不可避免的现象。当设备发生故障时&#xff0c;如何快速、有效地进行报修、维修&#xff0c;以恢复设备的正常运转&…
阅读更多...
企业年会/年终活动如何邀请媒体记者报道?

企业年会/年终活动如何邀请媒体记者报道?

​媒体邀约是企业或组织进行宣传的重要手段之一。通过邀请媒体参加活动&#xff0c;可以增加活动的曝光度和知名度&#xff0c;吸引更多的关注和参与。同时&#xff0c;媒体报道还可以提高企业或组织的权威性和可信度&#xff0c;从而让公众更容易接受其传达的信息。 企业年会或…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023