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

第七章 查找 八、B树

目录

一、定义

二、B树的核心特性

1、B树各个结点的子树数和关键字数

2、子树高度

3、关键字的值

4、B树高度

三、B树的插入

四、B树的删除


一、定义

B树,又称多路平衡查找树,B树中所有结点的孩子个数的最大值称为B树的阶,通常用m表示。

一棵m阶B树或为空树,或为满足如下特性的m叉树:

1)树中每个结点至多有m棵子树,即至多含有m-1个关键字。

2)若根结点不是终端结点,则至少有两棵子树。

3)除根结点外的所有非叶结点至少有「m/2]棵子树,即至少含有「m/2]-1个关键字

4)所有的叶结点都出现在同一层次上,并且不带信息(可以视为外部结点或类似于折半查找判定树的查找失败结点,实际上这些结点不存在,指向这些结点的指针为空)。

注意:在B树中,所有子树的高度都必须相同,也就是说它们的平衡因子都为0,这样才能保证B树的查找效率。

二、B树的核心特性

1、B树各个结点的子树数和关键字数

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

其他结点的子树数∈[[m/2], m];关键字数∈[[m/2]-1, m-1]

2、子树高度

对任意结点,其所有子树高度都相同。

3、关键字的值

左<中<右

4、B树高度

含n个关键字的m叉B树,\log_{m}(n+1)<=h<=\log_{m/2}\frac{n+1}{2}+1

三、B树的插入

四、B树的删除

相关文章:

第七章 查找 八、B树

目录 一、定义 二、B树的核心特性 1、B树各个结点的子树数和关键字数 2、子树高度 3、关键字的值 4、B树高度 三、B树的插入 四、B树的删除 一、定义 B树&#xff0c;又称多路平衡查找树&#xff0c;B树中所有结点的孩子个数的最大值称为B树的阶&#xff0c;通常用m表示…...

Vue以及整合ElementUI

初始化vue项目 #vue 脚手架使用 webpack 模板初始化一个 appname 项目 vue init webpack appname启动 vue 项目 #项目的 package.json 中有 scripts&#xff0c;代表我们能运行的命令 npm start npm run dev #启动项目 npm run build&#xff1a;将项目打包项目结构 运行流程…...

免费、丰富、便捷的资源论坛——Yiove论坛,包括但不限于阿里云盘、夸克云盘、迅雷云盘等等

引言 目前资源的数量达到了60000&#xff0c;六万多的资源意味着在这里几乎可以找到任何你想要的资源。 当然&#xff0c;资源并不是论坛的全部&#xff0c;其中还包括了技术交流、福利分享、最新资讯等等。 传送门&#xff1a;YiOVE论坛 - 一个有资源有交流&#xff0c;有一…...

1.3 互联网的组成

思维导图&#xff1a; 前言&#xff1a; 我的笔记&#xff1a; #### 一、总览 - **互联网的结构**&#xff1a; - 具有全球覆盖和复杂的拓扑结构。 - 即便结构复杂&#xff0c;还是可以从工作方式上简化为两大部分&#xff1a;边缘部分和核心部分。 #### 二、边缘部分 -…...

【机器学习】熵和概率分布,图像生成中的量化评估IS与FID

详解机器学习中的熵、条件熵、相对熵、交叉熵 图像生成中常用的量化评估指标通常有Inception Score (IS)和Frchet Inception Distance (FID) Inception Score (IS) 与 Frchet Inception Distance (FID) GAN的量化评估方法——IS和FID&#xff0c;及其pytorch代码...

Vue3.0跨端Web SDK访问微信小程序云储存,文件上传路径不存在/文件受损无法显示问题(已解决)

整理需求&#xff1a; 需要vue3.0作为pc端的后台管理来连接微信小程序客户端需要Web SDK的引入&#xff0c;实现vue3.0接入云开发环境需要以云环境作为线上服务器&#xff0c;将vue3.0上传的本地文件通过云环境进入云储存&#xff0c;并将文件在云端生成云端快捷访问路径及htt…...

使用chat GPT 生成一个js 生成天数的方法

