c++AVL树

c++AVL树

1. 前言

map/multimap、set/multiset这几个容器的共同点是：它们的底层都是按照搜索二叉树来实现的，但是搜索二叉树存在一个缺陷：如果往树中插入的元素有序或接近有序，二叉树搜索就会退化成单支树，时间复杂度会退化成O(N)。

因此map、set等关联式容器的底层结构对搜索二叉树做了平衡处理，即用平衡树（AVL树）来实现。

2. AVL树的概念

俄罗斯的数学家G.M.Adelson-Velskii 和E.M.Landis在1962年发明了一种解决二叉搜索树将退化为单支树的方法：

当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1（需要对树中的结点进行调整），即可降低树的高度，从而减少平均搜索长度。平衡因子不是必须的，只是一种控制方式，帮助便捷得控制树。

AVL树的性质：

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

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

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

3. AVL树的定义

template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data):_pLeft(nullptr),_pRight(nullptr),_pParent(nullptr),_data(data),_bf(0){}AVLTreeNode<T>* _pLeft;//左孩子AVLTreeNode<T>* _pRight;//右孩子AVLTreeNode<T>* _pParent;//该结点的父结点T_data;int _bf;       
};

3. AVL树的插入

AVL树是添加了平衡因子的搜索二叉树，它的插入可以分成两步：

1.按照搜索二叉树的方式插入新结点

2.调整平衡因子

在这里插入图片描述

在这颗AVL树中，绿色的数字表示每个结点的平衡因子(_bf)：如果左子树高度多1，那么_bf减1；如果右边的子树高度多1，那么_bf；如果左右子树高度相等，那么_bf就是0

在这里插入图片描述

插入一个结点会对平衡因子产生影响

插入结点对平衡因子的影响：

  1. 在父结点的左边插入，父结点的_bf–；在父结点的右边插入，父结点的_bf++

  2. _bf是否继续更新取决于父结点的高度是否发生变化，是否影响爷结点

  3. 更新后，如果_bf是0，说明更新前_bf是1或-1。父结点的左右平衡了，高度不变，不会影响爷结点。

  4. 更新后，如果_bf是1或-1，说明更新前_bf是0，父结点的左右不平衡了，高度变化，会影响爷结点。

  5. 更新后，如果_bf是2或-2，树就要旋转，使树的结构仍符合AVL树。

判断怎么插入的方式是通过查看平衡因子的值决定的：

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;}

4. AVL树的旋转

由于AVL树插入的规则是根据“比我小的插入左边，比我大的插入右边”，所以在某些情况下，插入会导致出现不平衡的情况。这时候就需要通过旋转操作来平衡AVL树。旋转的目的是降低树的高度。

在这里插入图片描述

某些情况插入可能会导致出现不平衡的情况

在这里插入图片描述

这种情况下，把结点旋转到左边，树就能变回平衡了

4.1 左单旋：

对于插入的结点是在右边的情况，只需要把200的结点向左旋转即可。

左旋某个结点的口诀是**“我的左变成你的右，你变成我的左”**。

在这里插入图片描述

200的左子树（b）变成了100的右子树，100变成了200的左孩子

void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if(subRL)//b不一定有subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->parent;parent->_parent = subR;if(ppnode == _root)//判断100为根结点的情况{_root=subR;subR->_parent = nullptr;}else			 //判断100还有父结点的情况{if(ppnode->left == parent)//判断100在它父结点的左边的情况{ppnode->_left = subR;}else					//判断100在它父结点的右边的情况{ppnode->_right = subR;}}parent->_bf = 0;subR->_bf = 0;
}

4.2 右单旋：

对于插入的结点是在左边的情况，只需要把100的结点向右旋转即可。

右旋某个结点的口诀是**“我的右变成你的左，你变成我的右”**。

在这里插入图片描述

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;}

4.3 双旋：

双旋也有两种情况，可以分为先左单旋再右单旋的结构和先右单旋再左单旋的结构：

