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

学习第十一天-树

news 来源：原创 2025/8/30 4:37:05

一、树的基础概念

1. 定义

树是一种非线性数据结构，由 n 个有限节点组成层次关系集合。特点：

有且仅有一个根节点
其余节点分为若干互不相交的子树
节点间通过父子关系连接

2. 关键术语

术语	定义
节点	包含数据和子节点引用的单元
根节点	树的起始节点，没有父节点
子节点	直接连接到父节点的节点
叶子节点	没有子节点的节点
度	节点拥有的子树数目
树的高度	从根节点到最远叶子节点的最长路径边数
树的深度	从根节点到当前节点的层数
路径	从根到某节点的唯一通道

3. 分类

二叉树：每个节点最多两个子节点（左子树 / 右子树）
多叉树：每个节点可包含多个子节点（如三叉树、四叉树）
有序树：子树顺序有意义（如二叉搜索树）
无序树：子树顺序无关

二、二叉树的核心特性

1. 特殊二叉树

满二叉树：所有层节点数达到最大值
完全二叉树：最后一层节点靠左排列，其余层满
二叉搜索树：左子树值 < 根值 < 右子树值

2. 重要性质

第 i 层最多有 2^(i-1) 个节点
高度为 h 的二叉树最多有 2^h -1 个节点
完全二叉树节点编号 i 的子节点为 2i 和 2i+1
叶子节点数 = 度为 2 的节点数 + 1

3. 存储结构

方式	实现方式	适用场景
数组存储	按层序编号存储节点值	完全二叉树
链式存储	结构体包含左右指针	任意二叉树

三、二叉树遍历方法

1. 深度优先遍历

前序遍历：根→左→右
递归实现:

收起

python

def preorder(root):if root:print(root.val)preorder(root.left)preorder(root.right)

中序遍历：左→根→右
应用: 二叉搜索树中序遍历结果有序
后序遍历：左→右→根
应用: 计算表达式树

2. 广度优先遍历

层序遍历：逐层访问节点
队列实现:

收起

python

def levelorder(root):queue = [root]while queue:node = queue.pop(0)print(node.val)if node.left: queue.append(node.left)if node.right: queue.append(node.right)

3. 遍历对比

遍历方式	时间复杂度	空间复杂度	典型应用
前序	O(n)	O(h)	复制树、生成括号
中序	O(n)	O(h)	二叉搜索树排序
后序	O(n)	O(h)	删除树、计算表达式
层序	O(n)	O(w)	层次处理、找最近公共祖先

四、树结构的典型应用

文件系统：目录结构（Windows 资源管理器）
XML/JSON 解析：文档对象模型（DOM）
数据库索引：B 树 / B + 树优化查询
压缩算法：哈夫曼树构建最优前缀编码
人工智能：决策树、蒙特卡洛树搜索
网络路由：路由表的层次化存储

五、高级树结构详解

5.1 B 树（B-Tree）

5.1.1 定义与特性

平衡多路查找树，所有叶子节点在同一层
阶数 m：每个节点最多有 m 个子节点（m≥2）
关键特性：
- 根节点至少 2 个子节点
- 非根节点至少⌈m/2⌉个子节点
- 叶子节点包含所有数据

5.1.2 操作复杂度

操作	时间复杂度
查找	O(log_m n)
插入	O(log_m n)
删除	O(log_m n)

5.1.3 典型应用

数据库索引（如 MySQL 的 InnoDB 引擎）
文件系统目录结构
外部存储数据管理

5.1.4 与二叉搜索树对比

特性	B 树	二叉搜索树
平衡方式	多叉平衡	二叉平衡
查找效率	更低的 I/O 次数	依赖树的高度
适用场景	外存数据管理	内存数据管理

5.2 红黑树（Red-Black Tree）

5.2.1 定义与性质

