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

学习第十一天-树

一、树的基础概念

1. 定义

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

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

2. 关键术语

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

3. 分类

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

二、二叉树的核心特性

1. 特殊二叉树

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

2. 重要性质

  1. 第 i 层最多有 2^(i-1) 个节点
  2. 高度为 h 的二叉树最多有 2^h -1 个节点
  3. 完全二叉树节点编号 i 的子节点为 2i 和 2i+1
  4. 叶子节点数 = 度为 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)层次处理、找最近公共祖先

四、树结构的典型应用

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

五、高级树结构详解

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 选择策略

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

七、树结构算法优化技巧

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

相关文章:

学习第十一天-树

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

网络服务之SSH协议

一.SSH基础 1.1 什么是ssh SSH&#xff08;Secure Shell&#xff09;协议是一种用于字符界面远程登录和数据加密传输的协议。 1.2 ssh优点 优点&#xff1a; 数据传输是加密的&#xff0c;可以防止信息泄漏 数据传输是压缩的&#xff0c;可以提高传输速度 注意&#xff…...

蓝桥杯 之 前缀和与查分

文章目录 题目求和棋盘挖矿 前缀和有利于快速求解 区间的和、异或值 、乘积等情况差分是前缀和的反操作 前缀和 一维前缀和&#xff1a; # 原始的数组num,下标从1到n n len(num) pre [0]*(n1) for i in range(n):pre[i1] pre[i] num[i] # 如果需要求解num[l] 到num[r] 的区…...

GB28181开发--ZLMediaKit‌+WVP+Jessibuca‌

一、核心组件功能 1‌、ZLMediaKit‌ 定位‌:基于 C++11 的高性能流媒体服务框架,支持 RTSP/RTMP/HLS/HTTP-FLV 等协议互转,具备低延迟(最低 100ms)、高并发(单机 10W 级连接)特性,适用于商用级流媒体服务器部署‌。 ‌特性‌:跨平台(Linux/Windows/ARM 等)、支持 …...

Ubuntu20.04 在离线机器上安装 NVIDIA Container Toolkit

步骤 1.下载4个安装包 Index of /nvidia-docker/libnvidia-container/stable/ nvidia-container-toolkit-base_1.13.5-1_amd64.deb libnvidia-container1_1.13.5-1_amd64.deb libnvidia-container-tools_1.13.5-1_amd64.deb nvidia-container-toolkit_1.13.5-1_amd64.deb 步…...

如何快速上手RabbitMQ 笔记250304

如何快速上手RabbitMQ 要快速上手 RabbitMQ&#xff0c;可以按照以下步骤进行&#xff0c;从安装到基本使用逐步掌握核心概念和操作&#xff1a; 1. 理解核心概念 Producer&#xff08;生产者&#xff09;&#xff1a;发送消息的程序。Consumer&#xff08;消费者&#xff09…...

无人机端部署 AI 模型,实现实时数据处理和决策

在无人机端部署 AI 模型&#xff0c;实现实时数据处理和决策&#xff0c;是提升无人机智能化水平的关键技术之一。通过将 AI 模型部署到无人机上&#xff0c;可以实现实时目标检测、路径规划、避障等功能。以下是实现这一目标的详细方案和代码示例。 一、实现方案 1. 硬件选择…...

CentOS 7中安装Dify

Dify 是一个开源的 LLM 应用开发平台。其直观的界面结合了 AI 工作流、RAG 管道、Agent、模型管理、可观测性功能等&#xff0c;让您可以快速从原型到生产。尤其是我们本地部署DeepSeek等大模型时&#xff0c;会需要用到Dify来帮我们快捷的开发和应用。 大家可以参考学习它的中…...

CoDrivingLLM

CoDrivingLLM 思路 1.输入和输出 输入 算法的输入包括车辆当前时刻的状态 S t S_t St​ &#xff0c;这个状态包含了车辆的位置、速度、行驶方向等信息&#xff1b;以及参与协同驾驶的联网自动驾驶汽车列表C&#xff0c;用于确定需要进行决策的车辆集合。 输出 输出为车辆…...

Centos7升级openssl和openssh最新版

1、事前准备 下载openssl3.4.1和openssh9.9p2压缩包上传到服务器 https://cdn.openbsd.org/pub/OpenBSD/OpenSSH/portable// Release OpenSSL 3.4.1 openssl/openssl GitHub 2、查看centos7、ssh以及openssl的版本信息 # 查看CentOS系统版本信息 cat /etc/redhat-release …...

相控阵扫盲

下图展示天线增益 在仰角为0度的情况下随着方位角的变化而变化。需要注意到的是在天线视轴方向上的高增益主瓣上还有几个低增益旁瓣 阵列因子乘以新的阵元方向图会形成指向性更强的波速...

nginx 配置 301跳转

HTTP 跳转到 HTTPS 将所有 HTTP 请求&#xff08;80 端口&#xff09;跳转到 HTTPS&#xff08;443 端口&#xff09;&#xff1a; server {listen 80;server_name example.com;# 跳转到 HTTPSreturn 301 https://$host$request_uri; }server {listen 443 ssl;server_name exa…...

开发环境搭建-03.后端环境搭建-使用Git进行版本控制

