数据结构——AVL树

目录

1.什么是AVL树？

2.AVL树插入的模拟实现

①节点定义

②插入

③旋转

⑴右单旋

⑵左单旋

⑶双旋（右左旋）

⑷双旋（左右旋）

⑸完整的插入代码

3.AVL树的性能分析

1.什么是AVL树？

AVL树是一种自平衡二叉查找树，也被称为高度平衡树。它具有以下特点：

  1. 它本身是一棵二叉搜索树，即每个结点包含一个关键字和两个子结点，且满足左子树中所有关键字小于该结点的关键字，右子树中所有关键字大于该结点的关键字。
  2. AVL树带有平衡条件，即每个结点的左右子树的高度之差的绝对值（平衡因子）最多为1。为了保持这种平衡，可能需要通过一次或多次树旋转来重新平衡，这可能需要对树进行调整。

2.AVL树插入的模拟实现

①节点定义

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

因为在使用过程中可能会频繁使用到父节点，因此我们将其设计为三叉链，且在这里我们设计一个平衡因子（注：在AVL树中可能没有平衡因子，在这里引入平衡因子只是为了方便我们理解），规定一个初始节点的平衡因子为0，当它的左子树中出现新节点时平衡因子就--，右子树中出现新节点时平衡因子就++，当平衡因子==2或者==-2时，此时我们就认为当前节点往下的树已经失衡，需要对其作出调整（各式各样的旋转）

②插入

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;// 寻找要插入的位置while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}// 到此处cur已经指向了应该插入的位置，// 然后判断应该插入到parent的哪边cur = new Node(kv);if (kv.first > cur->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 插入完成后要更改平衡因子// 从父节点向上更新一直更新到平衡因子为0(已平衡)// 或者更新到平衡因子为2或-2(已失衡)// 或者更新到根节点的父节点为止while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0){break;}else if (parent->_bf == -1 || parent->_bf == 1){cur = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 此时当前节点已失衡，需要通过旋转来调整// ......(在下方结合图片具体分析)}else{assert();}}return true;
}

③旋转

根据插入位置的不同，可以具体地将它们大致分为四类。它们分别有对应的旋转策略，在这里我们使用先特殊后推广到一般的方法来解释

⑴右单旋

此情况适用于新节点插入较高左子树的左侧时，抽象图如下

当h==0时，示例图如下

当h==1时，示例图如下

接下来推广到一般，示例图如下

不难看出，右单旋操作的关键是将当前节点（即5）的右边赋给父节点（即10）的左边，然后将当前节点（即5）的右边指向父节点，再增添一些细节后可以得到如下右单旋代码

void RotateR(Node* parent)
{Node* cur = parent->_left;    // 记录当前节点Node* curright = cur->_right; // 记录当前节点的右节点// 如果当前节点的右节点为空说明是h为0的情况// 不为空时就要进行节点间的连接if (curright) {curright->_parent = parent;}parent->_left = curright;cur->_right = parent;// 此时需要确定parent是否属于子树if (parent == _root){_root = cur;cur->_parent = nullptr;}else // 此时parent以下的节点属于子树{cur->_parent = parent->_parent;// 确认parent与其父节点间的关系// 然后将cur与parent的父节点连接起来if (parent->_parent->_left == parent){parent->_parent->_left = cur;}else{parent->_parent->_right = cur;}}parent->_parent = cur;// 在进行右单旋后，当前节点与父节点的平衡因子均变为0cur->_bf = parent->_bf = 0;
}

⑵左单旋

此情况适用于新节点插入较高右子树的右侧，抽象图如下

其具体情况与右单旋类似，这里就不过多赘述，直接给出代码

void RotateL(Node* parent)
{Node* cur = parent->_right;    // 记录当前节点Node* curleft = cur->_left; // 记录当前节点的左节点// 如果当前节点的左节点为空说明是h为0的情况// 不为空时就要进行节点间的连接if (curleft){curleft->_parent = parent;}parent->_right = curleft;cur->_left = parent;// 此时需要确定parent是否属于子树if (parent == _root){_root = cur;cur->_parent = nullptr;}else // 此时parent以下的节点属于子树{cur->_parent = parent->_parent;// 确认parent与其父节点间的关系// 然后将cur与parent的父节点连接起来if (parent->_parent->_left == parent){parent->_parent->_left = cur;}else{parent->_parent->_right = cur;}}parent->_parent = cur;// 在进行左单旋后，当前节点与父节点的平衡因子均变为0cur->_bf = parent->_bf = 0;
}

⑶双旋（右左旋）

此情况适用于新节点插入较高左子树的右侧，抽象图如下

在此我们先以左边的插入情况举例

当h==0时，示例图如下

当h==1时，示例图如下