4.3.1 左右双旋

如果插入的结点在中间且左高右低，这时候不能直接在这个层面上操作，还需要把b拆开，然后再对插入的左或右子树进行先左旋再右旋的操作：

在这里插入图片描述

那么此时需要分三种情况讨论

插入的结点在中间结点的左子树：

在这里插入图片描述

在这里插入图片描述

插入的结点在中间结点的右子树：

如果插入的结点在150的右边，那么其实操作和上面类似，只是最后的平衡因子不一样

在这里插入图片描述

在这里插入图片描述

中间结点就是被插入的结点本身：

如果150就是被插入的结点，操作也是一样的，先左单旋，再右单旋

在这里插入图片描述

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.2 右左双旋

如果插入的结点在中间且左低右高，需要把b拆开，然后再对插入的左或右子树进行先右旋再左旋的操作：

在这里插入图片描述

插入的结点在中间结点的左子树：

在这里插入图片描述

在这里插入图片描述

插入的结点在中间结点的右子树：

在这里插入图片描述

在这里插入图片描述

中间的结点就是插入结点本身：

在这里插入图片描述

void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << "[" << root->_bf << "]" << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);}int _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;}int Height(){return _Height(_root);}

5. AVL树的检查

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

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

2.验证其为平衡树：

每个节点子树高度差的绝对值不超过1注意节点中如果没有平衡因子）
节点的平衡因子是否计算正确

bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight) || !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout <<root->_kv.first<<"不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first <<"平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}bool IsBalance(){int height = 0;return _IsBalance(_root, height);}

6. AVL树的性能

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过1，这样可以保证查询时高效的时间复杂度，即O(log2n)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。

因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但一个结构经常修改，就不太适合。
t << root->_kv.first <<“平衡因子异常” << endl;
return false;
}

	height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;
}bool IsBalance()
{int height = 0;return _IsBalance(_root, height);
}

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

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

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

相关文章

GIS与Python机器学习：开创地质灾害风险评价新纪元

GIS与Python机器学习：开创地质灾害风险评价新纪元

地质灾害是指全球地壳自然地质演化过程中&#xff0c;由于地球内动力、外动力或者人为地质动力作用下导致的自然地质和人类的自然灾害突发事件。由于降水、地震等自然作用下&#xff0c;地质灾害在世界范围内频繁发生。我国除滑坡灾害外&#xff0c;还包括崩塌、泥石流、地面沉…
阅读更多...
【数学】第十三届蓝桥杯省赛C++ A组/研究生组 Python A组/研究生组《数的拆分》（C++）

【数学】第十三届蓝桥杯省赛C++ A组/研究生组 Python A组/研究生组《数的拆分》（C++）

【题目描述】 给定 T 个正整数 &#xff0c;分别问每个 能否表示为 的形式&#xff0c;其中 , 为正整数&#xff0c;, 为大于等于 2 的正整数。 【输入格式】 输入第一行包含一个整数 T 表示询问次数。 接下来 T 行&#xff0c;每行包含一个正整数 。 【输出格式】 对于…
阅读更多...
《无名之辈》新手攻略：抢先领取神秘礼包！

《无名之辈》新手攻略：抢先领取神秘礼包！

欢迎来到《无名之辈》&#xff01;在这个丰富多彩的冒险世界里&#xff0c;你将踏上一段充满挑战与机遇的旅程。以下是针对新手玩家的详尽攻略&#xff0c;助你快速提升实力&#xff0c;成为一名优秀的冒险者。 第一步&#xff1a;迅速起步 当你第一次踏入《无名之辈》的世界时…
阅读更多...
【wails】（10）：研究go-llama.cpp项目，但是发现不支持最新的qwen大模型，可以运行llama-2-7b-chat

【wails】（10）：研究go-llama.cpp项目，但是发现不支持最新的qwen大模型，可以运行llama-2-7b-chat