function calculateDaysDifference(targetDateString) {const currentDate new Date();const targetDate new Date(targetDateString);// 计算毫秒差异const timeDifference targetDate - currentDate;// 计算天数差异&#xff0c;如果结果为负数&#xff0c;则设置为0const…...

BUUCTF reverse wp 76 - 80

[CISCN2018]2ex 四处游走寻找关键代码 int __fastcall sub_400430(int a1, unsigned int a2, int a3) {unsigned int v3; // $v0int v4; // $v0int v5; // $v0int v6; // $v0unsigned int i; // [sp8h] [8h]unsigned int v9; // [sp8h] [8h]int v10; // [spCh] [Ch]v10 0;for…...

科技资讯|AirPods Pro基于定位控制的自适应音频功能

在接受 TechCrunch 媒体采访时&#xff0c;苹果高管 Ron Huang 和 Eric Treski 谈到了关于 AirPods Pro 自适应音频&#xff08;Adaptive Audio&#xff09;功能的轶事&#xff0c;曾考虑基于 GPS 信号来控制自适应音频级别。 Treski 表示在探索自适应音频功能初期&#xff0…...

《Jetpack Compose从入门到实战》第九章 Accompanist 与第三方组件库

目录 AccompanistSystemUiControllerPagerSwipeRefreshFlow LayoutInsets LottieCoilAsyncImageSubcomposeAsyncImageAsyncImagePainter Accompanist 最新可用版本accompanist官方文档 SystemUiController 依赖&#xff1a;implementation “com.google.accompanist:accompa…...

Centos7 docker 容器内root身份应用自启动 /usr/sbin/init 问题

Centos7 docker 容器内root身份应用自启动 & /usr/sbin/init 问题 环境&#xff1a;我在一个 docker 容器内手动安装了 mysql、nginx、autotestsystem&#xff08;自己的服务&#xff09;&#xff1b; mysql 和 nginx 都做了服务脚本&#xff1a;mysqld.service、nginx.se…...

STL学习笔记之容器

首先我们要学习的是容器 第一个是容器的初始化&#xff08;构造方式&#xff09;有三种方式 分别是 第一种 int arr[]{1,2,3} vector<int> v1(arr,arr3) 即容器存放的种类和从另外一个数组去拷贝一段数据。 第二种 vector<int> v2(3,10); 第一个3是指存放…...

Java基础---第十二篇

系列文章目录 文章目录 系列文章目录一、获取一个类Class对象的方式有哪些?二、ArrayList 和 LinkedList 的区别有哪些?三、用过 ArrayList 吗?说一下它有什么特点?一、获取一个类Class对象的方式有哪些? 搞清楚类对象和实例对象,但都是对象。 第一种:通过类对象的 get…...

Acwing 841. 字符串哈希

Acwing 841. 字符串哈希 题目描述思路讲解代码展示 题目描述 思路讲解 代码展示 #include <iostream> #include <algorithm>using namespace std;typedef unsigned long long ULL;const int N 100010, P 131; // P 131 或者13331(经验值)int n, m; char str[N]…...

NEON优化:性能优化经验总结

NEON优化&#xff1a;性能优化经验总结 1. 什么是 NEONArm Adv SIMD 历史 2. 寄存器3. NEON 命名方式4. 优化技巧5. 优化 NEON 代码(Armv7-A内容&#xff0c;但区别不大)5.1 优化 NEON 汇编代码5.1.1 Cortex-A 处理器之间的 NEON 管道差异5.1.2 内存访问优化 Reference: NEON优…...

C++ 并发编程实战 第九章

目录 9.1 线程池 9.1.1 最简易可行的线程池 9.1.2 等待提交给线程池的任务完成运行 9.1.3等待其他任务完成的任务 9.1.4 避免任务队列上的争夺 9.1.5 任务窃取 9.2 中断线程 9.2.1 发起一个线程&#xff0c;以及把他中断 9.2.2 检测线程是否被中断 9.2.3 中断条件变…...

【Java】super 关键字用法

目录 this与super区别 1.访问成员变量-示例代码 继承中构造方法的访问特点 2.访问构造方法-示例代码&#xff1a; 继承中成员方法访问特点 3.访问成员方法-示例代码&#xff1a; super 关键字的用法和 this 关键字相似 this : 代表本类对象的引用super : 代表父类存储空间…...

前端笔试题总结,带答案和解析

1. 执行以下程序&#xff0c;输出结果为&#xff08;&#xff09; var x 10; var y 20; var z x < y ? x:y; console.log(xx;yy;zz);A x11;y21;z11 B x11;y20;z10 C x11;y21;z10 D x11;y20;z11 初始化x的值为10&#xff0c;y的值为20&#xff0c;x < y返回结果为tru…...

Omniverse Machinima

Omniverse Machinima App | NVIDIA Omniverse Machinima 是 NVIDIA 推出的一款实时动画创作工具&#xff0c;可用于在虚拟世界中制作和操纵角色及其环境。该工具使用 Universal Scene Description (USD) 作为其通用场景描述格式&#xff0c;可与多种 3D 建模、动画和渲染应用程…...

【测试人生】游戏业务测试落地精准测试专项的一些思路

精准测试在互联网领域有广泛的应用。以变更为出发点&#xff0c;通过对变更内容进行分析&#xff0c;可以确定单次变更具体涉及到哪些模块和功能点&#xff0c;以及是否存在夹带风险&#xff0c;从而从QA的视角&#xff0c;可以知道哪些功能模块需要做测试&#xff0c;以及哪些…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

QT: `long long` 类型转换为 `QString` 2025.6.5

在 Qt 中&#xff0c;将 long long 类型转换为 QString 可以通过以下两种常用方法实现&#xff1a; 方法 1&#xff1a;使用 QString::number() 直接调用 QString 的静态方法 number()&#xff0c;将数值转换为字符串&#xff1a; long long value 1234567890123456789LL; …...

vue3+vite项目中使用.env文件环境变量方法

vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量&#xff0c;这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...

Java线上CPU飙高问题排查全指南

一、引言 在Java应用的线上运行环境中&#xff0c;CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时&#xff0c;通常会导致应用响应缓慢&#xff0c;甚至服务不可用&#xff0c;严重影响用户体验和业务运行。因此&#xff0c;掌握一套科学有效的CPU飙高问题排查方法&…...

视频行为标注工具BehaviLabel(源码+使用介绍+Windows.Exe版本)

前言&#xff1a; 最近在做行为检测相关的模型&#xff0c;用的是时空图卷积网络&#xff08;STGCN&#xff09;&#xff0c;但原有kinetic-400数据集数据质量较低&#xff0c;需要进行细粒度的标注&#xff0c;同时粗略搜了下已有开源工具基本都集中于图像分割这块&#xff0c…...

C++:多态机制详解

目录 一. 多态的概念 1.静态多态&#xff08;编译时多态&#xff09; 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1&#xff09;.协变 2&#xff09;.析构函数的重写 5.override 和 final关键字 1&#…...

MySQL 知识小结(一)

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

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

DBLP数据库是什么?

DBLP&#xff08;Digital Bibliography & Library Project&#xff09;Computer Science Bibliography是全球著名的计算机科学出版物的开放书目数据库。DBLP所收录的期刊和会议论文质量较高&#xff0c;数据库文献更新速度很快&#xff0c;很好地反映了国际计算机科学学术研…...