接下来推广到一般，示例图如下

接下来再让我们看看右边的情况

当h==0时，示例图如下

当h==1时，示例图如下

接下来推广到一般，示例图如下

结合上述几幅图像来看，从结果上来看，最终的结果是15节点的右边赋给了20节点的左边，15节点的左边边赋给了10节点的右边；此外，对于平衡因子来说，当h==0时，三个节点的平衡因子均被更新为0，而h!=0时，三个节点的平衡因子分为2种情况，当插入在15节点的左边时，三个节点的平衡因子分别被更新为0,0,1，当插入在15节点的右边时，三个节点的平衡因子分别被更新为0,0,-1。通过复用左单旋与右单旋的代码可以得到如下代码

void RotateRL(Node* parent)
{Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(cur);RotateL(parent);if (bf == 0) // h==0的情况{parent->_bf = 0;cur->_bf = 0;curleft->_bf = 0;}else if (bf == 1) //新节点插入到右侧的情况{parent->_bf = -1;cur->_bf = 0;curleft->_bf = 0;}else if (bf == -1)//新节点插入到左侧的情况{cur->_bf = 1;parent->_bf = 0;curleft->_bf = 0;}else // 出现其他情况时报错{assert();}
}

⑷双旋（左右旋）

此情况适用于新节点插入较高左子树的右侧，具体抽象图如下

这里与上面的右左旋大同小异，因此在这里只画出两种情况的一般示例图与h==0的示例图

当h==0时，示例图如下

当新节点插入在7的左侧时，一般示例图如下

当新节点插入在7的右侧时，一般示例图如下

根据结果我们发现它的结果与右左旋类似，因此我们只需对代码作一定的修改即可，代码如下

void RotateLR(Node* parent)
{Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(cur);RotateR(parent);if (bf == 0) // h==0的情况{parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1) //新节点插入到右侧的情况{parent->_bf = 0;cur->_bf = -1;curleft->_bf = 0;}else if (bf == -1)//新节点插入到左侧的情况{cur->_bf = 0;parent->_bf = 1;curleft->_bf = 0;}else // 出现其他情况时报错{assert();}
}

⑸完整的插入代码

bool Insert(const pair<K, V>& kv)
{if (_root == nullptr){_root = new Node(kv);return true;}Node* cur = _root;Node* parent = nullptr;// 寻找要插入的位置while (cur){if (kv.first < cur->_kv.first){parent = cur;cur = cur->_left;}else if (kv.first > cur->_kv.first){parent = cur;cur = cur->_right;}else{return false;}}// 到此处cur已经指向了应该插入的位置，// 然后判断应该插入到parent的哪边cur = new Node(kv);if (kv.first > cur->_kv.first){parent->_right = cur;}else{parent->_left = cur;}cur->_parent = parent;// 插入完成后要更改平衡因子// 从父节点向上更新一直更新到平衡因子为0(已平衡)// 或者更新到平衡因子为2或-2(已失衡)// 或者更新到根节点的父节点为止while (parent){if (cur == parent->_left)parent->_bf--;elseparent->_bf++;if (parent->_bf == 0){break;}else if (parent->_bf == -1 || parent->_bf == 1){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){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}// 插入完成后结束插入break;}else{assert();}}return true;
}

3.AVL树的性能分析

        AVL树是一种绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1。这样的平衡条件使得AVL树在查询时的性能高效且稳定。在AVL树中，任何节点的两个子树的高度差都不超过1，因此，在执行查询操作时，最坏的情况就是需要遍历log(N)层节点，其中N是树中节点的数量，因此查询效率非常高。

        然而，如果需要对AVL树进行结构修改操作，比如插入或删除节点，维持其绝对平衡性的同时会导致性能降低。在插入节点时，需要维护其平衡性，这可能会导致旋转的次数增加。在最差的情况下，旋转次数可能达到O(log(N))，这会显著影响到插入操作的性能。

        在删除节点时，可能需要执行多次旋转操作来重新平衡树。在最差的情况下，删除操作可能需要O(log(N))的时间复杂度，因为需要一直旋转到根节点。因此，如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树。然而，如果数据经常需要修改，那么AVL树可能就不是最佳选择了。

        总的来说，AVL树在查询性能上表现出色，但如果需要经常进行结构修改操作，其性能就可能会变得较差。

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

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

相关文章

NLP文本生成全解析：从传统方法到预训练完整介绍

NLP文本生成全解析：从传统方法到预训练完整介绍

目录 1. 引言1.1 文本生成的定义和作用1.2 自然语言处理技术在文本生成领域的使用 2 传统方法 - 基于统计的方法2.1.1 N-gram模型2.1.2 平滑技术 3. 传统方法 - 基于模板的生成3.1 定义与特点3.2 动态模板 4. 神经网络方法 - 长短时记忆网络(LSTM)LSTM的核心概念PyTorch中的LST…
阅读更多...
中尺度混凝土二维有限元求解——运行弯曲、运行光盘、运行比较、运行半圆形（Matlab代码实现）

