当前位置: 首页 > news >正文

平衡二叉树(AVL树)

平衡二叉树是啥我就不多说了,本篇博客只讲原理与方法。

首先引入平衡因子的概念。平衡因子(Balance Factor),以下简称bf。

bf = 右子树深度 - 左子树深度。平衡结点的平衡因子可为:-1,0,1。除此之外的结点都需要调整。

如下图:

AVL树的基础创建

创建AVL树的基本架构与二叉搜索树的创建基本一样,不同是为了方便后续的旋转与平衡因子的改变,多引入bf与parent记录结点的平衡因子与该结点的父节点,形成三叉链。

AVL树的旋转

右单旋

新节点插入较高左子树的左侧

以上过程可以简单的看作是30的右子树变成60的左子树,60变成30的右子树。其中h高度可以取值为0。

这是两种不同的情况。不同点在于30的右子树为NULL,此时并不需要更新其子树的parent结点的指向。每个结点的bf统统归零。

左单旋

 新节点插入较高右子树的右侧

以上过程可简单看成,60的左变成30的右,30变成60的左。其中60的左可以为空。

和右单旋同理。

先左单旋再右单旋(LR)

新节点插入较高左子树的右侧

路径可以形象的看作“<”先左后右(LR)

将双旋变成单旋后再旋转,即:先对30进行左单旋,然后再对90进行右单旋,旋转完成后再
考虑平衡因子的更新。

平衡因子的更新

情况一:如上图在b处插入后60结点的bf=-1,最终平衡树的平衡因子为60:0,30:0,90:1。

情况二:

在c处插入后60结点的bf=1,最终平衡因子为30:-1,60:0,90:0。

情况三:

插入60结点,60结点bf=1,最终平衡因子为30:0,60:0,90:0。

先右单旋再左单旋(RL)

新节点插入较高右子树的左侧

路径可以形象看作“>’,先右后左(RL)。

将双旋变成单旋后再旋转,即:先对90进行左单旋,然后再对30进行右单旋,旋转完成后再
考虑平衡因子的更新。

平衡因子讨论和LR类似。

代码

