【C++之AVL树旋转操作的详细图解】
C++学习笔记---022
- C++之AVL树旋转操作的详细图解
- 1、AVL树的简单介绍
- 1.1、基本概念
- 1.2、平衡因子
- 1.3、AVL树的特性
- 2、C++中pair的介绍
- 2.1、定义和初始化
- 2.2、访问元素
- 2.3、作为容器的元素
- 2.4、作为函数的返回值
- 3、AVL树节点的定义
- 4、AVL的插入规则探究
- 5、AVL树的旋转操作
- 5.1、RotateL左旋操作
- 5.2、RotateR右旋操作
- 5.3、不单纯的右边高或左边高的情况:LR双旋 或 RL双旋
- 6、AVL树的性能分析
C++之AVL树旋转操作的详细图解
前言:
前面篇章学习了C++对于map的认知和了解,接下来继续学习,C++的AVL树旋转插入操作等知识。
/知识点汇总/
1、AVL树的简单介绍
1.1、基本概念
AVL树(Adelson-Velsky和Landis发明的树)是一种自平衡的二叉搜索树(BST)。它在二叉搜索树的基础上添加了平衡的条件,以确保树的搜索、插入和删除操作都能保持较高的效率。
AVL树是一种特殊的二叉搜索树,其中每个节点的左子树和右子树的高度差(平衡因子)的绝对值不超过1。这个特性使得AVL树在插入或删除节点后,通过一系列的旋转操作可以保持其平衡性。
1.2、平衡因子
平衡因子:对于AVL树中的每个节点,其平衡因子定义为左子树的高度减去右子树的高度。平衡因子的值只能是-1、0或1。
1.3、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 log_2 n log2n)。
2、C++中pair的介绍
在C++中,std::pair 是一个模板类,用于将两个值组合成一个单一的对象。这通常用于需要同时处理两个值的情况,例如在STL(Standard Template Library)中的 std::map,其元素就是键值对(key-value pairs)。
2.1、定义和初始化
可以直接使用花括号初始化一个 std::pair 对象,或者使用 make_pair 函数来创建。
std::pair<int, std::string> p1(1, "one"); // 直接初始化
std::pair<int, std::string> p2 = {2, "two"}; // 使用花括号初始化
std::pair<int, std::string> p3 = std相关文章:
【C++之AVL树旋转操作的详细图解】
C++学习笔记---022 C++之AVL树旋转操作的详细图解1、AVL树的简单介绍1.1、基本概念1.2、平衡因子1.3、AVL树的特性2、C++中pair的介绍2.1、定义和初始化2.2、访问元素2.3、作为容器的元素2.4、作为函数的返回值3、AVL树节点的定义4、AVL的插入规则探究5、AVL树的旋转操作5.1、R…...
制作Android分区镜像
1 python生成一个sector数据 def get_oem_bootmode(): # Header size SECTOR_SIZE_IN_BYTES 512 header [0 for i in \ range(SECTOR_SIZE_IN_BYTES)] # magic # The ord() built-in function in # Python converts a character # into …...
如何代码激活service——packageKit 系统更新番外
在访问packageKit服务的过程中,服务一直访问失败,PackageKit::Daemon::global()->isRunning() 一直返回false,他是一个用于检查 PackageKit 守护进程是否正在运行的函数调用。在 Qt 和 PackageKit 的集成中,isRunning 方法通常…...
音视频常用工具
VLC 播放器简介 VLC 播放器 VLC支持多种常见音视频格式,支持多种流媒体传输协议,也可当作本地流媒体服务器使用,功能十分强大。官网下载地址: https://www.videolan.org/ VLC media player VLC 是一款自由、开源的跨平台多媒体播放器及框架&…...
周刊是聪明人筛选优质知识的聪明手段!
这是一个信息过载的时代,也是一个信息匮乏的时代。 这种矛盾的现象在 Python 编程语言上的表现非常明显。 它是常年高居编程语言排行榜的最流行语言之一,在国外发展得如火如荼,开发者、项目、文章、播客、会议活动等相关信息如海如潮。 但…...
设计模式Java实现-建造者模式
楔子 小七在2019年的时候,就想写一个关于设计模式的专栏,但是最终却半途而废了。粗略一想,如果做完一件事要100分钟,小七用3分钟热情做的事,最少也能完成10件事情了。所以这一次,一定要把他做完࿰…...
微博视频怎么下载无水印
在当今社交媒体时代,微博已经成为人们获取信息、分享生活的重要平台之一。许多人在浏览微博时常常遇到一个问题:如何下载微博视频而不留下烦人的水印呢?今天,我将分享一些神秘的方法,让你轻松解锁微博视频的无水印下载技巧。 第…...
为什么要梯度累积
文章目录 梯度累积什么是梯度累积如何理解理解梯度累积梯度累积的工作原理 梯度累积的数学原理梯度累积过程如何实现梯度累积 梯度累积的可视化 梯度累积 什么是梯度累积 随着深度学习模型变得越来越复杂,模型的训练通常需要更多的计算资源,特别是在训…...
知识图谱在提升大语言模型性能中的应用:减少幻觉与增强推理的综述
幻觉现象指的是模型在生成文本时可能会产生一些听起来合理但实际上并不准确或相关的输出,这主要是由于模型在训练数据中存在知识盲区所致。 为了解决这一问题,研究人员采取了多种策略,其中包括利用知识图谱作为外部信息源。知识图谱通过将信息…...
P8800 [蓝桥杯 2022 国 B] 卡牌
P8800 [蓝桥杯 2022 国 B] 卡牌 分析 “最多” -- 二分 1.二分区间(凑齐的卡牌套数): l:a[]min;r:(a[]b[])max 2.check(x): (1)for循环内: 判断x - a[i…...
MySQL商城数据表(80-84)
80商品规格值表 DROP TABLE IF EXISTS niumo_spec_items; CREATE TABLE niumo_spec_items (itemId int(11) NOT NULL AUTO_INCREMENT COMMENT 自增ID,shopId int(11) NOT NULL DEFAULT 0 COMMENT 店铺ID,catId int(11) NOT NULL DEFAULT 0 COMMENT 类型ID,goodsId int(11) NOT…...
使用Gitbook生成电子书
背景 《Google工程实践文档》相对原文Google’s Engineering Practices documentation ,部分内容过时了。需要更新中文版,并使用Gitbook把Markdown文件转换成对应的PDF电子书。 上一次生成PDF电子书是5年前,当时生成电子书的环境早已不在…...
设计模式之传输对象模式
在编程江湖里,有一种模式,它如同数据的“特快专递”,穿梭于系统间,保证信息的快速准确送达,它就是——传输对象模式(Data Transfer Object, DTO)。这不仅仅是数据的搬运工,更是提升系…...
Re69:读论文 LaMDA: Language Models for Dialog Applications
诸神缄默不语-个人CSDN博文目录 诸神缄默不语的论文阅读笔记和分类 论文名称:LaMDA: Language Models for Dialog Applications ArXiv网址:https://arxiv.org/abs/2201.08239 本文介绍谷歌提出的对话大模型LaMDA,主要关注对各项指标&#x…...
算法学习:二分查找
🔥 引言 在现代计算机科学与软件工程的实践中,高效数据检索是众多应用程序的核心需求之一。二分查找算法,作为解决有序序列查询问题的高效策略,凭借其对数时间复杂度的优越性能,占据着算法领域里举足轻重的地位。本篇内…...
github提交代码失败解决方案
1.打开github.push 工具 如果未安装github客户端请参考附录github 安装配置 2.设置Git的user name和email git config --global user.name "yourname" git config --global user.email "youremail" 3.生成SSH密钥 查看是否已经有了ssh密钥࿱…...
连锁收银系统总仓到门店库存调拨操作教程
1、进入系统后台,系统后台登录网址: 2、点击商品>门店调拨 3、选择调出仓库和调入门店 4、可选择添加商品逐个进行调拨,也可以批量导入需要调拨的商品 然后点击确定。 5、新增调拨后,系统会显示“待出库”状态 6、仓库已经准备…...
公网tcp转流
之前做过几次公网推流的尝试, 今天试了UDP推到公网, 再用TCP从公网拉下来, 发现不行, 就直接改用TCP转TCP了. 中间中转使用的python脚本, 感谢GPT提供技术支持: import socket import threadingdef tcp_receiver(port, forward_queue):"""接收TCP数据并将其放入…...
【Linux 基础 IO】文件系统
文章目录 1.初步理解文件2. fopen ( )的详解 1.初步理解文件 🐧① 打开文件: 本质是进程打开文件; 🐧②文件没有被打开的时候在哪里呢? ----- 在磁盘中; 🐧③进程可以打开很多个文件吗ÿ…...
Chrome浏览器安装React工具
一、如果网络能访问Google商店,直接安装官方插件即可 二、网络不能访问Google商店,使用安装包进行安装 1、下载react工具包 链接:https://pan.baidu.com/s/1qAeqxSafOiNV4CG3FVVtTQ 提取码:vgwj 2、chrome浏览器安装react工具…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
LLM基础1_语言模型如何处理文本
基于GitHub项目:https://github.com/datawhalechina/llms-from-scratch-cn 工具介绍 tiktoken:OpenAI开发的专业"分词器" torch:Facebook开发的强力计算引擎,相当于超级计算器 理解词嵌入:给词语画"…...
使用LangGraph和LangSmith构建多智能体人工智能系统
现在,通过组合几个较小的子智能体来创建一个强大的人工智能智能体正成为一种趋势。但这也带来了一些挑战,比如减少幻觉、管理对话流程、在测试期间留意智能体的工作方式、允许人工介入以及评估其性能。你需要进行大量的反复试验。 在这篇博客〔原作者&a…...
uniapp手机号一键登录保姆级教程(包含前端和后端)
目录 前置条件创建uniapp项目并关联uniClound云空间开启一键登录模块并开通一键登录服务编写云函数并上传部署获取手机号流程(第一种) 前端直接调用云函数获取手机号(第三种)后台调用云函数获取手机号 错误码常见问题 前置条件 手机安装有sim卡手机开启…...
Redis:现代应用开发的高效内存数据存储利器
一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发,其初衷是为了满足他自己的一个项目需求,即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源,Redis凭借其简单易用、…...
Chrome 浏览器前端与客户端双向通信实战
Chrome 前端(即页面 JS / Web UI)与客户端(C 后端)的交互机制,是 Chromium 架构中非常核心的一环。下面我将按常见场景,从通道、流程、技术栈几个角度做一套完整的分析,特别适合你这种在分析和改…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