中尺度混凝土二维有限元求解——运行弯曲、运行光盘、运行比较、运行半圆形（Matlab代码实现）

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…
阅读更多...
YOLOv8快速复现 训练 SCB-Dataset3-S 官网版本 ultralytics

YOLOv8快速复现 训练 SCB-Dataset3-S 官网版本 ultralytics

目录 0 相关资料SCB-Dataset3-S 数据训练yaml文件 YOLOv8 训练SCB-Dataset3-S相关参数 0 相关资料 YOLOV8环境安装教程.&#xff1a;https://www.bilibili.com/video/BV1dG4y1c7dH/ YOLOV8保姆级教学视频:https://www.bilibili.com/video/BV1qd4y1L7aX/ b站视频&#xff1a;…
阅读更多...
ceph分布式存储

ceph分布式存储

ceph特点 Ceph项目最早起源于Sage就读博士期间的工作&#xff08;最早的成果于2004年发表&#xff09;&#xff0c;并随后贡献给开源社区。在经过了数年的发展之后&#xff0c;目前已得到众多云计算厂商的支持并被广泛应用。RedHat及OpenStack都可与Ceph整合以支持虚拟机镜像的…
阅读更多...
经典指标策略回测一览

经典指标策略回测一览

编辑 经典指标策略回测一览 关键词 A股市场&#xff08;沪深京三市&#xff09; 5000股票20年内日线走势回测&#xff0c;区分除权&#xff0c;前复权&#xff0c;后复权三种模式&#xff1b;由于数据量较大&#xff0c;采用两种方式共享数据&#xff0c;一是 天启网站的数据…
阅读更多...
每天几道Java面试题：IO流（第五天）

每天几道Java面试题：IO流（第五天）

目录 第五幕 、第一场&#xff09;街边 友情提醒 背面试题很枯燥&#xff0c;加入一些戏剧场景故事人物来加深记忆。PS:点击文章目录可直接跳转到文章指定位置。 第五幕 、 第一场&#xff09;街边 【衣衫褴褛老者&#xff0c;保洁阿姨&#xff0c;面试者老王】 衣衫褴褛老…
阅读更多...
【数据结构】二叉树的·深度优先遍历（前中后序遍历）and·广度优先（层序遍历）

【数据结构】二叉树的·深度优先遍历（前中后序遍历）and·广度优先（层序遍历）

&#x1f490; &#x1f338; &#x1f337; &#x1f340; &#x1f339; &#x1f33b; &#x1f33a; &#x1f341; &#x1f343; &#x1f342; &#x1f33f; &#x1f344;&#x1f35d; &#x1f35b; &#x1f364; &#x1f4c3;个人主页 &#xff1a;阿然成长日记 …
阅读更多...
CDH 集群离线部署、大数据组件安装与扩容详细步骤(cdh-6.3.1)

CDH 集群离线部署、大数据组件安装与扩容详细步骤(cdh-6.3.1)

一、环境准备 1、服务器配置和角色规划 IP 地址主机名硬件配置操作系统安装步骤10.168.168.1cm-server8C16GCentos7新建10.168.168.2agent018C16GCentos7新建10.168.168.3agent028C16GCentos7新建10.168.168.4agent038C16GCentos7新建10.168.168.5agent048C16GCentos7扩容 2…
阅读更多...
七天学会C语言-第五天（函数）

七天学会C语言-第五天（函数）

1. 调用有参函数 有参函数是一种接受输入参数&#xff08;参数值&#xff09;并执行特定操作的函数。通过向函数传递参数&#xff0c;你可以将数据传递给函数&#xff0c;让函数处理这些数据并返回结果。 例1&#xff1a;编写一程序&#xff0c;要求用户输入4 个数字&#xf…
阅读更多...
Innodb底层原理与Mysql日志机制

Innodb底层原理与Mysql日志机制

MySQL内部组件结构 Server层 主要包括连接器、词法分析器、优化器、执行器等&#xff0c;涵盖 MySQL 的大多数核心服务功能&#xff0c;以及所有的内置函数&#xff08;如日期、时间、数学和加密函数等&#xff09;&#xff0c;所有跨存储引擎的功能都在这一层实现&#xff0c…
阅读更多...
超级详细 SQL 优化大全

超级详细 SQL 优化大全

