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

数据结构【DS】B树

m阶B树的核心特性:

Q:根节点的子树数范围是多少?关键字数的范围是多少?

A:根节点的子树数∈[2, m],关键字数∈[1, m-1]。

Q:其他结点的子树数范围是多少?关键字数范围是多少?

Q:对任一结点,其所有子树高度有什么特点?

  • 都相同

Q:关键字的值的大小关系是什么样的?

  • 关键字的值:类比二叉查找树:左<中<右

 

Q:含 n 个关键字的 m 阶 B 树,最小高度、最大高度是多少?

  • 最小高度:
  • 最大高度:
    • 让各层的分叉尽可能的少

Q:对于高度为 2 的 5 阶 B 树所含关键字的个数最少是多少?

A:根结点只有达到 5 个关键字时才能产生分裂, 成为高度为 2 的 B 树 ,因此高度为 2 的 5 阶 B 树所含关键字的个数最少是 5 。

B树的插入和删除

插入

  • 通过“查找”确定插入位置(一定是在终端结点插入)
  • 若插入后结点关键字个数未超过上限,则无需做其他处理
  • 若插入后关键字个数超过上限,则需要将当前结点的中间元素放到父节点中,当前结点分裂为两个部分;
  • 该操作会导致父节点关键字个数+1,若父节点关键字个数也超过了上限,则需要再向上分裂;根节点的分裂会导致B树高度+1。

Q:B树裂开的时候从哪开始裂?

删除

  • 非终端结
    • 用其直接前驱或直接后继替代其位置,转化为对“终端结点”的删除点关键字.
    • 直接前驱:当前关键字左边指针所指子树中最右下的元素
    • 直接后继:当前关键字右边指针所指子树中最左下的元素
    • 删除后结点关键字个数未低于下限,无需任何处理
  • 终端结点
    • 右兄弟够借,则用当前结点的后继、后继的后继依次顶替空缺
    • 左兄弟够借,则用当前结点的前驱、前驱的前驱依次顶替空缺
    • 左(右)兄弟都不够借,则需要与父结点内的关键字、左(右)兄弟进行合并。合并后导致父节点关键字数量-1,可能需要继续合并。

相关文章:

数据结构【DS】B树

m阶B树的核心特性: Q&#xff1a;根节点的子树数范围是多少&#xff1f;关键字数的范围是多少&#xff1f; A&#xff1a;根节点的子树数∈[2, m],关键字数∈[1, m-1]。 Q&#xff1a;其他结点的子树数范围是多少&#xff1f;关键字数范围是多少&#xff1f; Q&#xff1a;对任…...

Chatgpt网页版根据关键词自动批量写原创文章软件【可多开自动登录切换gpt账号】

Chatgpt网页版根据关键词自动批量写原创文章软件介绍&#xff1a; 1、需要放入GPT账号和密码放入在账号库.txt里&#xff0c;可以放入多组账号密码&#xff0c;账号切换轮流使用。 2、可以自定义回答指令&#xff0c;也可多个回答指令随机切换。 3、可以给关键词加双标题&…...

研发效能认证学员作品:快速进行持续集成应用实践丨IDCF

作者&#xff1a;赖嘉明 研发效能&#xff08;DevOps&#xff09;工程师认证学员 随着数字化转型的推进及市场竞争的加剧&#xff0c;越来越多的企业也意识到持续集成的重要性。 而持续集成作为一种先进的软件开发实践和工具链&#xff0c;可以帮助企业实现自动化构建、集成和…...

中文编程开发语言工具系统化教程零基础入门篇和初级1专辑课程已经上线,可以进入轻松学编程

中文编程开发语言工具系统化教程零基础入门篇和初级1专辑课程已经上线&#xff0c;可以进入轻松学编程 学习编程捷径&#xff1a;&#xff08;不论是正在学习编程的大学生&#xff0c;还是IT人士或者是编程爱好者&#xff0c;在学习编程的过程中用正确的学习方法 可以达到事半…...

2024年最新水果音乐制作软件FL Studio21需要多少钱呢?

