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

C++实现AVL树

news 来源：原创 2025/8/23 1:47:06

一 AVL树的概念

上上节我们学习了二叉搜索树，他的理想查找的时间复杂度是o(log n)，但是如果是下面这种情况，那么它的时间复杂度就会变成o(n).

这种情况就是出现一边高的那种，它的个数和它的高度相差不大。

那么这样就会把二叉搜索树的优势给丢了，效率也是大打折扣，所以后面发明了一个用来平衡左右高度的树，AVL树。

AVL树得名于它的发明者G. M. Adelson-Velsky和E. M. Landis是两个前苏联的科学家，他们在1962年的论⽂《An algorithm for the organization of information》中发表了它。

AVL树实现这⾥我们引⼊⼀个平衡因⼦(balance factor)的概念，每个结点都有⼀个平衡因⼦，任何结点的平衡因⼦等于右⼦树的⾼度减去左⼦树的⾼度，也就是说任何结点的平衡因⼦等于0/1/-1，AVL树并不是必须要平衡因⼦，但是有了平衡因⼦可以更⽅便我们去进⾏观察和控制树是否平衡，就像⼀个⻛向标⼀样。

思考⼀下为什么AVL树是⾼度平衡搜索⼆叉树，要求⾼度差不超过1，⽽不是⾼度差是0呢？0不是更好的平衡吗？画画图分析我们发现，不是不想这样设计，⽽是有些情况是做不到⾼度差是0的。⽐如⼀棵树是2个结点，4个结点等情况下，⾼度差最好就是1，⽆法做到⾼度差是0 。

AVL树整体结点数量和分布和完全⼆叉树类似，⾼度可以控制在，那么增删查改的效率也可以控制在O（logN），相比二叉搜索树有了显著的提升。

二 AVL树的实现

2.1 AVL树的结构

使用类模板来构建一个K，V模型，首先是使用标准库里面的pair结构体，然后后面定义了3个结构体指针，分别是左孩子节点，右孩子结点，父亲节点，父亲节点的主要作用是在后面进行旋转操作的时候能够分清楚各个节点之间的关系，还有一个平衡因子，这个就是后面我们用来控制平衡的关键。

2.2 AVL树的插入

2.2.1 AVL树插⼊⼀个值的⼤概过程

1. 插⼊⼀个值按⼆叉搜索树规则进⾏插⼊。

2. 新增结点以后，只会影响祖先结点的⾼度，也就是可能会影响部分祖先结点的平衡因⼦，所以更新从新增结点->根结点路径上的平衡因⼦，实际中最坏情况下要更新到根，有些情况更新到中间就可以停⽌了，具体情况我们下⾯再详细分析。

3. 更新平衡因⼦过程中没有出现问题，则插⼊结束.

4. 更新平衡因⼦过程中出现不平衡，对不平衡⼦树旋转，旋转后本质调平衡的同时，本质降低了⼦树的⾼度，不会再影响上⼀层，所以插⼊结束。

2.2.2 平衡因⼦更新
更新原则：

1.平衡因⼦ = 右⼦树⾼度-左⼦树⾼度

2.只有⼦树⾼度变化才会影响当前结点平衡因⼦。

3.插⼊结点，会增加⾼度，所以新增结点在parent的右⼦树，parent的平衡因⼦++，新增结点在parent的左⼦树，parent平衡因⼦--

4.parent所在⼦树的⾼度是否变化决定了是否会继续往上更新

更新停⽌条件：

1.更新后parent的平衡因⼦等于0，更新中parent的平衡因⼦变化为-1->0 或者 1->0，说明更新前 parent⼦树⼀边⾼⼀边低，新增的结点插⼊在低的那边，插⼊后parent所在的⼦树⾼度不变，不会影响parent的⽗亲结点的平衡因⼦，更新结束。

2.更新后parent的平衡因⼦等于1 或 -1，更新前更新中parent的平衡因⼦变化为0->1 或者 0->-1，说明更新前parent⼦树两边⼀样⾼，新增的插⼊结点后，parent所在的⼦树⼀边⾼⼀边低，parent所在的⼦树符合平衡要求，但是⾼度增加了1，会影响parent的⽗亲结点的平衡因⼦，所以要继续向上更新。