1、MySQL的基本架构 1&#xff09;MySQL的基础架构图 左边的client可以看成是客户端&#xff0c;客户端有很多&#xff0c;像我们经常你使用的CMD黑窗口&#xff0c;像我们经常用于学习的WorkBench&#xff0c;像企业经常使用的Navicat工具&#xff0c;它们都是一个客户端。右…
阅读更多...
Python实现Redis缓存MySQL数据并支持数据同步

Python实现Redis缓存MySQL数据并支持数据同步

简介 本文讲讲如何用Redis做MySQL的读缓存&#xff0c;提升数据库访问性能。 MySQL是一种很常用的关系型数据库&#xff0c;用于持久化数据&#xff0c;并存放在磁盘上。但如果有大数据量的读写&#xff0c;靠MySQL单点就会捉襟见肘&#xff0c;尽管可以在MySQL本身做优化&am…
阅读更多...
Qt httpclient

Qt httpclient

记录一次Qt中处理https请求的操作 构造函数 get onFinished函数&#xff1a; onCompleted是对外的信号&#xff0c;这里接收的数据主要是文本类 post form post json Form 与 Json的差别是http header 的设置 文件下载处理 这里与服务器有个约定&#xff0c;文件长度不能小于…
阅读更多...
springboot整合sentinel完成限流

springboot整合sentinel完成限流

1、直入正题&#xff0c;下载sentinel的jar包 1.1 直接到Sentinel官网里的releases下即可下载最新版本&#xff0c;Sentinel官方下载地址&#xff0c;直接下载jar包即可。不过慢&#xff0c;可能下载不下来 1.2 可以去gitee去下载jar包 1.3 下载完成后&#xff0c;进行打包…
阅读更多...
68、Spring Data JPA 的 方法名关键字查询（全自动，既不需要提供sql语句，也不需要提供方法体）

68、Spring Data JPA 的 方法名关键字查询（全自动，既不需要提供sql语句，也不需要提供方法体）

1、方法名关键字查询&#xff08;全自动&#xff0c;既不需要提供sql语句&#xff0c;也不需要提供方法体&#xff09; 2、Query查询&#xff08;半自动&#xff1a;提供 SQL 或 JPQL 查询&#xff09; 3、自定义查询&#xff08;全手动&#xff09; ★ 方法名关键字查询&…
阅读更多...
简明 SQL 组合查询指南：掌握 UNION 实现数据筛选

简明 SQL 组合查询指南：掌握 UNION 实现数据筛选

在SQL中&#xff0c;组合查询是一种将多个SELECT查询结果合并的操作&#xff0c;通常使用UNION和UNION ALL两种方式。 UNION 用于合并多个查询结果集&#xff0c;同时去除重复的行&#xff0c;即只保留一份相同的数据。UNION ALL 也用于合并多个查询结果集&#xff0c;但不去除…
阅读更多...
3D模型格式转换工具HOOPS Exchange与iBase-t的Solumina集成：支持用户查询与编辑模型

3D模型格式转换工具HOOPS Exchange与iBase-t的Solumina集成：支持用户查询与编辑模型

iBase-t是一家软件公司&#xff0c;致力于简化复杂产品的构建和维护。iBase-t 于 1986 年在南加州成立&#xff0c;提供的解决方案可确保全球范围内制造、质量以及维护、修理和大修 (MRO) 运营的数字连续性。iBase-t 的 Solumina 制造运营平台是一种云原生解决方案&#xff0c;…
阅读更多...
PX4 通过 Vision 实现 Position、Altitude 和 Offboard 模式

PX4 通过 Vision 实现 Position、Altitude 和 Offboard 模式

本文通过 VINS-Fusion 的里程计信息为 PX4 提供视觉信息&#xff0c;从而达到 视觉定高和定点 的目的 主要工作为创建一个将 vins 里程计信息发布给 Mavros 的 /mavros/vision_pose/pose 话题 首先创建一个工作空间 mkdir -p ~/catkin_ws/src/vision_to_mavros/src/ cd ~/ca…
阅读更多...
贝叶斯滤波计算4d毫米波聚类目标动静属性

贝叶斯滤波计算4d毫米波聚类目标动静属性

机器人学中有些问题是二值问题&#xff0c;对于这种二值问题的概率评估问题可以用二值贝叶斯滤波器binary Bayes filter来解决的。比如机器人前方有一个门&#xff0c;机器人想判断这个门是开是关。这个二值状态是固定的&#xff0c;并不会随着测量数据变量的改变而改变。就像门…
阅读更多...
企业架构LNMP学习笔记46

企业架构LNMP学习笔记46

PHP测试连接代码&#xff1a; php代码测试使用memcached&#xff1a; 示例代码&#xff1a; <?php //实例化类 $mem new memcached(); //调用连接memcached方法 注意连接地址和端口号 $mem->addServer(192.168.17.114,11211); //存数据 var_dump($mem->set(name,l…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023