水果&#xff0c;全称Fruity Loop Studio&#xff0c;简称FL Studio。是一款全能的音乐制作软件&#xff0c;经过二十多年的演化更迭&#xff0c;其各项功能非常的先进。其开创性的Pat\song模式&#xff0c;也为初学者的学习提供了便利。那么水果音乐制作软件FL Studio21需要多…...

当生成式AI遇到业务流程管理,大语言模型正在变革BPM

生成式AI对各领域有很大影响&#xff0c;一个方面在于它改变了很多固有业务的工作流。 工作流&#xff08;Workflow&#xff09;是业务流程的一种实现方式&#xff0c;一个业务流程往往包含多个工作流范式以及相关的数据、组织和系统。 因此&#xff0c;提及工作流必然离不开业…...

Kotlin数据流概览

文章目录 一 什么是数据流二 创建数据流三 修改数据流四 从数据流中进行收集五 数据流捕获异常六 在不同 CoroutineContext 中执行七 Jetpack 库中的数据流八 将基于回调的 API 转换为数据流 一 什么是数据流 数据流以协程为基础构建&#xff0c;可提供多个值。从概念上来讲&a…...

npm : 无法加载文件 C:\Program Files\nodejs\npm.ps1,因为在此系统上禁止运行脚本。

1、在vscode终端执行 get-ExecutionPolicy &#xff0c;显示Restricted&#xff0c;说明状态是禁止的。 2、更改状态: set-ExecutionPolicy RemoteSigned 出现需要管理员权限提示&#xff0c;可选择执行 Set-ExecutionPolicy -Scope CurrentUser 出现的ExecutionPolicy参数后输…...

036-第三代软件开发-系统时间设置

第三代软件开发-系统时间设置 文章目录 第三代软件开发-系统时间设置项目介绍系统时间设置演示效果QML 实现小伙伴自创 TumblerQt 家 Tumbler C 端实现 总结一下 关键字&#xff1a; Qt、 Qml、 Time、 时间、 系统 项目介绍 欢迎来到我们的 QML & C 项目&#xff01;…...

C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2

下面介绍四道题目和解法 1.杨氏矩阵 算法&#xff1a;右上角计算 题目&#xff1a;有一个数字矩阵&#xff0c;矩阵的每行从左到右是递增的&#xff0c;矩阵从上到下是递增的&#xff0c;请编写程序在这样的矩阵中查找某个数字是否存在。 要求&#xff1a;时间复杂度小于O(N…...

PX4天大bug,上电反复重启,连不上QGC!

一、Debug与Bug 由于自己写的代码CPU占用率过高&#xff0c;解锁报错 CPU load too high!无法解锁。 于是把 COM_CPU_MAX 从默认的 90% 变为 99%&#xff08;千万别这样搞&#xff0c;这是bug&#xff0c;除非想玩&#xff01;&#xff09;。 然后重启&#xff0c;飞机就反…...

归并排序——

之前我们学习过把两个有序数组合并再一起后任然有序&#xff0c;就叫归并&#xff1b; 那么&#xff0c;排序是否也可以把一个要排序的数组分割成两个有序的数组&#xff0c;然后归并&#xff0c;之后再拷贝回原数组&#xff0c;就实现了排序 但是怎么才能控制分割成的数组是有…...

阿里云企业邮箱基于Spring Boot快速实现发送邮件功能

邮件在项目中经常会被用到&#xff0c;比如用邮件发送通知。比如&#xff0c;通过邮件注册、认证、找回密码、系统报警通知、报表信息等。本篇文章带大家通过SpringBoot快速实现一个发送邮件的功能。 邮件协议 下面先简单了解一下常见的邮件协议。常用的电子邮件协议有SMTP、…...

大数据Doris(十三):创建用户和创建数据库并赋予权限

文章目录 创建用户和创建数据库并赋予权限 一、创建用户...

【Unity小技巧】可靠的相机抖动及如何同时处理多个震动

文章目录 每篇一句前言安装虚拟相机虚拟相机震动测试代码控制震动清除震动控制震动的幅度和时间 两个不同的强弱震动同时发生源码完结 每篇一句 围在城里的人想逃出来&#xff0c;站在城外的人想冲进去&#xff0c;婚姻也罢&#xff0c;事业也罢&#xff0c;人生的欲望大都如此…...