3.更新后parent的平衡因⼦等于2 或 -2，更新前更新中parent的平衡因⼦变化为1->2 或者 -1->-2，说明更新前parent⼦树⼀边⾼⼀边低，新增的插⼊结点在⾼的那边，parent所在的⼦树⾼的那边更⾼了，破坏了平衡，parent所在的⼦树不符合平衡要求，需要旋转处理，旋转的⽬标有两个：

(1)、把parent⼦树旋转平衡。

(2)、降低parent⼦树的⾼度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插⼊结束。

4.不断更新，更新到根，跟的平衡因⼦是1或-1也停⽌了。

2.2.3 插入节点以及更新平衡因子的代码实现
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 = parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2){// 旋转if (parent->_bf == -2 && cur->_bf == -1) // 右单旋{RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == 1) // 左单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋{RotateLR(parent);}else if (parent->_bf == 2 && cur->_bf == -1) // 右左双旋{RotateRL(parent);}else{assert(false);}break;}else{assert(false);}}return true;
}
这里的原理就往前看更新的停止条件就好理解了。（懒得再写一遍了）

说一下RotateL，RotateR，RotateLR，RotateRL：

右单旋（RotateR）：

在a里面插入了一个树导致5的左右子树不平衡需要旋转，那么5的右子树作为一个整体subLR，5作为subL，10是parent，把5的right接到10节点，10的left接到5的right，这样就完成旋转了，因为5的右孩子依旧是比10小的，所以把5的右孩子给成10的左孩子是没有问题的，还有后面记得把5的parent变成曾经10的parent，10的parent改成5，曾经是5的右孩子那一片的parent改成10，这样就完成了旋转了。
void RotateR(Node* parent)
{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;subL->_right = parent;if (subLR)subLR->_parent = parent;Node* parentParent = parent->_parent;parent->_parent = subL;//if (parentParent == nullptr)if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}subL->_bf = parent->_bf = 0;
}
左单旋（RotateL）：

和右旋类似就不多说了。
void RotateL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;Node* parentParent = parent->_parent;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parent == parentParent->_left){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}parent->_bf = subR->_bf = 0;
}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);}
}
左右双旋（RotateLR）：

举个简单的例子：

左边⾼时，如果插⼊位置不是在a⼦树，⽽是插⼊在b⼦树，b⼦树⾼度从h变成h+1，引发旋转，右单旋⽆法解决问题，右单旋后，我们的树依旧不平衡。右单旋解决的纯粹的左边⾼，但是插⼊在b⼦树中，10为跟的⼦树不再是单纯的左边⾼，对于10是左边⾼，但是对于5是右边⾼，需要⽤两次旋转才能解决，以5为旋转点进⾏⼀个左单旋，以10为旋转点进⾏⼀个右单旋，这棵树就平衡了。

代码实现：
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);}
}
右左双旋（RotateRL）：

这个和左右双旋的实现思路还是差不多的，只是变换了位置来旋转，也就不多介绍了
void RotateRL(Node* parent)
{Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}
}
2.3 AVL树的查找

按照二叉搜索树的逻辑来实现就可以了，查找效率是O（logN）。
bool Find(const K& key)
{Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return true;}}return false;
}
2.4 AVL树的平衡检测

AVL树是在二叉搜索树的基础上添加了平衡因子，因此想要检测其平衡性，可以分成两步：

1 检测是否在中序遍历下是有序的，如果是有序的，那说明是二叉搜索树。