1&#xff0c;视频演示地址 2&#xff0c;项目地址go-llama.cpp 下载并进行编译&#xff1a; git clone --recurse-submodules https://github.com/go-skynet/go-llama.cpp cd go-llama.cpp make libbinding.a项目中还打了个补丁&#xff1a; 给 编译成功&#xff0c;虽然有…
阅读更多...
AXI4-Stream Interconnect IP核（1）——原理

AXI4-Stream Interconnect IP核（1）——原理

一、概述 AXI4-Stream Interconnect 是复杂片上系统&#xff08;SoC&#xff09;和现场可编程门阵列&#xff08;FPGA&#xff09;应用设计中的关键组件&#xff0c;它负责在系统内部不同模块之间路由数据流。AXI4-Stream协议是ARM引入的AMBA&#xff08;高级微控制器总线架构&…
阅读更多...
mysql--＞highgo迁移

mysql--＞highgo迁移

1、迁移工具免安装,解压双击迁移工具&#xff0c;会进入如下界面&#xff1a;migration.rar 2、新建组–>创建新的服务 3、在创建好的服务下,新建数据库连接,建立源表和目标表 4、这一步是获取源库&#xff08;Mysql数据库&#xff09;与目标库&#xff08;瀚高数据库&…
阅读更多...
【二叉树】Leetcode 226. 翻转二叉树【简单】

【二叉树】Leetcode 226. 翻转二叉树【简单】

翻转二叉树 给你一棵二叉树的根节点 root &#xff0c;翻转这棵二叉树&#xff0c;并返回其根节点。 示例 1&#xff1a; 输入&#xff1a;root [4,2,7,1,3,6,9] 输出&#xff1a;[4,7,2,9,6,3,1] 解题思路 二叉树翻转操作是指将二叉树中每个节点的左右子树进行交换。具体…
阅读更多...
eNSP ppp验证实验

eNSP ppp验证实验

1、R1和R2使用PPP链路直连&#xff0c;R2和R3把2条PPP链路捆绑为PPP MP直连 2、按照图示配置IP地址 3、R2对R1的PPP进行单向chap验证 4、R2和R3的PPP进行双向chap验证 实验步骤&#xff1a; R1配置&#xff1a; #修改名称 <Huawei>sys Enter system view, return u…
阅读更多...
Mybatis-核心配置文件 / Mybatis增删改查

Mybatis-核心配置文件 / Mybatis增删改查

1. 核心配置文件 1.1. 概述 核心配置文件是MyBatis框架中用于集中定义全局配置信息的XML文件&#xff0c;其内部包含了一系列预设标签&#xff0c;用于设置数据库连接、对象映射、类型处理等关键参数。这些标签遵循特定的排列顺序&#xff0c;尽管并非所有标签都是强制性的&a…
阅读更多...
Altair（澳汰尔） Radioss® 评估和优化动态载荷下的高度非线性问题

Altair（澳汰尔） Radioss® 评估和优化动态载荷下的高度非线性问题

Altair&#xff08;澳汰尔&#xff09; Radioss 评估和优化动态载荷下的高度非线性问题 Radioss 是一款超前的分析解决方案&#xff0c;可评估和优化动态载荷下的高度非线性问题。它广泛应用于全球各行各业&#xff0c;能有效提高复杂设计的耐撞性、安全性和可制造性。 30 多…
阅读更多...
Python实现一个简单的银行管理系统GUI应用

Python实现一个简单的银行管理系统GUI应用

介绍 在本教程中&#xff0c;我们将创建一个基本的银行管理系统GUI应用&#xff0c;用户可以通过图形界面执行各种银行操作。我们将使用Python编程语言和Tkinter库来实现此应用。 使用说明 需要安装Python解释器&#xff0c;以及PythonCharm &#x1f449; 点我去下载 效果图…
阅读更多...
23届嵌入式被裁，有什么好的就业建议？

23届嵌入式被裁，有什么好的就业建议？

