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

【数据结构】树哈希

news 来源：原创 2025/5/9 14:11:49

一、树的同构
- 1. 定义
- 2. 具体理解
- - (1) 结点对应
  - (2) 孩子相同
  - (3) 递归性质
- 3. 示例
二、树哈希
- 1.定义
- 2.哈希过程
- - （1）叶节点哈希
  - （2）非叶节点哈希
  - （3）组合哈希值
- 3.性质
- - （1） $\red{\texttt{唯一性}}$
  - （2）快速比较
  - （3）检测修改
- 4.应用
- 5.示例
- - （1）*first step*
  - （2）*second step*
  - （3）*third step*

一、树的同构

树的同构是一个重要的概念，以下是关于树的同构的详细定义：

1. 定义

给定两棵树 $T 1$ 和 $T 2$ ，如果 $T 1$ 可以通过若干次左右孩子互换就变成 $T 2$ ，则称这两棵树是“同构”的。这意味着，两棵树中的每两个对应结点的孩子必须相同，但左右位置可以不一样。

2. 具体理解

(1) 结点对应

两棵树中的结点需要一一对应，即每一个结点都有一个与之对应的结点，且这些对应结点的值需要相等。

(2) 孩子相同

对应结点的孩子（即子结点）必须相同，也就是说，对应结点左孩子和右孩子的数量和值都要相等，但它们的左右位置可以互换。

(3) 递归性质

由于树是递归定义的，因此树的同构也具有递归性质。即，如果两棵树的根结点对应，且它们的左子树和右子树（不考虑左右顺序）分别同构，则这两棵树就是同构的。

3. 示例

例如，有以下两棵树：

树 $A$ ：根结点为 $1$ ，左子结点为 $2$ ，右子结点为 $3$ 。
树 $B$ ：根结点为 $1$ ，左子结点为 $3$ ，右子结点为 $2$ 。

虽然树 $A$ 和树 $B$ 的左右子结点位置不同，但它们的根结点值相同，且左子结点和右子结点的值也相同（只是位置互换），因此可以认为这两棵树是同构的。

综上所述，树的同构是一个基于结点对应和孩子相同（左右位置可互换）的递归概念。

二、树哈希

树哈希（Tree Hash）是对树形数据结构进行哈希处理的一种方法。以下是对树哈希的详细解释：

1.定义

树哈希是一种哈希算法，它通过对树形数据结构中的每个节点进行哈希计算，并将这些哈希值组合起来，以生成整个树的唯一哈希值。这个哈希值可以作为树的“数字指纹”，用于快速比较两棵树是否相同或检测树的修改。

2.哈希过程

（1）叶节点哈希

首先，对树中的每个叶节点进行哈希计算，生成叶节点的哈希值。这些哈希值通常作为叶节点的标签或标识符。

（2）非叶节点哈希

对于非叶节点（包括中间节点和根节点），它们的哈希值是通过对其子节点的哈希值进行进一步哈希计算得到的。具体来说，可以将子节点的哈希值作为输入，应用哈希函数来生成非叶节点的哈希值。

（3）组合哈希值

在生成非叶节点的哈希值时，通常需要按照一定的顺序或规则来组合其子节点的哈希值。这可以确保哈希值的唯一性和一致性。

3.性质

（1） $\red{\texttt{唯一性}}$

对于不同的树形数据结构，即使它们包含相同的节点和边，但只要结构不同（例如节点的排列顺序不同），它们的哈希值也将不同。

（2）快速比较

通过比较两棵树的哈希值，可以快速判断它们是否相同。如果哈希值相同，则两棵树在结构上必然相同；如果哈希值不同，则两棵树在结构上必然不同。

（3）检测修改

哈希值对树的修改非常敏感。即使对树中的某个节点进行微小的修改（例如更改节点的值或添加/删除节点），也会导致整个树的哈希值发生变化。

4.应用

例如算法优化，在算法设计中，树哈希可以用于优化某些算法的性能。例如，在字符串匹配算法中，可以使用树哈希来快速比较两个字符串的子串是否相同。

5.示例

假设有以下树形数据结构：

我们可以按照以下步骤计算整个树的哈希值：

（1）first step