2 检测平衡因子，每个节点字数高度的绝对值都不应该超过1，由此来计算平衡因子是否正确
bool _IsBalanceTree(Node* root)
{// 空树也是AVL树if (nullptr == root)return true;// 计算pRoot结点的平衡因子：即pRoot左右子树的高度差int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);int diff = rightHeight - leftHeight;// 如果计算出的平衡因子与pRoot的平衡因子不相等，或者// pRoot平衡因子的绝对值超过1，则一定不是AVL树if (abs(diff) >= 2){cout << root->_kv.first << " 高度差异常" << endl;return false;}if (root->_bf != diff){cout << root->_kv.first << "平衡因子异常" << endl;return false;}// pRoot的左和右如果都是AVL树，则该树一定是AVL树return _IsBalanceTree(root->_left) && _IsBalanceTree(root->_right);
}
这个代码的作用就先是计算root左右子树的高度差，然后用diff来存这个高度差，如果绝对值大于等于2，那么平衡因子就是有问题的，然后用递归的思想来一个个字树的检测。

2.5 AVL树的删除

因为AVL树也是二叉搜索树，可按照二叉搜索树的方式将节点删除，然后再更新平衡因子，只不过与删除不同的是，删除节点后的平衡因子更新，最差情况下一直要调整到根节点的位置。具体实现可参考《算法导论》或《数据结构-用面向对象方法与C++描述》殷人昆版。

C++实现AVL树

一 AVL树的概念上上节我们学习了二叉搜索树，他的理想查找的时间复杂度是o(log n)，但是如果是下面这种情况，那么它的时间复杂度就会变成o(n). 这种情况就是出现一边高的那种，它的个数和它的高度相差不大。那么这样就会把二叉搜索…...

编程日记 2025/8/23 1:47:06

Linux系统安全及应用

目录一.账号安全措施 1.1系统账号清理 1.1.1将非登录用户的shell设为无法登录 1.1.2删除无用用户 userdel 1.1.3锁定账号文件 1.1.4锁定长期不使用的账号 1.2密码安全控制 1.2.1 对新建用户 1.2.2对已有用户 1.3命令历史限制 1.3.1临时清除历史命令 1.3.2限制命令…...

编程日记 2025/8/23 1:45:57

JAVA反序列化深入学习（十三）：Spring2

让我们回到Spring Spring2 在 Spring1 的触发链上有所变换： 替换了 spring-beans 的 ObjectFactoryDelegatingInvocationHandler使用了 spring-aop 的 JdkDynamicAopProxy ，并完成了后续触发 TemplatesImpl 的流程简而言之，换了一个chain&am…...

编程日记 2025/8/22 19:43:36

迭代器运算详解（四十二）

1. 迭代器的随机访问运算对于 vector 和 string 这样的容器，它们的迭代器支持以下随机访问运算符： 运算符说明iter n返回一个新的迭代器，该迭代器比原来的迭代器 iter 向前移动了 n 个位置（即指向后面的第 n 个元素&#xff0…...

编程日记 2025/8/23 1:45:16

Linux中Squid服务常用操作

在 Linux 中 Squid 服务常用操作介绍 1. Squid 基础操作启动 Squid # 前台启动（调试用） squid -N -d 1# 后台启动（-s 表示将日志输出到 syslog） squid -s停止 Squid # 安全停止（需配置 pid_file） squid…...

编程日记 2025/8/20 13:07:10

Linux操作系统--进程的概念

目录 1.了解进程前的前景知识冯诺依曼体系结构操作系统(OS) 2.进程 2.1进程的概念 2.2描述进程-PCB 2.2.1task_struct 2.3查看进程 2.4通过系统调用获取进程的标识符 2.5认识fork()--创建进程该专栏会持续更新更新时间一周一更。下周更新内容进程状态 1.了解进程前…...

编程日记 2025/8/20 2:27:14

HTML零基础入门笔记：狂神版

前言本笔记是学习狂神的java教程，建议配合视频，学习体验更佳。【狂神说Java】HTML5完整教学通俗易懂_哔哩哔哩_bilibili 第1-2章：Java零基础入门笔记：(1-2)入门（简介、基础知识）-CSDN博客第3章&…...

编程日记 2025/8/17 22:20:51

算法竞赛备赛——【图论】链式前向星

图论图的存储方式： 通用的三种：邻接矩阵、邻接表、边集数组有向图：十字链表无向图：多重邻接表刷题常用：邻接矩阵、链式前向星（邻接表变形） 链式前向星算法题常用: 邻接矩阵、二维vector模…...