#pragma once
#include <iostream>
#include <stdlib.h>
using namespace std;template <class K,class V>
struct AVLtreeNode {AVLtreeNode<K, V>* _right;AVLtreeNode<K, V>* _left;AVLtreeNode<K, V>* _parent;AVLtreeNode(const pair<K,V>& kv):_right(nullptr),_left(nullptr),_parent(nullptr),_kv(kv),_bf(0){}int _bf; //平衡因子pair<K, V> _kv;
};
template <class K,class V>
class AVLtree {typedef AVLtreeNode<K,V> Node;
public: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->_left;}else if (cur->_kv.first < kv.first){parent = cur;cur = cur->_right;}else{return false;}}cur = new Node(kv);if (parent->_kv.first > kv.first){parent->_left = cur;cur->_parent = parent;}else{parent->_right = cur;cur->_parent = parent;}while (parent){if (cur == parent->_right){parent->_bf++;}else{parent->_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){//parnet所在的子树出现不平衡,需要旋转if (parent->_bf == 2){if (cur->_bf == 1){RotateL(parent);}else if (cur->_bf == -1){RotateRL(parent);}}else if (parent->_bf == -2){if (cur->_bf == -1){RotateR(parent);}else if(cur->_bf==1){RotateLR(parent);}}break;}}return true;}void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL) subRL->_parent = parent;subR->_left = parent;Node* node = parent->_parent;parent->_parent = subR;//1、原来parent是这棵树的根,现在subR是根//2、parent不是根,parent还有他自己的_parent,现在让_parent指向subRif (_root == parent){_root = subR;subR->_parent = nullptr;}else{if (node->_left == parent){node->_left = subR;}else{node->_right = subR;}subR->_parent = node;}parent->_bf = subR->_bf = 0;}void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subL->_right;Node* node = parent->_parent;subL->_right = parent;if (subLR) subLR->_parent = parent;parent->_parent = subL;if (_root == parent){_root = subL;subL->_parent = nullptr;}else{if (parent == node->_left){node->_left = subL;}else{node->_right = subL;}subL->_parent = node;}subL->_bf = parent->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else if (bf == 1){subR->_bf = 0;parent->_bf = -1;subRL->_bf = 0;}else if (bf == 0){subR->_bf = 0;parent->_bf = 0;subRL->_bf = 0;}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}}void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first <<" : " << root->_kv.second << endl;_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}int Height(Node* root){if (root == nullptr) return 0;int left = Height(root->_left);int right = Height(root->_right);return left > right ? left + 1 : right + 1;}bool _IsBalance(Node*root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return abs(leftHeight - rightHeight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);}bool IsBalance(){return _IsBalance(_root);}private:Node* _root=nullptr;
};void TestAVLTree()
{int a[] = { 16,3,7,11,9,26,18,14,15 };AVLtree<int, int> t;for (auto e : a){t.Insert(make_pair(e, e));}t.InOrder();cout << t.IsBalance() << endl;
}

相关文章:

平衡二叉树(AVL树)

平衡二叉树是啥我就不多说了&#xff0c;本篇博客只讲原理与方法。 首先引入平衡因子的概念。平衡因子&#xff08;Balance Factor&#xff09;&#xff0c;以下简称bf。 bf 右子树深度 - 左子树深度。平衡结点的平衡因子可为&#xff1a;-1&#xff0c;0&#xff0c;1。除此…...

SpringBoot(一)--搭建架构5种方法

目录 一、⭐Idea从spring官网下载打开 2021版本idea 1.打开创建项目 2.修改pom.xml文件里的版本号 2017版本idea 二、从spring官网下载再用idea打开 三、Idea从阿里云的官网下载打开 ​编辑 四、Maven项目改造成springboot项目 五、从阿里云官网下载再用idea打开 Spri…...

RabbitMQ使用延迟消息

RabbitMQ使用延迟消息 1.什么情况下使用延迟消息 延迟消息适用于需要在一段时间后执行某些操作的场景&#xff0c;常见的有以下几类&#xff1a; 1.1. 订单超时取消&#xff08;未支付自动取消&#xff09; 场景&#xff1a; 用户下单后&#xff0c;如果 30 分钟内未付款&a…...

MyBatis-Plus 分页查询接口返回值问题剖析

在使用 MyBatis-Plus 进行分页查询时,很多开发者会遇到一个常见的问题:当分页查询接口返回值定义为 Page<T> 时,执行查询会抛出异常;而将返回值修改为 IPage<T> 时,分页查询却能正常工作。本文将从 MyBatis-Plus 的分页机制入手,详细分析这一问题的根源,并提…...

DeepLabv3+改进7:在主干网络中添加SegNext_Attention|助力涨点

🔥【DeepLabv3+改进专栏!探索语义分割新高度】 🌟 你是否在为图像分割的精度与效率发愁? 📢 本专栏重磅推出: ✅ 独家改进策略:融合注意力机制、轻量化设计与多尺度优化 ✅ 即插即用模块:ASPP+升级、解码器 PS:订阅专栏提供完整代码 论文简介 近期有关移动网络设计…...

c语言笔记 内存管理之栈内存

物理内存和虚拟内存 在c语言的程序需要内存资源&#xff0c;用来存放变量&#xff0c;常量&#xff0c;函数代码等&#xff0c;不同的内容存放在不同的内存区域&#xff0c;不同的内存区域有着不同的特征。 c语言的每一个进程都有着一片结构相同的 虚拟内存&#xff0c;虚拟内…...

分布式事务的原理

文章目录 基于 XA 协议的两阶段提交&#xff08;2PC&#xff09;三阶段提交&#xff08;3PC&#xff09;TCC&#xff08;Try-Confirm-Cancel&#xff09;Saga 模式消息队列&#xff08;可靠消息最终一致性&#xff09; 分布式事务是指在分布式系统中&#xff0c;涉及多个节点或…...

鸿基智启:东土科技为具身智能时代构建确定性底座

人类文明的每一次跨越都伴随着工具的革新。从蒸汽机的齿轮到计算机的代码&#xff0c;生产力的进化始终与技术的“具身化”紧密相连。当大语言模型掀起认知革命&#xff0c;具身智能正以“物理实体自主决策”的双重属性重新定义工业、医疗、服务等领域的运行逻辑。在这场革命中…...

SQL29 计算用户的平均次日留存率

SQL29 计算用户的平均次日留存率 计算用户的平均次日留存率_牛客题霸_牛客网 题目&#xff1a;现在运营想要查看用户在某天刷题后第二天还会再来刷题的留存率。 示例&#xff1a;question_practice_detail -- 输入&#xff1a; DROP TABLE IF EXISTS question_practice_detai…...

MWC 2025 | 移远通信推出AI智能无人零售解决方案,以“动态视觉+边缘计算”引领智能零售新潮流

在无人零售市场蓬勃发展的浪潮中&#xff0c;自动售货机正经历着从传统机械式操作向AI视觉技术的重大跨越。 移远通信作为全球领先的物联网整体解决方案供应商&#xff0c;精准把握行业趋势&#xff0c;在2025世界移动通信大会&#xff08;MWC&#xff09;上宣布推出全新AI智能…...

sparkTTS window 安装

下载 Spark-TTS Go to Spark-TTS GitHubClick "Code" > "Download ZIP", then extract it. 2. 建立 Conda 环境 conda create -n sparktts python3.12 -y conda activate sparktts 3. Install Dependencies pip install -r requirements.txt In…...

数据库原理6

1.数据是信息的载体 2.数据库应用程序人员的主要职责&#xff1a;编写应用系统的程序模块 3.关系规范化理论主要属于数据库理论的研究范畴 4.数据库主要有检索和修改&#xff08;包括插入&#xff0c;删除&#xff0c;更新&#xff09;两大操作 5.概念模型又称为语义模型。…...

接口自动化入门 —— Http的请求头,请求体,响应码解析!

在接口自动化测试中&#xff0c;HTTP请求头、请求体和响应码是核心组成部分。理解它们的作用、格式和解析方法对于进行有效的接口测试至关重要。以下是详细解析&#xff1a; 1. HTTP 请求头&#xff08;Request Header&#xff09; 1.1 作用 请求头是客户端向服务器发送的附加…...

tcc编译器教程6 进一步学习编译gmake源代码

本文以编译gmake为例讲解如何使用tcc进行复杂一点的c代码的编译 1 简介 前面主要讲解了如何编译lua解释器,lua解释器的编译很简单也很容易理解.当然大部分c语言程序编译没那么简单,下面对前面的gmake程序进行编译. 2 gmake源码结构 首先打开之前tcc-busybox-for-win32\gmak…...

公司共享网盘怎么建立

公司共享网盘的建立&#xff0c;关键在于明确使用需求、选择合适的网盘服务、搭建统一的文件管理规范、做好权限分级与安全防护。尤其要强调选择合适的网盘服务这一点&#xff0c;如果企业规模较大&#xff0c;且对协同办公的需求强烈&#xff0c;就需要考虑支持多人实时协作、…...

【高分论文密码】AI大模型和R语言的全类型科研图形绘制,从画图、标注、改图、美化、组合、排序分解科研绘图每个步骤

在科研成果竞争日益激烈的当下&#xff0c;「一图胜千言」已成为高水平SCI期刊的硬性门槛——数据显示很多情况的拒稿与图表质量直接相关。科研人员普遍面临的工具效率低、设计规范缺失、多维数据呈现难等痛点&#xff0c;因此科研绘图已成为成果撰写中的至关重要的一个环节&am…...

深入理解Java中的static关键字及其内存原理

static是Java中实现类级共享资源的核心修饰符&#xff0c;它突破了对象实例化的限制&#xff0c;使得变量和方法能够直接与类本身绑定。这种特性让static成为构建工具类、全局配置等场景的利器&#xff0c;但同时也带来独特的内存管理机制需要开发者关注。 static修饰成员变量…...

linux 系统 之centos安装 docker

对于 CentOS 安装 Docker 的前置条件 首先&#xff0c;需要安装一些必要的软件包&#xff0c; 对于 CentOS 7&#xff0c;可以使用以下命令&#xff1a; sudo yum install -y yum-utils device-mapper-persistent-data lvm2添加 Docker 仓库 设置 Docker 的官方仓库。对于 …...

Python语法核心架构与核心知识点:从理论到实践

一、Python的核心设计哲学 Python以“简洁优雅”为核心理念&#xff0c;遵循以下原则&#xff1a; # Zen of Python&#xff08;输入 import this 可查看&#xff09; >>> import this The Zen of Python, by Tim Peters ... Simple is better than complex. Readab…...

FreeRTOS(5)内核控制函数及其他函数

FreeRTOS 提供了一些用于控制内核的 API 函数&#xff0c;这些 API 函数主要包含了进出临界区、开关中断、启停任务调度器等一系列用于控制内核的 API 函数。本章就来学习 FreeRTOS 的内 核控制函数。 内核控制函数 1. 函数 taskYIELD() 此函数用于请求切换任务&#xff0c; …...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

oracle与MySQL数据库之间数据同步的技术要点

Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异&#xff0c;它们的数据同步要求既要保持数据的准确性和一致性&#xff0c;又要处理好性能问题。以下是一些主要的技术要点&#xff1a; 数据结构差异 数据类型差异&#xff…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

Linux --进程控制

本文从以下五个方面来初步认识进程控制&#xff1a; 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程&#xff0c;创建出来的进程就是子进程&#xff0c;原来的进程为父进程。…...

中医有效性探讨

文章目录 西医是如何发展到以生物化学为药理基础的现代医学&#xff1f;传统医学奠基期&#xff08;远古 - 17 世纪&#xff09;近代医学转型期&#xff08;17 世纪 - 19 世纪末&#xff09;​现代医学成熟期&#xff08;20世纪至今&#xff09; 中医的源远流长和一脉相承远古至…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用

中达瑞和自2005年成立以来&#xff0c;一直在光谱成像领域深度钻研和发展&#xff0c;始终致力于研发高性能、高可靠性的光谱成像相机&#xff0c;为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...

比特币:固若金汤的数字堡垒与它的四道防线

第一道防线&#xff1a;机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”&#xff08;Hashing&#xff09;就是一种军事级的加密术&#xff08;SHA-256&#xff09;&#xff0c;能将信函内容&#xff08;交易细节&#xf…...

第22节 Node.js JXcore 打包

Node.js是一个开放源代码、跨平台的、用于服务器端和网络应用的运行环境。 JXcore是一个支持多线程的 Node.js 发行版本&#xff0c;基本不需要对你现有的代码做任何改动就可以直接线程安全地以多线程运行。 本文主要介绍JXcore的打包功能。 JXcore 安装 下载JXcore安装包&a…...