自平衡二叉搜索树，通过颜色标记保持平衡
五大性质：
1. 节点颜色为红或黑
2. 根节点为黑色
3. 叶子节点（NIL）为黑色
4. 红节点的子节点必须为黑色
5. 从任一节点到其叶子的路径包含相同数量黑节点

5.2.2 操作复杂度

操作	时间复杂度
查找	O(log n)
插入	O(log n)
删除	O(log n)

5.2.3 典型应用

Java 的 TreeMap/TreeSet
C++ 的 std::map
Linux 内核的进程调度
Nginx 的定时器管理

5.2.4 旋转操作

左旋转：将某个节点作为支点向左下方旋转
右旋转：将某个节点作为支点向右上方旋转
示例代码片段：

收起

python

def left_rotate(x):y = x.rightx.right = y.leftif y.left:y.left.parent = xy.parent = x.parentif x.parent is None:root = yelif x == x.parent.left:x.parent.left = yelse:x.parent.right = yy.left = xx.parent = y

5.3 其他重要树结构

类型	核心特性	典型应用
AVL 树	严格平衡（左右子树高度差≤1）	内存中的有序数据
哈夫曼树	带权路径长度最小	数据压缩（如 ZIP 算法）
B + 树	所有数据在叶子节点，非叶子存索引	数据库索引
线段树	区间查询优化	统计类问题
字典树 (Trie)	前缀共享存储	拼写检查、IP 路由表

六、树结构对比与选择策略

6.1 平衡树对比

结构	平衡条件	插入 / 删除复杂度	适用场景
B 树	多叉平衡	O(log_m n)	外存数据管理
红黑树	颜色标记平衡	O(log n)	内存有序结构
AVL 树	高度差平衡	O(log n)	频繁查询场景

6.2 选择策略

内存场景：
- 数据量小 → 二叉搜索树
- 数据量大 → 红黑树 / AVL 树
外存场景：
- 读多写少 → B + 树
- 读写均衡 → B 树
特殊需求：
- 前缀匹配 → Trie 树
- 数据压缩 → 哈夫曼树

七、树结构算法优化技巧

空间优化：
- 使用数组存储完全二叉树（节省指针空间）
- 共享子树结构（如 Trie 树的前缀共享）
时间优化：
- 利用缓存友好性（B 树的节点大小与磁盘块对齐）
- 延迟更新（如红黑树的懒删除）
并行处理：
- 多叉树的多路并行查找
- 分布式哈希表（DHT）的树状路由

学习第十一天-树

一、树的基础概念 1. 定义树是一种非线性数据结构，由 n 个有限节点组成层次关系集合。特点： 有且仅有一个根节点其余节点分为若干互不相交的子树节点间通过父子关系连接 2. 关键术语术语定义节点包含数据和子节点引用的单元根节点树的起始节点&#…...

编程日记 2025/8/30 4:37:05

场景题：10亿QQ用户，如何统计在线人数？

现在卷的环境下，面试除了八股文算法项目外，场景题也是问的越来越多了。一方面是就业市场竞争者较多所带来的必然结果；另一方面是公司对于应聘者的技术要求也越来越高了。今天继续介绍Java面试常见的场景题：在线人数统计现在用户…...

编程日记 2025/8/29 11:38:35

学习工具的一天之（burp）

第一呢一定是先下载【Java环境】：Java Downloads | Oracle 下来是burp的下载 Download Burp Suite Community Edition - PortSwigger 【下载方法二】关注的一个博主【BurpSuite 安装激活使用详细上手教程 web安全测试工具】https://www.bilibili.com/video/BV…...

编程日记 2025/8/29 3:17:50

归并排序：分治哲学的完美演绎与时空平衡的艺术

引言：跨越世纪的算法明珠在计算机科学的璀璨星河中，归并排序犹如一颗恒久闪耀的明星。1945年，现代计算机之父冯诺伊曼在EDVAC计算机的研发过程中首次系统性地提出了这一算法，其精妙的分治思想不仅奠定了现代排序算法的理论基础&…...

编程日记 2025/8/28 1:43:56

