二叉搜索树进阶--AVL树详细实现过程

目录

  • AVL树概念
  • AVL树实现
    • AVL树基础结构
    • 插入
      • 插入:左旋实现
      • 插入:右旋实现
    • AVL树完整实现代码:

之前学习到的二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。
因此为了解决这一问题,发明了一种新方法:当向二叉搜索树中插入新结点后,如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。

AVL树概念

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

  • 它的左右子树都是AVL树
  • 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
    在这里插入图片描述
    如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在 O ( l o g 2 n ) O(log_2 n) O(log2n),搜索时间复杂度 O ( l o g 2 n ) O(log_2 n) O(log2n)

AVL树实现

AVL树基础结构

  • AVL树节点定义
//AVL树节点定义
template <class T>
struct AVLNode
{T _val;//平衡因子int _bf;typedef AVLNode<T> Node;Node* _parent;Node* _left;Node* _right;AVLNode(const T& val = T()):_val(val),_bf(0),_parent(nullptr),_left(nullptr),_right(nullptr){}
};
  • AVL树定义
template <class T>
class AVLTree
{
public:typedef AVLNode<T> Node;private:Node* _root = nullptr;
};

插入

AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么AVL树的插入过程可以分为两步:

  1. 按照二叉搜索树的方式插入新节点
  2. 调整节点的平衡因子
	bool insert(const T& val){if (_root == nullptr){_root = new Node(val);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_val == val)return false;else if (cur->_val > val)cur = cur->_left;elsecur = cur->_right;}cur = new Node(val);if (parent->_val > val)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//调整,从parent开始while (parent){//更新parent的平衡因子,如果在左子树插入新节点-1,如果右子树插入+1if (parent->_left == cur)--parent->_bf;else++parent->_bf;//直到父节点的平衡因子为0时停止更新(平衡因子为0说明插入新节点对祖先父节点的平衡因子不会有影响)if (parent->_bf == 0)//停止更新break;//如果平衡因子不为0,则继续向上更新else if (parent->_bf == 1 || parent == -1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){if (parent->_bf == -2 && cur->_bf == -1){//左边的左边高//右旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//右边的右边高//左旋RotateL(parent);}break;}}return true;}

插入:左旋实现

	//左旋操作结构如下://parent(2)//          subR(1)//  subRL(0)void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subL->_left;subR->_left = parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subR;subR->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subR;//更新平衡因子subR->_bf = parent->_bf = 0;}

插入:右旋实现

	//右旋操作结构如下://          parent(-2)//subL(-1)//     subLR(0)void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subL;//更新平衡因子subL->_bf = parent->_bf = 0;}

AVL树完整实现代码:

//AVL树节点定义
template <class T>
struct AVLNode
{T _val;//平衡因子int _bf;typedef AVLNode<T> Node;Node* _parent;Node* _left;Node* _right;AVLNode(const T& val = T()):_val(val),_bf(0),_parent(nullptr),_left(nullptr),_right(nullptr){}
};template <class T>
class AVLTree
{
public:typedef AVLNode<T> Node;bool insert(const T& val){if (_root == nullptr){_root = new Node(val);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if (cur->_val == val)return false;else if (cur->_val > val)cur = cur->_left;elsecur = cur->_right;}cur = new Node(val);if (parent->_val > val)parent->_left = cur;elseparent->_right = cur;cur->_parent = parent;//调整,从parent开始while (parent){//更新parent的平衡因子,如果在左子树插入新节点-1,如果右子树插入+1if (parent->_left == cur)--parent->_bf;else++parent->_bf;//直到父节点的平衡因子为0时停止更新(平衡因子为0说明插入新节点对祖先父节点的平衡因子不会有影响)if (parent->_bf == 0)//停止更新break;//如果平衡因子不为0,则继续向上更新else if (parent->_bf == 1 || parent == -1){cur = parent;parent = parent->_parent;}else if (abs(parent->_bf) == 2){if (parent->_bf == -2 && cur->_bf == -1){//左边的左边高//右旋RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1){//右边的右边高//左旋RotateL(parent);}break;}}return true;}//右旋操作结构如下://          parent(-2)//subL(-1)//     subLR(0)void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subL;//更新平衡因子subL->_bf = parent->_bf = 0;}//右旋操作结构如下://          parent(-2)//subL(-1)//     subLR(0)void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;subL->_right = parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subL;subL->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subL;elsepparent->_right = subL;subL->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subL;//更新平衡因子subL->_bf = parent->_bf = 0;}//左旋操作结构如下://parent(2)//          subR(1)//  subRL(0)void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subL->_left;subR->_left = parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;//更新cur和父亲的父亲之间的连接//判断是否为根节点if (parent == _root){_root = subR;subR->_parent = nullptr;}else{Node* pparent = parent->_parent;if (pparent->_left == parent)pparent->_left = subR;elsepparent->_right = subR;subR->_parent = pparent;}//更新父亲的父亲为curparent->_parent = subR;//更新平衡因子subR->_bf = parent->_bf = 0;}private:Node* _root = nullptr;
};

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

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

相关文章

实现Traefik工具Dashboard远程访问:搭建便捷的远程管理平台

文章目录 前言1. Docker 部署 Trfɪk2. 本地访问traefik测试3. Linux 安装cpolar4. 配置Traefik公网访问地址5. 公网远程访问Traefik6. 固定Traefik公网地址 前言 Trfɪk 是一个云原生的新型的 HTTP 反向代理、负载均衡软件&#xff0c;能轻易的部署微服务。它支持多种后端 (D…

HTML笔记-狂神

1. 初识HTML 什么是HTML&#xff1f; Hyper Text Markup Language : 超文本标记语言 超文本包括&#xff1a;文字、图片、音频、视频、动画等 目前使用的是HTML5&#xff0c;使用 W3C标准 W3C标准包括&#xff1a; 结构化标准语言&#xff08;HTML、XML&#xff09; 表现标…

大二第三周总结(算法+生活)

算法&#xff1a; 题目&#xff1a;有效的括号 这个题目也是做过很多回了。主要就是数据结构中”栈“的应用&#xff0c;先进后出。 解题思路&#xff1a; 1.创建 Map 哈希表形成键值对映射 2.进行遍历字符串 在遍历过程中 如果 遍历到的字符c 是左括号&#xff0c;则入栈 pu…

大小端字节序存储

大小端字节序存储&#xff1a;是以字节为单位讨论它在内存中的存储顺序&#xff0c;而不是更小的二进制位 例如&#xff1a; int main() {int a 0x11223344;return 0; }a在内存中的存储16进制为44 33 22 11&#xff0c;两个16进制为一个单位进行存储&#xff0c;而两个十六进…

Leetcode—260.只出现一次的数字III【中等】

2023每日刷题&#xff08;三&#xff09; Leetcode—260.只出现一次的数字III 借助lowbit的解题思想 参考的灵茶山艾府大神的题解 实现代码 /*** Note: The returned array must be malloced, assume caller calls free().*/ int* singleNumber(int* nums, int numsSize, in…

git rebase 和 git merge的区别?

一、是什么 在使用 git 进行版本管理的项目中&#xff0c;当完成一个特性的开发并将其合并到 master 分支时&#xff0c;会有两种方式&#xff1a; git mergegit rebase git rebase 与 git merge都有相同的作用&#xff0c;都是将一个分支的提交合并到另一分支上&#xff0c…

谈谈你对spring boot 3.0的理解

谈谈你对spring boot 3.0的理解 一&#xff0c;Spring Boot 3.0 的兼容性 Spring Boot 3.0 在兼容性方面做出了很大的努力&#xff0c;以支持存量项目和老项目。尽管如此&#xff0c;仍需注意以下几点&#xff1a; Java 版本要求&#xff1a;Spring Boot 3.0 要求使用 Java 1…

Web前端—Flex布局:标准流、浮动、Flex布局、综合案例(短视频首页解决方案)

版本说明 当前版本号[20231024]。 20231024初版 目录 文章目录 版本说明目录Flex布局01-标准流02-浮动基本使用产品区域布局HTML标签CSS样式 清除浮动场景搭建额外标签法单伪元素法双伪元素法overfow法 03-Flex布局Flex组成主轴对齐方式侧轴对齐方式修改主轴方向弹性伸缩比弹…

概率论_概率公式中的分号(;)、逗号(,)、竖线(|) 及其优先级

目录 1.概率公式中的分号(;)、逗号(,)、竖线(|) 2.各种概率相关的基本概念 2.1 联合概率 2.2 条件概率&#xff08;定义&#xff09; 2.3 全概率(乘法公式的加强版) 2.4 贝叶斯公式 贝叶斯定理的公式推导 1.概率公式中的分号(;)、逗号(,)、竖线(|) ; 分号代表前后是两类…

最新Tuxera NTFS2023最新版Mac读写NTFS磁盘工具 更新详情介绍

Tuxera NTFS for Mac是一款Mac系统NTFS磁盘读写软件。在系统默认状态下&#xff0c;MacOSX只能实现对NTFS的读取功能&#xff0c;Tuxera NTFS可以帮助MacOS 系统的电脑顺利实现对NTFS分区的读/写功能。Tuxera NTFS 2023完美兼容最新版本的MacOS 11 Big Sur&#xff0c;在M1芯片…

互联网Java工程师面试题·Spring篇·第二弹

目录 3、Beans 3.1、什么是 spring bean&#xff1f; 3.2、spring 提供了哪些配置方式&#xff1f; 3.3、spring 支持集中 bean scope&#xff1f; 3.4、spring bean 容器的生命周期是什么样的&#xff1f; 3.5、什么是 spring 的内部 bean&#xff1f; 3.6、什么是 spri…

【tg】4:NetworkManager :p2p、ice、消息收发

代码分布 NetworkManager 自成体系,看起来也么有啥依赖 class NetworkManager : public sigslot::has_slots<>, public std::enable_shared_from_this<NetworkManager

现在游戏出海有多少优势?

国内游戏市场趋于饱和&#xff0c;但是国外市场潜力仍然可观&#xff0c;因此很多人选择游戏出海&#xff0c;那么现在游戏出海有多少优势呢&#xff1f; 1、市场潜力 全球游戏市场潜力巨大&#xff0c;增长迅速。中国游戏公司具有强大的研发能力和创新能力&#xff0c;能够开…

[AUTOSAR][诊断管理][ECU][$19] 读取ECU的DTC故障信息

一、简介 在车载诊断中常用的诊断协议有ISO 14229等&#xff0c;在协议中主要定义了诊断请求、诊断响应的报文格式及ECU该如何处理诊断请求的应用。其中ISO 14229系列标准协议定义了用于行业内诊断通信的需求规范&#xff0c;也就是UDS。UDS主要应用于OSI七层模型的第七层——…

论文解读:Large Language Models as Analogical Reasoners

一、动机 大模型在各种类型的NLP任务上均展现出惊艳的表现。基于CoT propmt能够更好地激发大模型解决复杂推理问题的能力&#xff0c;例如解决数学解题&#xff0c;可以让模型生成reasoning path。现有的经典的CoT方法有few-shot cot、zero-shot cot等。然后现有的cot面临两个…

vue后台第二部步(布局和封装图标组件)

目录结构&#xff1b;根据需求修改、创建对应目录&#xff1b; src 应用部署目录├─api 接口├─assets 公共文件│ ├─theme.scss 主题样式…

数据库监控:关键指标和注意事项

【squids.cn】 全网zui低价RDS&#xff0c;免费的迁移工具DBMotion、数据库备份工具DBTwin、SQL开发工具等 听到模糊的说法“我们的数据库有问题”对于任何数据库管理员或管理员来说都是一场噩梦。有时是真的&#xff0c;有时不是&#xff0c;到底问题出在哪里呢&#xff1f;真…

《语音优先》智能语音技术驱动的交互界面设计与语音机器人设计(译者序)...

“言为心声,语为心境”&#xff0c;语言与对话是我们沟通与协作的重要方式。而智能语音技术是一种基于人工智能和自然语言处理技术的语音交互技术。它可以通过语音识别技术将用户的语音指令转换为文本&#xff0c;然后通过自然语言处理技术对文本进行分析和理解&#xff0c;最终…

2023Etsy入驻攻略——防封安全

2023了&#xff0c;跨境电商现在上车还来得及吗&#xff1f;当然&#xff01;Etsy是一个低成本低竞争高回报的平台&#xff0c;相较于其他电商平台&#xff0c;他的佣金非常低&#xff0c;利润率更高&#xff0c;非常合适跨境小白入局。 但由于目前Etsy关闭了中国大陆卖家的注…

FTP服务器操作手册

FTP服务器(File Transfer Protocol Server)是在互联网上提供文件存储和访问服务的计算机&#xff0c;它们依照FTP协议提供服务。FTP协议是File Transfer Protocol(文件传输协议)&#xff0c;专门用来传输文件的协议。FTP服务器是企业里经常用到的服务器&#xff0c;今天就介绍一…