最近看到了一个提问&#xff0c;原话如下&#xff1a; 本人23届毕业生&#xff0c;就业方向嵌入式软件&#xff0c;坐标深圳&#xff0c;工作3月公司裁员&#xff0c;目前接近12月开始找工作。 boss上投递简历&#xff0c;校招岗&#xff0c;比较有规模的好公司基本已读不回&am…
阅读更多...
二进制日志备份与恢复

二进制日志备份与恢复

二进制备份是 MySQL 数据库备份的一种方式&#xff0c;它通过记录数据库的所有更改操作&#xff0c;以二进制格式保存&#xff0c;实现对数据库的增量备份和恢复。binlog_format 是 MySQL 中用来指定二进制日志格式的参数&#xff0c;有三种常见的选项&#xff1a;STATEMENT、R…
阅读更多...
Codeup_1132：问题 A: 最长公共子序列

Codeup_1132：问题 A: 最长公共子序列

目录 Problem DescriptionInputOutputSample InputSample Output原题链接解题思路代码实现&#xff08;C&#xff09; Problem Description 给你一个序列X和另一个序列Z&#xff0c;当Z中的所有元素都在X中存在&#xff0c;并且在X中的下标顺序是严格递增的&#xff0c;那么就…
阅读更多...
Etcd Raft 协议（进阶篇）

Etcd Raft 协议（进阶篇）

前言 在正式开始介绍 Raft 协议之间&#xff0c;我们有必要简单介绍一下其相关概念。在分布式系统中&#xff0c;一致性是比较常见的概念&#xff0c;所谓一致性指的是集群中的多个节点在状态上达成一致。在程序和操作系统不会崩溃、硬件不会损坏、服务器不会掉电、网络绝对可靠…
阅读更多...
GDC期间LayaAir启动全球化战略

GDC期间LayaAir启动全球化战略

3 月 18 日至 3 月 22 日&#xff0c;一年一度的游戏开发者大会&#xff08;GDC&#xff09;在美国旧金山举行。在此期间&#xff0c;Layabox宣布LayaAir引擎启动全球扩张战略&#xff0c;这标志着引擎将步入快速发展的新阶段。此举旨在利用公司先进的3D引擎技术&#xff0c;将…
阅读更多...
【数据分享】1929-2023年全球站点的逐年平均露点（Shp\Excel\免费获取）

【数据分享】1929-2023年全球站点的逐年平均露点（Shp\Excel\免费获取）

气象数据是在各项研究中都经常使用的数据&#xff0c;气象指标包括气温、风速、降水、能见度等指标&#xff0c;说到气象数据&#xff0c;最详细的气象数据是具体到气象监测站点的数据&#xff01; 有关气象指标的监测站点数据&#xff0c;之前我们分享过1929-2023年全球气象站…
阅读更多...
canvas画图历史记录撤销与恢复

canvas画图历史记录撤销与恢复

提示&#xff1a;canvas画图历史记录撤销与恢复 文章目录 前言一、历史记录撤销与恢复总结 前言 一、历史记录撤销与恢复 test.html <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport…
阅读更多...
JavaScript混淆工具选择与使用指南

JavaScript混淆工具选择与使用指南

摘要 本文介绍了什么是js混淆工具&#xff0c;以及为什么需要使用js混淆工具。详细解释了js混淆工具的实现原理和作用&#xff0c;探讨了如何选择合适的js混淆工具&#xff0c;列举了几款常用的js混淆工具&#xff0c;并对它们的特点和适用场景进行了分析。最后总结了js混淆工…
阅读更多...
图书推荐|图解Java数据结构与算法：微课视频版

图书推荐|图解Java数据结构与算法：微课视频版

掌握Java数据结构与常见算法&#xff0c;精通Java语言编程 本书内容 《图解Java数据结构与算法&#xff1a;微课视频版》系统、全面地介绍数据结构的基础理论与算法设计&#xff0c;精选数据结构考研习题和各类典型例题进行讲解&#xff0c;案例和课后习题丰富&#xff0c;突出…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023