Megatron-LM GPT 源码分析(四) Virtual Pipeline Parallel分析

引言 本文接着上一篇【Megatron-LM GPT 源码分析&#xff08;三&#xff09; Pipeline Parallel分析】&#xff0c;基于开源代码 GitHub - NVIDIA/Megatron-LM: Ongoing research training transformer models at scale &#xff0c;通过GPT的模型运行示例&#xff0c;从三个维…...

IOC课程整理-8 Spring Bean作用域

1 Spring Bean作用域 2" singleton " Bean作用域 3" prototype " Bean作用域 • 注意事项 • Spring 容器没有办法管理 prototype Bean 的完整生命周期&#xff0c;也没有办法记录实例的存在。销毁回调方法将不会执行&#xff0c;可以利用 BeanPostProces…...

本地websocket服务端暴露至公网访问【内网穿透】

本地websocket服务端暴露至公网访问【cpolar内网穿透】 文章目录 本地websocket服务端暴露至公网访问【cpolar内网穿透】1. Java 服务端demo环境2. 在pom文件引入第三包封装的netty框架maven坐标3. 创建服务端,以接口模式调用,方便外部调用4. 启动服务,出现以下信息表示启动成功…...

C/C++跨平台构建工具CMake-----灵活添加库并实现开发和生产环境的分离

目录 1.概述2.创建项目3 配置运行项目3.1 编写开平方根示例代码3.2 编写CMake构建脚本 4.使用子模块实现求平方根的功能4.1 在子模块中实现两种求平方根的方法4.2 构建Mathfunctions子模块4.3 在根目录引用子模块的功能4.3.1 编写构建脚本4.3.2 编写C代码使用MathFunctions库中…...

javascript判断对象中是否存在某个字段

1. in 如果指定的属性在指定的对象或其原型链中&#xff0c;则 in 运算符返回 true。 const car { make: Honda, model: Accord, year: 1998 };console.log(make in car); // truedelete car.make; if (make in car false) {car.make Suzuki; }console.log(car.make); //…...

KubeSphere 容器平台高可用:环境搭建与可视化操作指南

Linux_k8s篇 欢迎来到Linux的世界&#xff0c;看笔记好好学多敲多打&#xff0c;每个人都是大神&#xff01; 题目&#xff1a;KubeSphere 容器平台高可用&#xff1a;环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...

UE5 学习系列(二)用户操作界面及介绍

这篇博客是 UE5 学习系列博客的第二篇&#xff0c;在第一篇的基础上展开这篇内容。博客参考的 B 站视频资料和第一篇的链接如下&#xff1a; 【Note】&#xff1a;如果你已经完成安装等操作&#xff0c;可以只执行第一篇博客中 2. 新建一个空白游戏项目 章节操作&#xff0c;重…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

Android第十三次面试总结(四大 组件基础)

Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成&#xff0c;用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机&#xff1a; ​onCreate()​​ ​调用时机​&#xff1a;Activity 首次创建时调用。​…...

C++使用 new 来创建动态数组

问题&#xff1a; 不能使用变量定义数组大小 原因&#xff1a; 这是因为数组在内存中是连续存储的&#xff0c;编译器需要在编译阶段就确定数组的大小&#xff0c;以便正确地分配内存空间。如果允许使用变量来定义数组的大小&#xff0c;那么编译器就无法在编译时确定数组的大…...

MySQL 知识小结(一)

一、my.cnf配置详解 我们知道安装MySQL有两种方式来安装咱们的MySQL数据库&#xff0c;分别是二进制安装编译数据库或者使用三方yum来进行安装,第三方yum的安装相对于二进制压缩包的安装更快捷&#xff0c;但是文件存放起来数据比较冗余&#xff0c;用二进制能够更好管理咱们M…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

【LeetCode】3309. 连接二进制表示可形成的最大数值(递归|回溯|位运算)

LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 题目描述解题思路Java代码 题目描述 题目链接&#xff1a;LeetCode 3309. 连接二进制表示可形成的最大数值&#xff08;中等&#xff09; 给你一个长度为 3 的整数数组 nums。 现以某种顺序 连接…...