知识点：串口(单片机发送数据)按键ADC 题目配置代码 adc.c uint16_t getadc2(void) {uint16_t adc0;HAL_ADC_Start(&hadc2);adcHAL_ADC_GetValue(&hadc2);return adc; } adc.h uint16_t getadc2(void); main.c #include "lcd.h" #include…...

编程日记 2025/8/28 10:23:37

Stable Diffusion Prompt编写规范详解

Stable Diffusion Prompt编写规范详解一、语法结构规范 （一）基础模板框架 [质量强化] [主体特征] [环境氛围] [风格控制] [镜头参数]质量强化：best quality, ultra detailed, 8k resolution‌主体特征：(1girl:1.3), long …...

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

es6常见知识点

官方文档：[https://es6.ruanyifeng.com/](https://es6.ruanyifeng.com/) 一、Class 1、Class Class只是一个语法糖,其功能用es5也能实现,但是比es5更符合类的期待定义: constructor代表构造方法,而this指向new 生成的实例定义类方法时,可以不使用function 注…...

编程日记 2025/8/27 12:28:19

leetcode1 两数之和哈希表

什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。 242. 有效的字母异位词 (opens new window)这道题目是用数组作为哈希表来解决哈希问题，349. 两个数组的交集 (o…...

编程日记 2025/8/29 18:37:31

Java中lombok的@Data注解【布尔类型】字段定义方式

文章目录背景第一步、场景复现第二步、分析问题第三步、实现方案总结背景在Data注解的bean中添加Boolean字段时，set方法正常，get方法无法获取。第一步、场景复现在OrderInfo的实体中，新增布尔类型的字段：支付过【hasPaid】…...

编程日记 2025/8/29 1:00:17

理解数学概念——稠密性(density)

目录 1. 定义 2. 等价定义 3. 直观理解 1. 定义在拓扑学(topology)和数学相关领域中，对于一个拓扑空间 X 的一个子集 A，若 X的每一个点要么属于A ，要么无限“接近”X的某个成员，则称这个子集 A 是稠密的(dense)或称A具有稠密性…...

编程日记 2025/8/28 20:55:17

【Spring AOP】_切点类的切点表达式

目录 1. 根据方法签名匹配编写切点表达式 1.1 具体语法 1.2 通配符表达规范 2. 根据注解匹配编写切点表达式 2.1 实现步骤 2.2 元注解及其常用取值含义 2.3 使用自定义注解 2.3.1 编写自定义注解MyAspect 2.3.2 编写切面类MyAspectDemo 2.3.3 编写测试类及测试方法在…...

编程日记 2025/8/28 21:43:28

通过多线程获取RV1126的AAC码流

目录一RV1126多线程获取音频编码AAC码流的流程 1.1AI模块的初始化并使能 1.2AENC模块的初始化 1.3绑定AI模块和AENC模块 1.4多线程获取每一帧AAC码流 1.5每个AAC码流添加ADTSHeader头部 1.6写入具体每一帧AAC的…...

编程日记 2025/8/27 9:37:07

HDFS 为什么不适合处理小文件？

目录一、HDFS 是什么？ 1. 核心目标 2. 基本架构二、HDFS 为什么不适合处理小文件？ 1. 元数据管理问题 2. 存储效率低下 3. 访问性能问题 4. 计算框架效率问题 5. 其他限制一、HDFS 是什么？ HDFS（Hadoop 分布式文件系统…...

编程日记 2025/8/29 9:59:28

网络空间安全（14）编辑器漏洞

一、概述网页在线编辑器允许用户在网页上进行文本的编辑，并设置字体样式、段落行间距等，类似于使用Word进行编辑。然而，由于编辑器在处理用户输入、文件上传、权限控制等方面可能存在安全缺陷，因此容易成为攻击者利用的目标。二…...

编程日记 2025/8/28 15:00:24

SpringMvc与Struts2

一、Spring MVC 1.1 概述 Spring MVC 是 Spring 框架的一部分，是一个基于 MVC 设计模式的轻量级 Web 框架。它提供了灵活的配置和强大的扩展能力，适合构建复杂的 Web 应用程序。 1.2 特点轻量级：与 Spring 框架无缝集成，依赖…...

编程日记 2025/8/29 23:27:04

Avalonia 打包成deb

参考 https://www.cnblogs.com/Fengyinyong/p/13346642.html 安装工具 dotnet tool install --global dotnet-deb 还原包 dotnet restore -r linux-x64 dotnet deb install 打包，其中/p:SelfContainedtrue是独立运行 dotnet msbuild XXXCore.csproj /t:Creat…...

编程日记 2025/8/29 20:36:57

服务器数据恢复—raid5阵列中硬盘掉线导致上层应用不可用的数据恢复案例

服务器数据恢复环境&故障： 某公司一台服务器，服务器上有一组由8块硬盘组建的raid5磁盘阵列。磁盘阵列中2块硬盘的指示灯显示异常，其他硬盘指示灯显示正常。上层应用不可用。服务器数据恢复过程： 1、将服务器中所有硬盘编号…...

编程日记 2025/8/28 19:36:21

除了合并接口，还有哪些优化 Flask API 的方法？

除了合并接口，还有许多其他方法可以优化 Flask API，以下从性能优化、代码结构优化、安全性优化、错误处理优化等方面详细介绍： 性能优化 1. 使用缓存内存缓存：可以使用 Flask-Caching 扩展来实现内存缓存，减少对数…...

编程日记 2025/8/29 13:04:15

制服小程序的“滑手”：禁用页面左右滑动全攻略

哈哈，看来你已经很聪明地发现了小程序中左右滑动的“顽皮”行为！😄 没错，我们可以通过设置 disableScroll 属性来“管教”它，同时结合 CSS 样式让页面既禁得住横向“乱跑”，又能顺畅地上下滚动。你的方案已…...

编程日记 2025/8/29 1:35:36

学习日记-250305

阅读论文：Leveraging Pedagogical Theories to Understand Student Learning Process with Graph-based Reasonable Knowledge Tracing ps:代码逻辑最后一点还没理顺，明天继续 4.2 Knowledge Memory & Knowledge Tracing 代码研究： 一般…...

编程日记 2025/8/28 10:27:27

DeepSeek R1模型医疗机构本地化部署评估分析（Discuss V1版上）

为了确保医疗机构在部署和应用DeepSeek R1模型时的成功，可以根据各个步骤设计一套综合的评估和评测体系。该体系将帮助医疗机构在实施过程中持续跟踪效果、识别潜在问题并进行优化调整。以下是对各步骤的详细评估和评测体系设计。 1. 确定模型需求在医疗机构上线DeepSeek R…...

编程日记 2025/8/28 21:06:30

java 查找连个集合的交集部分数据

利用了Java 8的Stream API，代码简洁且效率高 import java.util.stream.Collectors; import java.util.List; import java.util.HashSet; import java.util.Set;public class ListIntersection {public static List<Long> findIntersection(List<Long> …...

编程日记 2025/8/29 6:28:38

Hadoop管理页看不到任务的问题

这个yarn分配任务了但是为空在$HADOOP_HOME/conf/mapred-site.xml 原来的配置文件基础之上添加： <property><name>mapreduce.framework.name</name><value>yarn</value></property> 重启之后就好了...

编程日记 2025/8/28 16:44:12

cmake、CMakeLists.txt、make、ninja

文章目录一、概念0.cmake官网1.什么是cmake2.为什么使用cmake3.CMakeLists.txt 二、CMakeLists.txt语法：如何编写CMakeLists.txt，语法详解(0)语法基本原则(1)project关键字(2)set关键字(3)message关键字(4)add_executable关键字(5)add_subdirectory关键…...

编程日记 2025/8/30 0:39:45

PHP之Cookie和Session

在你有别的编程语言的基础下，你想学习PHP，可能要了解的一些关于cookie和session的信息。 Cookie 参数信息 setcookie(name,value,expire, path, domain); name : Cookie的名称。 value : Cookie的值。 expire : Cookie的过期时间，可以是一…...

编程日记 2025/8/28 16:13:16

学习记录-用例设计编写

黑马测试视频记录目录一、软件测试流程二、测试用例编写格式 1、等价类法 2、边界值分析法 3、判定表法 4、场景法编辑 5、错误推荐法一、软件测试流程二、测试用例编写格式 1、等价类法 2、边界值分析法 3、判定表法 4、场景法 5、错误推荐法时间紧任务重…...

编程日记 2025/8/29 14:16:26

【Docker】容器安全之非root用户运行

【Docker】容器安全之非root用户运行 1. 场景2. 原 Dockerfile 内容3. 整改结果4. 非 root 用户带来的潜在问题4.1 文件夹读写权限异常4.2 验证文件夹权限 1. 场景最近有个项目要交付，第三方测试对项目源码扫描后发现一个问题，服务的 Dockerfile 都未指…...

编程日记 2025/8/28 19:41:15

CVE-2025-0392：JeeWMS graphReportController.do接口SQL注入漏洞复现

文章目录 CVE-2025-0392：JeeWMS graphReportController.do接口SQL注入漏洞复现0x01 前言0x02 漏洞描述0x03 影响版本0x04 漏洞环境0x05 漏洞复现1.构造POC2.复现CVE-2025-0392：JeeWMS graphReportController.do接口SQL注入漏洞复现 0x01 前言免责声明：请勿利用文章内的相…...

编程日记 2025/8/27 18:50:30

如何使用 Python+Flask+win32print 实现简易网络打印服务1

Python 实现网络打印机：Flask win32print 在工作场景中，我们可能需要一个简单的网页接口，供他人上传文档并自动打印到指定打印机。本文将演示如何使用 Python Flask win32print 库来实现这一需求。代码详见：https://github.…...

编程日记 2025/8/29 17:02:38

Ubuntu20.04双系统安装及软件安装（十一）：向日葵远程软件

Ubuntu20.04双系统安装及软件安装（十一）：向日葵远程软件打开向日葵远程官网，下载图形版本： 在下载目录下打开终端，执行： sudo dpkg -i SunloginClient(按tab键自动补全)出现报错： …...

编程日记 2025/8/27 23:28:12

鸿蒙启动页开发

鸿蒙启动页开发 1.1 更改应用名称和图标 1.更改应用图标找到moudle.json5文件，找到应用启动的EntryAbility下面的icon,将原来的图标改成自己设置的即可 2.更改应用名称 3.效果展示 2.1 广告页面开发 3.1 详细介绍 3.1.1 启动页面 import { PrivacyDialog } fr…...

编程日记 2025/8/29 3:45:43

认知动力学视角下的生命优化系统：多模态机器学习框架的哲学重构

认知动力学视角下的生命优化系统：多模态机器学习框架的哲学重构一、信息熵与生命系统的耗散结构在热力学第二定律框架下，生命系统可视为负熵流的耗散结构： d S d i S d e S dS d_iS d_eS dSdiSdeS 其中 d i S d_iS diS为内部熵…...

编程日记 2025/8/28 17:43:07

【Python编程】高性能Python Web服务部署架构解析

一、FastAPI 与 Uvicorn/Gunicorn 的协同 1. 开发环境：Uvicorn 直接驱动作用：Uvicorn 作为 ASGI 服务器，原生支持 FastAPI 的异步特性，提供热重载（--reload）和高效异步请求处理。启动命令： u…...

编程日记 2025/8/28 9:32:37

仿mudou库one thread oneloop式并发服务器

项目gitee：仿muduo: 仿muduo 一：项目目的 1.1项目简介通过咱们实现的⾼并发服务器组件，可以简洁快速的完成⼀个⾼性能的服务器搭建。并且，通过组件内提供的不同应⽤层协议⽀持，也可以快速完成⼀个⾼性能应⽤服务器…...

编程日记 2025/8/28 14:26:51

AI推理模型竞赛：从DeepSeek R1到Claude 3.7的关键进展

摘要在Reasoning Model首轮竞赛中，从R1到Sonnet 3.7，AI领域取得了显著进展。DeepSeek R1的发布激发了推理模型的竞争。过去一个月内，顶尖AI实验室相继推出了三款最新的SOTA推理模型：OpenAI的o3-mini和deep research，x…...

编程日记 2025/8/29 0:27:59

AORO P9000 PRO三防平板携手RTK高精度定位，电力巡检效率倍增

电网系统覆盖幅员辽阔，每年因设备故障导致的巡检耗时超过百万工日。传统巡检模式受限于定位误差、设备防护不足和作业效率低下三大核心痛点，亟需智能化工具的突破性革新。为了满足这一需求，遨游通讯推出AORO P9000 PRO三防平板，以…...

编程日记 2025/8/29 8:56:01

【Linux———信号精讲】

你是怎么做到的，给了她想要的爱............................................................................................ 文章目录前言一、【信号入门】 1.1、【生活角度的信号】 1.2、【ctrl c与z】 1.3、【信号的发送与记录】 1.4、【信号处理常见方式…...

编程日记 2025/8/28 19:17:32

Unity 文字高度自适应

期望文字有字号限制，输入文字文字后先判断高度是否适用于限制字号，若处于最小字号时高度任不适用，则调整RectTransform 的高度。核心代码每次输入文字时先将字号设定为原始字号。 comp.fontSize fontSize; comp.text content; 拓展T…...

编程日记 2025/8/29 13:54:21

鸿蒙通过用户首选项实现数据持久化

鸿蒙通过用户首选项实现数据持久化 1.1 场景介绍用户首选项为应用提供Key-Value键值型的数据处理能力，支持应用持久化轻量级数据，并对其修改和查询。当用户希望有一个全局唯一存储的地方，可以采用用户首选项来进行存储。Preferences会将该…...

编程日记 2025/8/29 2:34:00

数字图像相关(DIC)技术用于生物力学和生物材料测试

生物医学工程是一个跨学科科学领域，旨在改善人类健康和医疗护理。从工程的角度来看，生物材料、力生物学和生物制造与目标生物系统的相互作用，以实现各种医学治疗目的。数字图像相关(DIC)技术，作为一种非接触、精准高效、无损的全场…...

编程日记 2025/8/27 13:40:01

java8中young gc的垃圾回收器选型，您了解嘛

在 Java 8 的 Young GC（新生代垃圾回收）场景中，对于 ToC的场景，即需要尽可能减少垃圾回收停顿时间以满足业务响应要求的场景，以下几种收集器各有特点，通常 Parnew和 G1 young表现较为出色，下面详…...

编程日记 2025/8/30 4:08:51

【五.LangChain技术与应用】【13.LangChain与智普大模型接入：行业领先的AI整合】

当LangChain遇到智普大模型：拆解一个AI整合的超级方案最近半年，我一直在跟几个创业团队合作搞AI落地项目，发现一个特别有意思的现象：现在企业想用大模型干点实事，最大的痛点反而不是模型本身的能力，而是怎么把模型"塞"进现有系统里，还要塞得优雅、塞得高效。…...

编程日记 2025/8/27 18:20:48

【＜一＞炼丹初探：JavaWeb 的起源与基础】之 Servlet 与 JSP 的协作：MVC 模式的雏形

<前文回顾> 点击此处查看合集 https://blog.csdn.net/foyodesigner/category_12907601.html?fromshareblogcolumn&sharetypeblogcolumn&sharerId12907601&sharereferPC&sharesourceFoyoDesigner&sharefromfrom_link <今日更新> 一、Servl…...

编程日记 2025/8/28 17:15:47