一.Git进行版本控制 我们对项目开发就会产生很多代码&#xff0c;我们需要有效的将这些代码管理起来&#xff0c;因此我们真正开发代码前需要把我们的Git环境搭建好。通过Git来管理我们项目的版本&#xff0c;进而实现版本控制。 首先我们使用Git创建本地仓库&#xff0c;然后…...

vivado 充分利用 IP 核

充分利用 IP 核 使用预先验证的 IP 核能够大幅减少设计和验证工作量&#xff0c;从而加速产品上市进程。如需了解更多有利用 IP 的信息&#xff0c;请参 阅以下资源&#xff1a; • 《 Vivado Design Suite 用户指南&#xff1a;采用 IP 进行设计》 (UG896) [ 参照 1…...

外盘农产品期货数据:历史高频分钟回测的分享下载20250305

外盘农产品期货数据&#xff1a;历史高频分钟回测的分享下载20250305 在国际期货市场中&#xff0c;历史分钟高频数据的作用不可小觑。这些数据以分钟为时间尺度&#xff0c;详细记录了期货合约的价格变动和交易量信息&#xff0c;为投资者提供了全面、深入的市场分析视角。通…...

计算机毕设-基于springboot的网上商城系统的设计与实现(附源码+lw+ppt+开题报告)

博主介绍&#xff1a;✌多个项目实战经验、多个大型网购商城开发经验、在某机构指导学员上千名、专注于本行业领域✌ 技术范围&#xff1a;Java实战项目、Python实战项目、微信小程序/安卓实战项目、爬虫大数据实战项目、Nodejs实战项目、PHP实战项目、.NET实战项目、Golang实战…...

用DeepSeek-R1-Distill-data-110k蒸馏中文数据集 微调Qwen2.5-7B-Instruct!

下载模型与数据 模型下载&#xff1a; huggingface&#xff1a; Qwen/Qwen2.5-7B-Instruct HF MirrorWe’re on a journey to advance and democratize artificial intelligence through open source and open science.https://hf-mirror.com/Qwen/Qwen2.5-7B-Instruct 魔搭&a…...

【C++设计模式】第四篇:建造者模式(Builder)

注意&#xff1a;复现代码时&#xff0c;确保 VS2022 使用 C17/20 标准以支持现代特性。 分步骤构造复杂对象&#xff0c;实现灵活装配 1. 模式定义与用途 核心目标&#xff1a;将复杂对象的构建过程分离&#xff0c;使得同样的构建步骤可以创建不同的表示形式。 常见场景&am…...

【杂谈】信创电脑华为w515(统信系统)登录锁定及忘记密码处理

华为w515麒麟芯片版&#xff0c;还有非麒麟芯片版本&#xff0c;是一款信创电脑&#xff0c;一般安装的UOS系统。 准备一个空U盘&#xff0c;先下载镜像文件及启动盘制作工具&#xff0c;连接如下&#xff1a; 百度网盘 请输入提取码 http://livecd.uostools.com/img/apps/l…...

VBA信息获取与处理第五节:如何在单个工作表中查找某个给定值

《VBA信息获取与处理》教程(版权10178984)是我推出第六套教程&#xff0c;目前已经是第一版修订了。这套教程定位于最高级&#xff0c;是学完初级&#xff0c;中级后的教程。这部教程给大家讲解的内容有&#xff1a;跨应用程序信息获得、随机信息的利用、电子邮件的发送、VBA互…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

大语言模型如何处理长文本?常用文本分割技术详解

为什么需要文本分割? 引言:为什么需要文本分割?一、基础文本分割方法1. 按段落分割(Paragraph Splitting)2. 按句子分割(Sentence Splitting)二、高级文本分割策略3. 重叠分割(Sliding Window)4. 递归分割(Recursive Splitting)三、生产级工具推荐5. 使用LangChain的…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

Java多线程实现之Callable接口深度解析

Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...

Map相关知识

数据结构 二叉树 二叉树&#xff0c;顾名思义&#xff0c;每个节点最多有两个“叉”&#xff0c;也就是两个子节点&#xff0c;分别是左子 节点和右子节点。不过&#xff0c;二叉树并不要求每个节点都有两个子节点&#xff0c;有的节点只 有左子节点&#xff0c;有的节点只有…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

抽象类和接口(全)

一、抽象类 1.概念&#xff1a;如果⼀个类中没有包含⾜够的信息来描绘⼀个具体的对象&#xff0c;这样的类就是抽象类。 像是没有实际⼯作的⽅法,我们可以把它设计成⼀个抽象⽅法&#xff0c;包含抽象⽅法的类我们称为抽象类。 2.语法 在Java中&#xff0c;⼀个类如果被 abs…...

云安全与网络安全:核心区别与协同作用解析

在数字化转型的浪潮中&#xff0c;云安全与网络安全作为信息安全的两大支柱&#xff0c;常被混淆但本质不同。本文将从概念、责任分工、技术手段、威胁类型等维度深入解析两者的差异&#xff0c;并探讨它们的协同作用。 一、核心区别 定义与范围 网络安全&#xff1a;聚焦于保…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

职坐标物联网全栈开发全流程解析

物联网全栈开发涵盖从物理设备到上层应用的完整技术链路&#xff0c;其核心流程可归纳为四大模块&#xff1a;感知层数据采集、网络层协议交互、平台层资源管理及应用层功能实现。每个模块的技术选型与实现方式直接影响系统性能与扩展性&#xff0c;例如传感器选型需平衡精度与…...