非线性数据结构之数
一、基本概念
1. 二叉树的节点与深度
- 节点:二叉树的基本组成单位,每个节点包含一个数据值、一个左子节点和一个右子节点。
- 树的深度(Height):指树的根节点到叶子节点的最长路径所包含的边数。
2. 二叉树的类型
- 叶节点:没有子节点的节点。
- 内部节点:具有子节点的节点。
二、二叉树的种类
1. 完全二叉树(Complete Binary Tree)
定义:完全二叉树的所有层都被完全填满,除了最后一层的节点必须自左向右排列。
特点:
- 通常使用数组实现,具有简洁的内存结构,且方便通过索引访问。
- 节点索引公式:若根节点为第 0 个元素,则节点 i 的左子节点索引为 2i + 1,右子节点为 2i + 2,父节点为 (i-1) / 2。
优缺点:
- 优点:提高了存储和遍历的效率,常用于实现堆。
- 缺点:对树的结构有严格要求,插入和删除操作需要维护完全性。
应用:常见于堆排序、优先队列实现等。
2. 满二叉树(Full Binary Tree)
定义:每个节点都有两个子节点,且所有叶节点的深度相同。
特点:
- 所有层都被完全填满,节点数达到最大。
- 满二叉树的节点数 n 与深度 h 满足公式:n = 2^(h+1) - 1。
优缺点:
- 优点:结构紧凑,便于平衡和遍历。
- 缺点:插入和删除操作较为不便,需维持每层的完整性。
应用:常用于存储静态数据,或需要完全对称的数据结构中。
3. 二叉搜索树(Binary Search Tree, BST)
定义:BST 是一种特殊的二叉树,满足以下性质:
- 若左子树不为空,则左子树上所有节点的值均小于根节点的值。
- 若右子树不为空,则右子树上所有节点的值均大于根节点的值。
- 左右子树均为二叉搜索树。
特点:
- 支持平均 O(log n) 的插入、删除和查找操作。
- 中序遍历 BST 可获得有序序列。
优缺点:
- 优点:查找和修改操作效率高,适合动态数据集。
- 缺点:在极端情况下(如插入数据有序),树可能会退化为链表,导致性能下降到 O(n)。
应用:用于数据库索引、文件系统、字典等。
示例代码(Java):
class TreeNode {int value;TreeNode left;TreeNode right;TreeNode(int value) {this.value = value;}
}class BinarySearchTree {TreeNode root;// 插入public void insert(int value) {root = insertRecursive(root, value);}private TreeNode insertRecursive(TreeNode node, int value) {if (node == null) {return new TreeNode(value);}if (value < node.value) {node.left = insertRecursive(node.left, value);} else if (value > node.value) {node.right = insertRecursive(node.right, value);}return node;}// 查找public boolean search(int value) {return searchRecursive(root, value);}private boolean searchRecursive(TreeNode node, int value) {if (node == null) {return false;}if (value == node.value) {return true;} return value < node.value ? searchRecursive(node.left, value) : searchRecursive(node.right, value);}
}
三、平衡树
定义
平衡树是一种保持树结构平衡的二叉树,通常限制了节点的高度差异,使得查找、插入和删除操作保持在 O(log n) 的时间复杂度。
特点:平衡树通常通过旋转操作来调整子树的高度,从而防止极端情况导致的退化。
1. AVL 树
定义:AVL 树是一种自平衡二叉搜索树,具有以下性质:
- 每个节点的左右子树高度差最多为 1。
特点:
- 通过“旋转”操作(单旋、双旋)在插入和删除节点后重新平衡树。
- 查找、插入、删除操作复杂度均为 O(log n)。
优缺点:
- 优点:严格平衡,查找效率较高。
- 缺点:旋转操作较多,插入和删除效率较低。
应用:适用于查找频繁、插入删除较少的场景,如数据库索引。
2. 红黑树(Red-Black Tree)
定义:红黑树是一种二叉搜索树,具有以下性质:
- 节点为红色或黑色。
- 根节点为黑色。
- 红节点的子节点必须为黑色(红节点不能相邻)。
- 从根节点到叶节点的每条路径都包含相同数目的黑节点。
特点:
- 通过颜色和旋转操作来维持平衡。
- 查找、插入、删除操作平均时间复杂度为 O(log n)。
优缺点:
- 优点:插入和删除效率高,适合频繁修改的数据。
- 缺点:实现复杂。
应用:常见于 Java 的 TreeMap、C++ 的 map,适用于需要快速插入和删除的应用。
3. Splay 树
定义:Splay 树是一种自调整二叉搜索树,最近访问的节点将旋转至根节点。这样更常用的元素将接近根节点,减少平均查找时间。
特点:
- 最近使用的数据靠近根节点,提高局部访问效率。
- 每次查找、插入或删除操作都会将目标节点旋转至根节点。
优缺点:
- 优点:适合高频访问的数据。
- 缺点:单次操作复杂度较高,不适合随机访问。
应用:缓存、文件系统等需要频繁访问某些节点的数据结构。
4. 比较总结
| 树种类 | 平衡方式 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|
| AVL 树 | 左右子树高度差平衡 | 查找效率高 | 插入、删除操作复杂 | 查找频繁,变动少的数据集 |
| 红黑树 | 颜色与旋转 | 插入、删除效率高 | 实现复杂 | Java 的 TreeMap、Linux VFS |
| Splay 树 | 自调整,最近访问至根 | 适合频繁访问的数据结构 | 随机访问不高效 | 缓存、需要局部访问的系统 |
这些平衡树结构适用于不同的场景,各有优缺点。在实际应用中根据需求选择适合的平衡树可以显著提高数据结构的操作效率。
相关文章:
非线性数据结构之数
一、基本概念 1. 二叉树的节点与深度 节点:二叉树的基本组成单位,每个节点包含一个数据值、一个左子节点和一个右子节点。树的深度(Height):指树的根节点到叶子节点的最长路径所包含的边数。 2. 二叉树的类型 叶节…...
个人开发三步走
一、开发准备 1.需求分析:需求是开发的起点。第一步要做的就是明确需求,具体来说就是分析目标用户、他们的需求(功能需求、性能需求、安全需求)和痛点。 2.技术选型:综合开发需求、个人能力(能熟练使用&a…...
qt QAction详解
1、概述 QAction是Qt框架中的一个抽象类,用于表示用户界面中的一个动作(action)。这些动作可以绑定到菜单项、工具栏按钮或快捷键上,提供了一种灵活的方式来处理用户交互。QAction不仅包含了动作的名称、图标、提示信息等属性&am…...
建立maven项目常见问题解决办法
从git拉的项目爆红 https://blog.csdn.net/wsdbld_/article/details/115380325 idea点击具体的类没有反应 https://www.likecs.com/show-204943934.html maven Could not find artifact com.** 无法下载原因分析 https://www.cnblogs.com/thinkingandworkinghard/p/100824…...
Windows 10 安装使用Docker踩过的坑和解决-31/10/2024
目录 环境版本 一、Docker Desktop双击启动没反应,open //./pipe/dockerDesktopLinuxEngine: The system cannot find the file specified. 二、Docker Desktop运行run命令时显示错误HTTP code 500 并且错误大意是服务器拒绝访问 三、Docker Engine stopped/启动…...
微服务之间的调用关系
从数据的流向来区分有 1.直接调用(推)A直接B的接口直接将数据推送给B; 2.间接调用(拉)A先调B,B根据A给信息再去调A拉取数据; 感觉间接调用有点多此一举!!! 直接调用的…...
Chinese Spelling Correction as Rephrasing Language Model(AAAI2024)
Chinese Spelling Correction as Rephrasing Language Model(AAAI2024) 一.概述 目前最先进的方法将CSC(Chinese Spelling Correction)作为序列标注任务,并在句子对上微调基于bert的方法。然而,我们注意到在将一个字符标注为另一个字符的过…...
DirectShow过滤器开发-写MP3音频文件过滤器(再写 写MP3)
下载本过滤器DLL 本过滤器将MP3音频流写到MP3音频文件。 过滤器信息 过滤器名称:写MP3_2 过滤器GUID:{AE46BC15-71E5-471C-8540-3B73094111EC} DLL注册函数名:DllRegisterServer 删除注册函数名:DllUnregisterServer 过滤器有1个…...
文章解读与仿真程序复现思路——电力自动化设备EI\CSCD\北大核心《基于对等架构的虚拟电厂-配电网双层电碳协同调度模型》
本专栏栏目提供文章与程序复现思路,具体已有的论文与论文源程序可翻阅本博主免费的专栏栏目《论文与完整程序》 论文与完整源程序_电网论文源程序的博客-CSDN博客https://blog.csdn.net/liang674027206/category_12531414.html 电网论文源程序-CSDN博客电网论文源…...
大数据-204 数据挖掘 机器学习理论 - 混淆矩阵 sklearn 决策树算法评价
点一下关注吧!!!非常感谢!!持续更新!!! 目前已经更新到了: Hadoop(已更完)HDFS(已更完)MapReduce(已更完&am…...
Fsm1
为了处理有时间上先后的事件,在FPGA中采用状态机的形式完成事件处理。 Mealy 状态机:输出不仅取决于当前状态,还取决于输入状态。 Moore 状态机:组合逻辑的输出只取决于当前状态,而与输入状态无关。 二段式状态机&…...
C. Gorilla and Permutation
time limit per test 2 seconds memory limit per test 256 megabytes Gorilla and Noobish_Monk found three numbers nn, mm, and kk (m<km<k). They decided to construct a permutation†† of length nn. For the permutation, Noobish_Monk came up with the …...
从0开始学python-day17-数据结构2
2.3 队列 队列(Queue),它是一种运算受限的线性表,先进先出(FIFO First In First Out) 队列是一种受限的线性结构 受限之处在于它只允许在表的前端(front)进行删除操作,而在表的后端(rear)进行插入操作 P…...
(蓝桥杯C/C++)—— 编程基础
文章目录 一、C基础格式 1.打印hello, world 2.基本数据类型 二、string 1.string简介 2.string的声明和初始化 3.string其他基本操作 (1)获取字符串长度 (2) 拼接字符串( 或 append) (3)字符串查找(find) (4)字符串替换 (5)提取子字符串…...
企业物流管理数据仓库建设的全面指南
文章目录 一、物流管理目标二、总体要求三、数据分层和数据构成(1)数据分层(2)数据构成 四、数据存储五、数据建模和数据模型(1)数据建模(2)数据模型 六、总结 在企业物流管理中&…...
数据采集-Kepware 安装证书异常处理
这里写目录标题 一、 问题描述二、原因分析三、处理方案3.1 1.执行根证书的更新3.2 安装KepServerEx 资源 一、 问题描述 在进行KepServerEx进行安装的情况下,出现了如下的报错: The installer was unable to find required root certificates ,please …...
ubuntu禁止自动更新设置
背景概述 从CentOS变更到uBuntu或多或少会遇到一些坑,今天分享一个。 在Ubuntu系统中,自动更新是一个既方便又引发争议的功能。它可以帮助用户保持系统的最新状态,但有时也会因为自动更新而导致系统不稳定或不兼容。 Ubuntu系统的自动更新主…...
Rust 力扣 - 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串
文章目录 题目描述题解思路题解代码题目链接 题目描述 题解思路 长度为k的二进制子串所有取值的集合为[0, sum(k)],其中sum(k)为1 2 4 … 1 << (k - 1) 我们只需要创建一个长度为sum(k) 1的数组 f ,其中下标为 i 的元素用来标记字符串中子串…...
C#/.NET/.NET Core技术前沿周刊 | 第 11 期(2024年10.21-10.31)
前言 C#/.NET/.NET Core技术前沿周刊,你的每周技术指南针!记录、追踪C#/.NET/.NET Core领域、生态的每周最新、最实用、最有价值的技术文章、社区动态、优质项目和学习资源等。让你时刻站在技术前沿,助力技术成长与视野拓宽。 欢迎投稿、推荐…...
unity 三维数学 ,角度 弧度计算
弧度 角度*π/180...
利用最小二乘法找圆心和半径
#include <iostream> #include <vector> #include <cmath> #include <Eigen/Dense> // 需安装Eigen库用于矩阵运算 // 定义点结构 struct Point { double x, y; Point(double x_, double y_) : x(x_), y(y_) {} }; // 最小二乘法求圆心和半径 …...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
质量体系的重要
质量体系是为确保产品、服务或过程质量满足规定要求,由相互关联的要素构成的有机整体。其核心内容可归纳为以下五个方面: 🏛️ 一、组织架构与职责 质量体系明确组织内各部门、岗位的职责与权限,形成层级清晰的管理网络…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据
微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列,以便知晓哪些列包含有价值的数据,…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
Java数值运算常见陷阱与规避方法
整数除法中的舍入问题 问题现象 当开发者预期进行浮点除法却误用整数除法时,会出现小数部分被截断的情况。典型错误模式如下: void process(int value) {double half = value / 2; // 整数除法导致截断// 使用half变量 }此时...