计算叶节点 $D$ 、 $E$ 、 $C$ 的哈希值，分别记为 $H (D)$ 、 $H (E)$ 、 $H (C)$ 。

（2）second step

计算非叶节点 $B$ 的哈希值，可以使用 $H (B) = H a s h (H (D) + H (E))$ （这里的“ $+$ ”表示哈希值的组合方式，可以是拼接、异或等操作）。

（3）third step

计算根节点 $A$ 的哈希值，可以使用 $H (A) = H a s h (H (B) + H (C))$ 。

最终，整个树的哈希值就是 $H (A)$ 。

综上所述，树哈希是一种强大的工具，可以用于快速比较和检测树形数据结构的完整性和一致性。

【数据结构】树哈希

目录一、树的同构1. 定义2. 具体理解(1) 结点对应(2) 孩子相同(3) 递归性质 3. 示例二、树哈希1.定义2.哈希过程（1）叶节点哈希（2）非叶节点哈希（3）组合哈希值 3.性质（1） 唯一性 \re…...

编程日记 2025/5/9 14:11:49

UE5 蓝图学习计划 - Day 12：存储与加载

在游戏开发中，存储（Save）与加载（Load） 系统至关重要，玩家需要能够保存游戏进度、角色状态、道具数据等信息，并在下次启动游戏时恢复它们。UE5 提供了 SaveGame 蓝图类，帮助开发者快速…...

编程日记 2025/5/9 13:38:08

18爬虫:关于playwright相关内容的学习

1.如何在python中安装playwright 打开pycharm，进入终端，输入如下的2个命令行代码即可自动完成playwright的安装 pip install playwright ——》在python中安装playwright第三方模块 playwright install ——》安装playwright所需的工具插件和所支持的…...

编程日记 2025/5/9 14:06:04

图解BWT(Burrows-Wheeler Transform) 算法

Burrows-Wheeler Transform (BWT) 是一种数据转换算法, 主要用于数据压缩领域. 它由 Michael Burrows 和 David Wheeler 在 1994 年提出, 广泛应用于无损数据压缩算法(如 bzip2)中. BWT 的核心思想是通过重新排列输入数据, 使得相同的字符更容易聚集在一起, 从而提高后续压缩算…...

编程日记 2025/5/6 17:20:21

CMake轻松实现把编译生成文件分类输出到指定路径，同时又拷贝一份到别的指定路径（Window/Linux通用）

使用CMake管理的C项目工程你是否有以下需求： 1.项目编译时将生成的文件分类自动输出到指定位置； 2.除了上面输出到指定位置以外，还要拷贝一份到指定位置（包含头文件，配置文件，第三方依赖库文件等&#xf…...

编程日记 2025/5/5 3:18:19

黑马程序员视频地址： AJAX-Day03-01.XMLHttpRequest_基本使用https://www.bilibili.com/video/BV1MN411y7pw?vd_source0a2d366696f87e241adc64419bf12cab&spm_id_from333.788.videopod.episodes&p33https://www.bilibili.com/video/BV1MN411y7pw?vd_sour…...

编程日记 2025/5/4 7:36:08

C32.【C++ Cont】静态实现双向链表及STL库的list

目录 1.知识回顾 2.静态实现演示图 3.静态实现代码 1.初始双向链表 2.头插 3.遍历链表 4.查找某个值 4.任意位置之后插入元素 5.任意位置之前插入元素 6.删除任意位置的元素 4.STL库的list 1.知识回顾 96.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删 97.【C…...

编程日记 2025/5/3 23:20:09

【Elasticsearch】terms聚合误差问题

Elasticsearch中的聚合查询在某些情况下确实可能存在误差，尤其是在处理分布式数据和大量唯一值时。这种误差主要来源于以下几个方面： 1.分片数据的局部性 Elasticsearch的索引通常被分成多个分片，每个分片独立地计算聚合结果。由于数据在分…...

编程日记 2025/4/25 11:37:58

2-kafka服务端之延时操作实现原理

文章目录背景案例延时生产实现原理延时拉取实现原理总结背景上篇我们说到了kafka时间轮是延时操作内部实现的重要数据结构，这篇我们来说下kafka内部的延时操作实现原理。这里我们以延时生产和延时拉取为例说明延时操作的实现原理。案例延时生产我们知道如…...