编程日记 2025/8/21 14:12:36

JAVA_类和对象

目录 1.面向对象的初步认知 1.1.什么是面向对象 1.2.面向对象与面向过程 2.类的定义和使用 2.1.简单认识类 2.2类的定义格式 2.3.练习学生类动物类（可爱猫猫🐱） 3.类的实例化 3.1.什么是实例化 3.2.类和对象的说明 4.this引用…...

编程日记 2025/8/17 22:22:40

高频面试题（含笔试高频算法整理）基本总结回顾65

干货分享，感谢您的阅读！ （暂存篇---后续会删除，完整版和持续更新见高频面试题基本总结回顾（含笔试高频算法整理）） 备注：引用请标注出处，同时存在的问题请在相关博客留言…...

编程日记 2025/8/19 8:10:21

数据库系统-数据库控制

并发控制事务的ACID特性： 原子性（Atomicity）：事务包含的所有操作要么全部成功（commit提交），要么全部失败（rollback回滚）一致性（Consistency）&a…...

编程日记 2025/8/17 12:59:57

Python Cookbook-5.3 根据对象的属性将对象列表排序

任务需要根据各个对象的某个属性来完成对整个对象列表的排序。解决方案 DSU方法仍然一如既往地有效: def sort_by_attr(sed,attr):intermed [ (getattr(x,attr),i,x) for i,x in enumerate(seg)]intermed.sort()return [ x[-1] for x in intermed def sort_by_attr_inpl…...

编程日记 2025/8/22 5:12:08

Java MCP SDK 开发笔记（一）

MCP 简介 AI 大模型诞生之初，其高度模拟人的对话之能力惊为天人。但我们肯定不希望止步于此—— 工具化就是我们希望 AI 能够完成的目标，由此可以从单纯的对话发展为代替繁复人力的“干活”。这条道路上毋庸置疑 AI 大模型任重道远。而 MCP(Model Contr…...

编程日记 2025/8/21 10:47:00

AF3 OpenFoldDataLoader类_prep_batch_properties_probs方法解读

AlphaFold3 data_modules 模块的 OpenFoldDataLoader 类的 _prep_batch_properties_probs 方法是为每个批次数据准备 recycling 维度的概率分布。它将根据配置文件中的设定为每个批次数据生成 recycling 轮次的概率分布，并存储到 prop_probs_tensor 中，用于后续抽样选择特定…...

编程日记 2025/8/21 23:57:56

寻找字符串数组中的最长共同前缀字符串

问题描述：给定一个字符串数组 strs，编写一个函数来找到这些字符串的最长公共前缀字符串，如果没有则返回空字符串"" 算法思路横向扫描法： 从数组的第一个字符串开始，逐个和后面的字符串比较，逐…...

编程日记 2025/8/20 2:27:07

leetcode_数组 56. 合并区间

56. 合并区间以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。示例 1： 输入：int…...

编程日记 2025/8/19 1:49:14

Jenkins学习（B站教程）

文章目录 1.持续集成CI2.持续交付CD3.持续部署4.持续集成的操作流程5.jenkins简介6.后续安装部署，见视频 bilibili视频 Jenkins是一个开源的、提供友好操作界面的持续集成(CI)工具，起源于Hudson（Hudson是商用的），主要用…...

编程日记 2025/8/22 16:49:44

学习笔记—C++—类和对象（一）

目录类和对象类的定义类定义格式访问限定符类域实例化实例化概念对象的大小 this指针 C和C语言实现Stack对比类和对象类的定义类定义格式 ● class为定义类的关键字，Stack为类的名字，{}中为类的主体，注意类定义结束时后…...

编程日记 2025/8/21 8:35:33

PyTorch 深度学习 || 6. Transformer | Ch6.3 Transformer 简单案例

1. 简单案例这个代码是一个简单的 Transformer 模型的实现，这个例子展示了一个基本的序列到序列（seq2seq）任务，比如将一个数字序列转换为另一个数字序列。可以用于学习和理解 Transformer 的基本结构和工作原理。 import torch import torch.nn as nn import math# 位置…...

编程日记 2025/8/22 11:06:40

体育风暴篮球足球体育球员综合资讯网站模板

源码名称：篮球足球体育球员综合资讯网站模板开发环境：帝国cms7.5 空间支持：phpmysql 带软件采集，可以挂着自动采集发布，无需人工操作！ 演示地址：https://www.52muban.com/shop/184016.html …...

编程日记 2025/8/21 14:13:06

Visual Studio Code SSH 连接超时对策（ keep SSH alive）

文章目录问题解决方法一：配置服务端关于ClientAliveInterval和ClientAliveCountMax1、打开终端，打开SSH配置文件：输入以下命令：2、打开配置文件后，添加以下内容：3、添加后，Esc按 <Enter>…...

编程日记 2025/8/19 2:55:04

Docker容器中的ubuntu apt update报错解决办法

问题现象 # apt update Get:1 http://archive.ubuntu.com/ubuntu noble InRelease [256 kB] Get:2 http://security.ubuntu.com/ubuntu noble-security InRelease [126 kB] Err:2 http://security.ubuntu.com/ubuntu noble-security InRelease At least one invalid signa…...

编程日记 2025/8/22 5:12:18

CV - 目标检测

物体检测目标检测和图片分类的区别： 图像分类（Image Classification） 目的：图像分类的目的是识别出图像中主要物体的类别。它试图回答“图像是什么？”的问题。输出：通常输出是一个标签或一组概率值&am…...

编程日记 2025/8/19 10:24:24

linux提权 corn 提权

corn提权 corn的基本使用方法 corn的作用就是可以定时的完成一下任务（如备份一下log 或者清除一下日志文件这些就是运维人员用的） 先找一下定时任务的工作表 cat /bin/corntab 这个是普通用户我们直接看都看不了说明什么说明这个是root高权限执…...

编程日记 2025/8/21 7:22:22

1Panel安装失败国内docker安装失败

本文仅针对学习交流，只为了帮助计算机相关专业大学生个人技能实操而记录非学习目的严禁学习！！！否则后果自负 1、离线安装1Panel（不需要手动安装docker，离线安装包里包括了docker） 离线包下载地…...

编程日记 2025/8/21 16:09:47

Excel + VBA 实现“准实时“数据的方法

Excel 本身是静态数据处理工具，但结合 VBA（Visual Basic for Applications）可以实现准实时数据更新，不过严格意义上的实时数据（如毫秒级刷新）仍然受限。以下是详细分析： 1. Excel + VBA 实现“准实时”数据的方法 (1) 定时刷新（Timer 或 Application.OnTime） Appl…...

编程日记 2025/8/19 14:10:55

请问你怎么看待测试，指导哪些测试的类型，有用过哪些测试方法？

作为深耕测试领域多年的博主，我始终认为测试是软件质量的守护者，更是推动研发流程优化的催化剂。以下从测试认知、分类体系到实战方法论，结合具体案例为你系统拆解：一、测试的本质认知测试≠找 Bug，而是通过系统性验证回答三个核心问题：软件是否符合用户需求？系统在…...

编程日记 2025/8/22 14:37:13

详解 Redis repl_backlog_buffer（如何判断增量同步）

一、repl_backlog_buffer 复制积压缓冲区（Replication Backlog Buffer） 是一个环形内存区域（Ring Buffer），用于临时保存主节点最近写入的写命令，以支持从节点断线重连后的增量同步。 1.1 三个复制偏移量 …...

编程日记 2025/8/20 23:51:34

工业操作系统国产化替代的战略路径与挑战分析

一、政策背景与战略意义工信部提出的 2027 年替换 80 万套工业操作系统计划，是中国制造业向智能化转型的核心举措。该政策旨在通过国产化替代，解决工业领域 “缺芯少魂” 的问题，构建自主可控的工业软件生态体系。当前，中国工业操…...

编程日记 2025/8/20 11:39:58

JMeter接口性能测试从入门到精通

前言： 本文主要介绍了如何利用jmter进行接口的性能测试 1.在测试计划中添加线程组 1.1.线程组界面中元素含义如果点击循环次数为永远： 2.添加HTTP取样器 2.1.填写登录接口的各个参数 2.2.在线程组下面增加查看结果树请求成功的情况： 请求…...

编程日记 2025/8/17 22:20:59

WinForm真入门(9)——RichTextBox控件详解

WinForm中RichTextBox控件详解：从基础到高级应用上一文中笔者重点介绍了TextBox控件的详细用法，忘记的请点击WinForm真入门(8)——TextBox控件详解，那么本文中的RichTextBox与TextBox有什么区别吗，光看名字的话，多了…...

编程日记 2025/8/20 14:01:45

Linux : 内核中的信号捕捉

目录一前言二信号捕捉的方法 1.sigaction()编辑 2. sigaction() 使用三可重入函数四 volatile 关键字一前言如果信号的处理动作是用户自定义函数,在信号递达时就调用这个函数,这称为捕捉信号。在Linux: 进程信号初识-CSDN博客这一篇中已经学习到了一种信号…...

编程日记 2025/8/18 0:02:29

Linux 字符串截取#与%

在Linux的Shell脚本中，#和%用于字符串截取，通过通配符模式匹配删除部分内容批量修改文件名技巧：Linux下#、##、%、%%符号操作详解-CSDN博客从左截取（# 和 ##） #：删除最短匹配左侧内容。 ##&#xff1a…...

编程日记 2025/8/18 0:40:17

Android学习总结之自定义View实战篇

场景一：自定义进度条在很多应用中，我们会看到一些独特样式的进度条，接下来就实现一个简单的圆形进度条。实现思路继承 View 类。重写 onDraw 方法，在该方法里使用 Canvas 和 Paint 来绘制圆形进度条。提供更新进度的方法。 …...

编程日记 2025/8/22 12:00:21

C++ STL 详解 ——list 的深度解析与实践指南

在 C 的标准模板库（STL）中，list作为一种重要的序列式容器，以其独特的双向链表结构和丰富的操作功能，在许多编程场景下发挥着关键作用。深入理解list的特性与使用方法，能帮助开发者编写出更高效、灵活的代码…...

编程日记 2025/8/20 7:18:14

open函数的概念和使用案例

open 是 Linux/Unix 系统中用于打开或创建文件的系统调用，返回一个文件描述符（File Descriptor），后续可通过该描述符进行文件读写等操作。以下是其核心概念和使用案例的详细说明： 1. 核心概念作用：打开或…...

编程日记 2025/8/17 23:39:36

整理一些大模型部署相关的知识

不一定有什么用, 不经常用还会忘掉. 之前被人问到一次,脑子卡壳回答不出要点, 非常尴尬! 在此记录一下使用心得, 偶尔回来翻看! 一并行方式 1.1 数据并行 (Data Parallelism) 主要用于模型训练阶段, 即将多个完整的模型副本分布到多个gpu上, 每个gpu运行一部分数据数据, 每个…...

编程日记 2025/8/21 17:31:39

算法刷题记录——LeetCode篇(2.10) [第191~200题](持续更新)

更新时间：2025-04-04 算法题解目录汇总：算法刷题记录——题解目录汇总技术博客总目录：计算机技术系列博客——目录页优先整理热门100及面试150，不定期持续更新，欢迎关注！ 198. 打家劫舍你是一个专业的…...

编程日记 2025/8/21 2:15:43

蓝桥杯备赛 Day 19 加练dfs

是否需要回溯? 输入参数有哪几个(当前dfs和下一个dfs什么会变?)？ 是否需要返回值? 一.1158: 八皇后 P1158 - 八皇后 - New Online Judge (ecustacm.cn) 学习: 1.dfs输入为层数，即行号i，因为是每行只放一个，下一个dfs就是i1 2…...

编程日记 2025/8/17 23:16:22

蓝桥杯-卡java排序

问题描述本题是一道针对 Java 中 Arrays.sort 的题目，因此只有一个数据，该数据可以把 int 类型的数组在使用 Arrays.sort 后卡成 O(n2)O(n2)。给定一个有 nn 个正整数的序列 aa，你需要将其升序排序后输出。输入格式第一行输入一个正整…...

编程日记 2025/8/21 12:25:00

内存管理模块

在 Linux 内核中，内存管理是一个复杂而关键的组成部分。内核空间的虚拟地址被划分为多个区域，每个区域有其特定的用途和映射机制。本文将详细介绍直接映射区（Direct Mapping Area）、vmalloc 区、永久内核映射区（Perma…...

编程日记 2025/8/20 2:27:09

Spring RestTemplate修仙指南：从HTTP萌新到请求大能的终极奥义

各位在Spring生态摸爬滚打的道友们！今天要解锁的是Spring官方御用HTTP法宝——RestTemplate！这货堪称Java界的"御剑飞行术"，虽然官方已推荐WebClient接棒，但江湖上仍有80%项目在用这员老将！准备好一键起飞了…...

编程日记 2025/8/21 11:09:19

cpp经典数论问题

题目如下思路代码如下...

编程日记 2025/8/18 0:02:49

Redis 线程模型：单线程也能快如闪电？

目录一、核心思想：快刀斩乱麻的“单线程”高手 🦸‍♂️二、为什么是“单线程”？🤔三、单线程如何做到高性能？✨ “I/O 多路复用”是关键！四、真的一直都只有“一个线程”吗？并不完全是&#x…...

编程日记 2025/8/20 18:09:31

游戏引擎学习第208天

运行游戏并回顾我们的情况今天，我们将继续完成之前中断的调试输出工作。最近的工作偏离了一些，展示了如何进行元编程的实践，主要涉及了一个小的解析器。尽管这个解析器本身是一个玩具，但它展示了如何完成一个完整的循环&#xf…...

编程日记 2025/8/20 1:37:05

JavaScript箭头函数介绍（=＞）（箭头函数不绑定自己的this，而是继承上下文的this；不能用于造函数）JavaScript =＞

文章目录 JavaScript箭头函数全解析箭头函数的基本语法简洁语法特性隐式返回值对象字面量返回词法绑定的this不适用箭头函数的场景对象方法构造函数DOM事件处理高级用法在数组方法中的应用链式调用柯里化函数性能考量1. 作为回调函数时减少创建闭包的开销2. 简化代码结构&am…...

编程日记 2025/8/20 4:38:16

数据对象：DTO、DO、PO和 BO的区别和关系

在Java开发中，DTO（Data Transfer Object）、DO（Domain Object）、PO（Persistent Object）和BO（Business Object）是常用的数据对象概念，下面为你详细介绍并给出简…...

编程日记 2025/8/21 1:56:15

Java内存模型详解：堆、栈、方法区

1. 堆（Heap） 作用：存放所有对象实例及数组，是垃圾回收的主要区域。结构： 新生代（Young Generation）： Eden区：新创建的对象首先分配在此。 Survivor区（From…...

编程日记 2025/8/21 19:21:39

ubuntu 20.04 编译运行LeGo_LOAM 跑数据集并且保存pcl文件

1.搭建文件目录,clone代码,编译 mkdir -p Lego_LOAM/src cd Lego_LOAM/src git clone https://github.com/RobustFieldAutonomyLab/LeGO-LOAM.git cd .. catkin_make -j1 错误1：: fatal error: opencv/cv.h: 没有那个文件或目录 13 | #include <opencv/cv.h…...

编程日记 2025/8/20 11:49:54

一 AVL树的概念

二 AVL树的实现

2.1 AVL树的结构

2.2 AVL树的插入

2.2.1 AVL树插⼊⼀个值的⼤概过程

2.2.2 平衡因⼦更新

2.2.3 插入节点以及更新平衡因子的代码实现

2.3 AVL树的查找

2.4 AVL树的平衡检测

2.5 AVL树的删除

相关文章：