编程日记 2025/5/6 23:14:35

UE求职Demo开发日志#22 显示人物信息，完善装备的穿脱

1 创建一个人物信息显示的面板，方便测试简单弄一下： UpdateInfo函数： 就是获取ASC后用属性更新，就不细看了 2 实现思路在操作目标为装备栏，或者操作起点为装备栏时，交换前先判断能否交换（只…...

编程日记 2025/5/4 13:29:56

【DeepSeek论文精读】6. DeepSeek R1：通过强化学习激发大语言模型的推理能力

欢迎关注[【youcans的AGI学习笔记】](https://blog.csdn.net/youcans/category_12244543.html）原创作品【DeepSeek论文精读】1. 从 DeepSeek LLM 到 DeepSeek R1 【DeepSeek论文精读】2. DeepSeek LLM：以长期主义扩展开源语言模型【DeepSeek论文精读】…...

编程日记 2025/5/4 11:22:32

顺丰大数据开发面试题及参考答案

Flink 的提交过程是怎样的？ Flink 的提交过程通常包含以下步骤：代码编写与打包：开发人员首先使用 Flink 提供的 API 编写数据处理逻辑，包括定义数据源、转换操作和数据 sink 等。完成代码编写后，将项目打包成可执行的 JAR 文件，其中包含了所有依赖的库和资源。选择提交方…...

编程日记 2025/5/5 6:37:11

C# 函数多个返回值

有时候需要从C#函数中返回多个返回值，而且返回值的类型又不一样，这个时候又不能用数组或者list。其实C#函数是支持多个不同类型的返回值的，请参看下面的code. //多返回值函数定义 (string name, int age) GetNameAge(int id) {return (&qu…...

编程日记 2025/5/9 14:06:05

Deepseek 接入Word处理对话框（隐藏密钥）

硅基流动邀请码：1zNe93Cp 邀请链接：网页链接亲测deepseek接入word，自由调用对话，看截图有兴趣的复用代码（当然也可以自己向deepseek提问，帮助你完成接入，但是提问逻辑不一样给出的答案是千差万…...

编程日记 2025/5/9 5:56:06

RabbitMQ深度探索：简单实现 MQ

基于多线程队列实现 MQ ： 实现类： public class ThreadMQ {private static LinkedBlockingDeque<JSONObject> broker new LinkedBlockingDeque<JSONObject>();public static void main(String[] args) {//创建生产者线程Thread producer n…...

编程日记 2025/5/1 16:59:37

Baklib赋能数字内容体验个性化推荐提升用户体验的未来之路

内容概要随着数字化时代的不断发展，用户对内容消费的需求日益多样化，个性化推荐成为提升用户体验的重要手段。Baklib以其先进的技术手段，在数字内容领域内积极推动个性化推荐的实施，从而满足用户在信息获取和内容消费中的独特需…...

编程日记 2025/5/1 17:01:44

使用 TensorRT 和 Python 实现高性能图像推理服务器

在现代深度学习和计算机视觉应用中，高性能推理是关键。本文将介绍如何使用 TensorRT 和 Python 构建一个高性能的图像推理服务器。该服务器能够接收客户端发送的图像数据，使用 TensorRT 进行推理，并将结果返回给客户端。 1. 概述 1.1 项目目…...

编程日记 2025/5/6 21:54:52

[MySQL#1] database概述常见的操作指令 MySQL架构存储引擎

#1024程序员节｜征文# 目录一. 数据库概念 0.连接服务器 1. 什么是数据库口语中的数据库为什么数据不直接以文件形式存储，而需要使用数据库呢？ 总结二. ??基础操作三. 主流数据库四. 基础知识服务器，数据库&…...

编程日记 2025/5/5 5:03:46

WebAssembly：前后端开发的未来利器

引言在互联网的世界里，前端和后端开发一直是两块重要的领域。而 JavaScript 长期以来是前端的霸主，后端则有各种语言诸如 Java、Python、Node.js、Go 等等。然而，近年来一个名为 WebAssembly (Wasm) 的技术正在逐渐改变这一格局。它的高性能…...

编程日记 2025/5/7 9:51:52

Spring Task之Cron表达式

🌟 Spring Task高能预警：你以为的Cron表达式可能都是错的！【附实战避坑指南】开篇暴击：为什么你的定时任务总在凌晨3点翻车？ “明明设置了0 0 2 * * ?，为什么任务每天凌晨3点执行？” —— 来…...

编程日记 2025/4/30 21:05:11

deepseek API 调用-python

【1】创建 API keys 【2】安装openai SDK pip3 install openai 【3】代码： https://download.csdn.net/download/notfindjob/90343352...

编程日记 2025/5/1 17:00:56

数字滤波器的分类

数字滤波器可以根据不同的标准进行分类，以下是几种常见的分类方式： 1. 按实现结构分类 FIR滤波器（有限脉冲响应滤波器） - 特点：系统的脉冲响应在有限时间内衰减到零。 - 优点：线性相位特性（保…...

编程日记 2025/5/5 17:26:49

iOS 老项目适配 #Preview 预览功能

前言 iOS 开发者最憋屈的就是UI 布局慢，一直以来没有实时预览功能，虽然swiftUI 早就支持了，但是目前主流还是使用UIKit在布局，iOS 17 苹果推出了 #Preview 可以支持UIKit 实时预览，但是仅仅是 iOS 17，老项目怎么办呢？于是就有了这篇老项目适配 #Preview 预览的文章，…...

编程日记 2025/5/5 18:00:00

高等代数笔记—域与一元多项式

域与环数域 F F F：至少包含两个元素且对加减乘除运算封闭的复数集合 F F F，其中作除运算时除数不为0。封闭：集合 F F F中的两个元素作某一运算的结果仍属于集合 F F F，则称 F F F对该运算封闭。 Q , R , C \mathbb{Q}, \mathbb…...

编程日记 2025/5/9 11:32:40

【C语言设计模式学习笔记1】面向接口编程/简单工厂模式/多态

面向接口编程可以提供更高级的抽象，实现的时候，外部不需要知道内部的具体实现，最简单的是使用简单工厂模式来进行实现，比如一个Sensor具有多种表示形式，这时候可以在给Sensor结构体添加一个enum类型的type，…...

编程日记 2025/5/3 14:34:18

2.Python基础知识：注释、变量以及数据类型、标识符和关键字、输入函数、输出函数、运算符、程序类型转换

1. 注释注释是用来解释代码，增强代码可读性的部分。在 Python 中，注释分为单行注释和多行注释。单行注释：以 # 开头，后面的内容都被视为注释。 # 这是一个单行注释 print("Hello, World!") # 输出 "Hello, Wor…...

编程日记 2025/5/7 4:48:31

介绍10个比较优秀好用的Qt相关的开源库

记录下比较好用的一些开源库 1. Qt中的日志库“log4qt” log4qt 是一个基于 Apache Log4j 设计理念的 Qt 日志记录库，它为 Qt 应用程序提供了强大而灵活的日志记录功能。Log4j 是 Java 领域广泛使用的日志框架，log4qt 借鉴了其优秀的设计思想&#xff…...

编程日记 2025/5/4 16:00:15

利用Muduo库实现简单且健壮的Echo服务器

一、muduo网络库主要提供了两个类： TcpServer：用于编写服务器程序 TcpClient：用于编写客户端程序二、三个重要的链接库： libmuduo_net、libmuduo_base、libpthread 三、muduo库底层就是epoll线程池，其好处是…...

编程日记 2025/5/9 13:26:36

渗透测试之文件包含漏洞超详细的文件包含漏洞文章

目录说明通常分为两种类型： 本地文件包含典型的攻击方式1： 影响： 典型的攻击方式2： 包含路径解释： 日志包含漏洞： 操作原理包含漏洞读取文件文件包含漏洞远程代码执行漏洞: 远程文件包含…...

编程日记 2025/4/30 1:53:41

高性能：DeepSeek-V3 inference 推理时反量化实现 fp8_cast_bf16

FP8 (8 bits) & FP16 (16 bits) FP8 和 BF16 都是浮点数格式（floating-point formats），float通过科学计数法表示数据，float [符号位指数位系数位] FP8 (8 bits)：SEEEMMMMFP16 (16 bits)：SEEEEEMMMMM…...

编程日记 2025/5/5 17:54:37

kakailio官网推荐的安装流程ubuntu 22.04

https://kamailio.org/docs/tutorials/6.0.x/kamailio-install-guide-git/ # 非必须项 wget -O- https://deb.kamailio.org/kamailiodebkey.gpg | gpg --dearmor | sudo tee /usr/share/keyrings/kamailio.gpg在/etc/apt/sources.list文件追加以下内容 deb [signed-by/usr/sh…...

编程日记 2025/5/4 17:56:20

能否通过蓝牙建立TCP/IP连接来传输数据

前言： 最近在做一个项目时，产生了一个疑问：能否通过蓝牙建立TCP/IP连接来传输数据查阅了一些文章，可以得出结论：不行下面是我截取的两篇个人认可的文章的回答： 文章一： 蓝牙是一种短距离无…...

编程日记 2025/5/8 6:32:44

git基础使用--1--版本控制的基本概念

文章目录 git基础使用--1--版本控制的基本概念1.版本控制的需求背景，即为啥需要版本控制2. 集中式版本控制SVN3. 分布式版本控制 Git4. SVN和Git的比较 git基础使用–1–版本控制的基本概念 1.版本控制的需求背景，即为啥需要版本控制先说啥叫版本&…...

编程日记 2025/5/6 22:58:54

高端入门：Ollama 本地高效部署DeepSeek模型深度搜索解决方案

目录一、Ollama 介绍二、Ollama下载 2.1 官网下载 2.2 GitHub下载三、模型库四、Ollmal 使用 4.1 模型运行（下载） 4.2 模型提问五、Ollama 常用命令相关推荐一、Ollama 介绍 Ollama是一个专为在本地机器上便捷部署和运行大型语言模型&…...

编程日记 2025/5/5 1:56:47

高级java每日一道面试题-2025年01月30日-框架篇[SpringBoot篇]-如何理解 Spring Boot 配置加载顺序 ?

如果有遗漏,评论区告诉我进行补充面试官: 如何理解 Spring Boot 配置加载顺序 ? 我回答: 在 Java 高级面试中讨论 Spring Boot 配置加载顺序时，理解其机制对于有效管理和调试应用程序配置至关重要。Spring Boot 通过一系列预定义的规则来确定如何加载和覆盖配置…...

编程日记 2025/5/2 0:21:37

代码随想录day06

242.有效的字母异位词刚学哈希表想着使用unordered_set来实现，结果无法通过，原因是对字母异位词理解有问题，字母异位词是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。对字母出现的次数有要求&am…...

编程日记 2025/5/6 7:51:29

C#常用744单词

1.visual 可见的 2.studio 工作室 3.dot 点 4.net 网 5.harp 尖端的，锋利的。 6.amework 骨架，构架，框架 7.beta 测试版，试用版 8.XML（全称：eXtensible Markup Language&#xff09…...

编程日记 2025/5/4 12:42:08

14.PPT：中国注册税务师协会宣传【26】

目录 NO12 NO3/4/5 NO678 【文本框水平/垂直居中】【文本框内容水平/垂直居中】 NO12 坑：注意❗Word文档的PPt素材.docx的标题大纲是混乱的，虽然他设置了，所以我们需要重新设置设计→主题视图→幻灯片母版→删除版式插入logo NO3/4…...

编程日记 2025/5/7 5:42:42

Python大数据可视化：基于Python的王者荣耀战队的数据分析系统设计与实现_flask+hadoop+spider

开发语言：Python框架：flaskPython版本：python3.7.7数据库：mysql 5.7数据库工具：Navicat11开发软件：PyCharm 系统展示管理员登录管理员功能界面比赛信息管理看板展示系统管理摘要本文使用Python与…...

编程日记 2025/5/4 0:43:06

简单3步部署本地国产大模型DeepSeek大模型

简单3步部署本地国产大模型DeepSeek大模型 DeepSeek是最近非常火的开源大模型，国产大模型 DeepSeek 凭借其优异的性能和对硬件资源的友好性，受到了众多开发者的关注。无奈，在使用时候deepseek总是提示服务器繁忙，请稍后再试。 …...

编程日记 2025/5/5 3:18:05

Redis常见数据类型与编码方式

⭐️前言⭐️ 本小节围绕Redis中常见的数据类型与编码方式展开。 🍉欢迎点赞 👍 收藏 ⭐留言评论 🍉博主将持续更新学习记录收获，友友们有任何问题可以在评论区留言 🍉博客中涉及源码及博主日常练习代码均已上传GitHu…...

编程日记 2025/5/8 17:25:44

利用matlab寻找矩阵中最大值及其位置

目录一、问题描述1.1 max函数用法1.2 MATLAB中 : : :的作用1.3 ind2sub函数用法二、实现方法2.1 方法一：max和find2.2 方法二：max和ind2sub2.3 方法对比三、参考文献一、问题描述 matlab中求最大值可使用函数max，对于一维向量&#xff0…...

编程日记 2025/5/6 12:13:38

解锁云电脑爽玩TGA游戏，ToDesk、海马云等多款云电脑游戏横测

作为一名游戏爱好者，我深入研究了云电脑技术在游戏娱乐中的应用。通过对比传统游戏机与云电脑的成本效益，我发现云电脑以其低成本和灵活性脱颖而出。我以自身为例，分析了云电脑如何满足对游戏体验的高要求。在测评中，我选择了ToDe…...

编程日记 2025/5/7 6:27:17

蓝桥杯思维训练(五)

文章目录子集II1191.K次串联后最大子数组之和子集II 子集II 思路分析： 求解子集的问题的关键就是，通过递归与回溯，我们就是得确定以某个元素开始的子集，对于这个题目来说，比较麻烦的一点就是，存在重复的…...

编程日记 2025/5/7 8:04:13

kaggle视频行为分析1st and Future - Player Contact Detection

这次比赛的目标是检测美式橄榄球NFL比赛中球员经历的外部接触。您将使用视频和球员追踪数据来识别发生接触的时刻，以帮助提高球员的安全。两种接触，一种是人与人的，另一种是人与地面，不包括脚底和地面的，跟我之前做的这…...

编程日记 2025/5/9 13:26:35

2025 CCF BDCI｜“基于TPU平台的OCR模型性能优化”一等奖作品

2024年12月，中国计算机学会在海南博鳌成功举办了第十二届CCF大数据与计算智能大赛（简称2024 CCF BDCI）。本届比赛的算能赛道吸引了1748名选手报名，经过激烈角逐，北京航空航天大学的“常务副SOTA”团队脱颖而出&#xf…...

编程日记 2025/5/8 21:54:58

结合深度学习、自然语言处理（NLP）与多准则决策的三阶段技术框架，旨在实现从消费者情感分析到个性化决策

针对电商个性化推荐场景的集成机器学习和稳健优化三阶段方案。第一阶段:在线评论数据处理，利用深度学习和自然语言处理技术进行特征挖掘，进而进行消费者情感分析，得到消费者偏好在第一阶段，我们主要关注如何通过深度学习和自然语…...

编程日记 2025/5/7 17:34:46

Linux系统安装Nginx详解（适用于CentOS 7）

目录 1. 更新系统包 2. 安装EPEL仓库 3. 安装Nginx 4. 启动Nginx服务 5. 设置Nginx开机自启 6. 检查Nginx状态 7. 配置防火墙 8. 访问Nginx默认页面 9. 配置Nginx（可选） 10. 重启Nginx 解决步骤 1. 检查系统版本 2. 移除错误的 Nginx 仓库 …...

编程日记 2025/5/9 13:11:55

Qt常用控件输入类控件

文章目录 1.QLineEdit1.1 常用属性1.2 常用信号1.3 例子1，录入用户信息1.4 例子2，正则验证手机号1.5 例子3，验证输入的密码1.6 例子4，显示密码 2. QTextEdit2.1 常用属性2.2 常用信号2.3 例子1，获取输入框的内容2.4 例…...

编程日记 2025/5/6 20:26:00

[LeetCode]全排列I，II

全排列I 给定一个不含重复数字的整数数组 nums ，返回其所有可能的全排列。可以按任意顺序返回答案。示例 1： 输入：nums [1,2,3] 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2： 输入&#xff1…...

编程日记 2025/5/4 10:54:08

目录