使用Java实现一个简单的B树

1.B树简介

B树是一个搜索树,数据结构可以抽象成如二叉树一样的树,不过它有平衡、有序、多路的特点。

  • 平衡:所有叶子节点都在同一层。
  • 有序:任一元素的左子树都小于它,右子树都大于它。
  • 多路:B树的每个节点最多有m个子节点,m即为B数的阶数,同时由阶数可以得到另一个概念:B树的度数,它决定了每个节点最多存在的元素个数。

其结构图如下:

8ad6bb26f2bd4f9193869a91897c794b.jpeg

2.代码实现

2.1 B树节点类设计

首先定义一个节点,代码结构如下,它的成员变量以及函数定义如下。

  • curKeyNums记录当前节点元素个数,用于判断节点是否需要分裂的操作等。
  • keys数组接收每个节点的元素,初始化时定义一个B树度数的数组,表示最多能容纳n个元素。
  • children数组负责存储对应keys数组中每个元素对应的左子树、右子树,初始化时定义一个B树度数长度+1的数组,表示该节点最多有B树度数+1的子节点。
  • isLeaf()方法判断当前节点是否是叶子节点,判断依据就是看它有没有“孩子”。
public class BtreeNode {int curKeyNums;Integer[] keys;BtreeNode[] children;public BtreeNode(int degrees){curKeyNums = 0;keys = new Integer[degrees];children = new BtreeNode[degrees+1];}public boolean isLeaf(){return children[0] == null;}
}

假设某个key在keys数组中的下标是i,那么在children数组中小于等于i的子树都是该key的左子树,都小于key,同理大于i的子树都是该key的右子树,都大于key。这个结论非常重要,务必要记住,因为将会在后面的合并节点中使用到。

2.2 B树类设计

B树是一颗树,因此它的设计如下:

  • degress表示一颗B树的度数,即任一节点最多容纳的key数量。
  • root根节点,因为本质上是一颗结构树,B树的增删查操作都是通过根节点作为入口完成的。
public class Btree {int degrees; // 度数BtreeNode root; // B树的根节点public Btree(int degrees){this.degrees = degrees;root = new BtreeNode(degrees);}
}

2.3 增加元素到B树

这个小节将用Java手动实现怎么将一个元素添加到B树。

增加元素要考虑的场景其实也比较复杂,从上面定义的B树度数、任一元素的左右子树均小于、大于该元素,因此会涉及一个节点拆分的过程,此过程不是太复杂,复杂的是拆分以后的节点合并工作。

2.3.1 二分查找确定插入key的位置

当添加一个新的key到B树时,假设此时找到了需要添加的节点(keys数组也没满),那么如何确定待插入的key应该放在keys数组的哪里吗?

通过二分查找(时间复杂度O(logN))的方法确定插入下标,二分查找的特点是根据中间元素和待插入key判断,随时调整每一次遍历的起始下标,具体代码如下:

    private int binarySearchInsertIdx(int key, BtreeNode node){// 二分查找的特点是随时调整左右下标int left = 0;int right = node.curKeyNums-1;while (left<=right){int mid = (right-left)/2 + left;// 再加上left的意思是补充移位if (node.keys[mid]>key){// 往左边查找right = mid-1;} else if (node.keys[mid]<key) {// 往右边查找left = mid+1;}else {return mid;}}return left;}

2.3.2 节点分裂操作

当插入元素,找到一个插入节点时,若发现此时的keys数组已满,则需要进行节点的拆分。

由于keys数组的元素插入都是通过二分查找的方式找到插入下标完成,因此keys数组是有序的。

因此这里我们用 (keys.length/2)计数出中间元素的下标即为midIdx,即此时下标小于midIdx的元素都小于中间元素,提取为左子树,大于midIdx的元素都大于中间元素,提取为右子树。此外中间元素将升级为一个新的父节点,将中间元素值直接存入keys[0]中,该新父节点的curKeyNums为1,这是后面插入方法中判断是否分裂成了一个新节点的判断依据(因为B树的度数一般都大于1)。

具体代码如下:

    private BtreeNode splitNode(BtreeNode node){// 拆分节点,进到这里的node的keys数量肯定是刚好等于B树的度数了int midIdx = (node.curKeyNums)/2;int extractVal = node.keys[midIdx];BtreeNode newFatherNode = new BtreeNode(degrees);newFatherNode.keys[0] = extractVal;newFatherNode.curKeyNums++;// 小于midIdx的作为新父节点的左子树BtreeNode leftNode = new BtreeNode(degrees);for (int i=0;i<midIdx;i++){leftNode.curKeyNums++;leftNode.keys[i] = node.keys[i];}// 大于midIdx的作为新父节点的右子树,右子树的填充使用倒序更加明确BtreeNode rightNode = new BtreeNode(degrees);for (int i= node.curKeyNums-1;i>midIdx;i--){rightNode.curKeyNums++;rightNode.keys[i-midIdx-1] = node.keys[i];}newFatherNode.children[0]=leftNode;newFatherNode.children[1]=rightNode;return newFatherNode;}

2.3.3 插入元素操作

插入元素的操作,切入点都是B树的root根节点。因为后面的插入操作都是通过递归完成的,需要有较强的递归回溯思维才能更好理解。

首先 insert(int key)方法是外界添加元素到B树的唯一入口,里面调用了insertKeyToNode(key, root)方法,表示每一次的插入元素都是以root根节点为入口。在insertKeyToNode方法中,会存在递归调用自己的情况。

首先,我们分析以下这几种情况:

①keys数组还没有满并且是叶子节点:

(新元素必须添加到叶子节点中)将key插入到二分查找的插入下标位置中。如度数为3的B树,有这么一个节点的keys=【2,5】,要插入的key是1,则最终找到的插入下标是0,那么将变成keys=【1,2,5】。

    private void insert(int key){root = insertKeyToNode(key, root);}// 插入key到叶子节点private BtreeNode insertKeyToNode(int key, BtreeNode node){int curNodeKeyNums = node.curKeyNums;if (curNodeKeyNums == degrees){// 如果插入节点的key数量达到了度数,则需要拆分该节点并返回新的父节点node = splitNode(node);}if (node.keys[0]!=null && node.keys[0]==key){return node;}int possibleInsertIdx = binarySearchInsertIdx(key, node);// 然后再判断当前的node是不是叶子节点if (node.isLeaf()){// 如果插入节点的key数量还没有达到度数,直接添加即可insertKeyToArray(possibleInsertIdx, key, node);}else {// 如果不是叶子节点,且节点数是1的话说明分裂成了新节点BtreeNode t = insertKeyToNode(key, node.children[possibleInsertIdx]);if(t.curKeyNums==1){// 需要将当前的t的key以及左右子树都并入到node中// 首先需要将node的key移动位置,比如node的keys=[5],此时t的keys[0]为2,那么// 插入下标就是0,从0+1开始for (int i = node.curKeyNums; i>possibleInsertIdx;i--){node.keys[i] = node.keys[i-1];}// 合并t的keys[0]node.keys[possibleInsertIdx] = t.keys[0];// 配合上面的insertKeyToNode(key, node.children[possibleInsertIdx])// 更好理解for (int i=node.curKeyNums+1;i>possibleInsertIdx+1;i--){node.children[i] = node.children[i-1];}node.children[possibleInsertIdx] = t.children[0];node.children[possibleInsertIdx+1] = t.children[1];node.curKeyNums++;}}return node;}

 ②keys数组还没有满并且不是叶子节点:

由于按照B树的定义,元素必须先插入到叶子节点中。不过此时需要回顾的一点是,初始化的root根节点是叶子节点,也就是说当root节点的keys数组满了并且经过节点分裂操作,此时的root节点升级为非叶子节点,因为root根节点有了“孩子”。

即无法直接添加到如今的root根节点时,根据此时root.keys数组和待插入key通过二分查找方式找到插入下标possibleInsertIdx,通过它可以知道这个key应该插入到root根节点的哪个子树,左子树还是右子树?

其实这个左右子树的判断光从代码上看挺难分析出来的,还是以具体例子去理解:B树度数为3,此时root.keys=【1,4,7】,准备插入元素5,此时需要将root节点拆分为root.keys=【4】,root.children=【【1】,【7】】,那么此时再添加5的时候,发现插入下标是1,则将5添加到的子树就是root的右子树【7】...最终将变成root.keys=【4】,root.children=【【1】,【5,7】】。

通过上面的例子,知道了如果找到的第一层节点不是叶子节点,则还是先通过二分查找找到待插入key的下标,再次递归调用insertKeyToNode方法,不过传入的插入节点此时是第一层节点的对应子树节点。

③新的分裂节点与旧的分裂节点合并:

由于在递归调用insertKeyToNode方法的时候,有可能又分裂了节点,那么就需要对新分裂的节点t和原来的节点node做合并操作。这个合并操作理解起来并不是那么容易。

如果新节点t的curKeyNums是1则肯定是一个新分裂出来的节点,此时待插入的key已经存入到了t节点,并且注意到BtreeNode t = insertKeyToNode(key, node.children[possibleInsertIdx])这行代码,是将node节点的某个插入子树传入调用了,即当调用栈回溯到这里时,可以认为node的这个子树已经死了、消亡了。记住这个概念对后面做子树合并会有非常大的帮助!

  • 新旧分裂节点的key元素合并,将新分裂节点t的key转移到老分裂节点node的keys中,由于新分裂节点的key只有一个,而且是没递归调用insertKeyToNode方法时就确定的插入下标,因此直接将从插入下标后面开始,将元素移动到后一位,最后再将t.keys[0]赋值给node.keys[possibleInsertIdx]中即完成了新旧分裂节点key元素的合并。
  • 新分裂节点的子树合并到老节点的子树中,子树合并的情况似乎更复杂一点,但是我们要记住的一点时,此时的旧节点其实只剩下一个子树了(只剩下一个子树的说法不严谨,但是由于是递归实现的,以第一次的情况描述好像也无问题,因为从数学归纳法角度看,一次递归和n次递归的效果都是一样的)。
  • 由于插入key的下标是possibleInsertIdx,并且node.children[possibleInsertIdx]也已经“死了”,那么新分裂节点的左子树t.children[0]应该被安置在哪里呢?安置在node.children[possibleInsertIdx]对应空间中。因为,t.keys[0]被安置在了node.keys[possibleInsertIdx]中,前面也介绍了小于等于元素下标的子树中都是小于该元素的。同理,新分裂节点的右子树t.children[1]应该分配在下标大于possibleInsertIdx、即possibleInsertIdx+1的老节点的子树数组中。
  • 由于最终子树合并占用了possibleInsertIdx、possibleInsertIdx+1两个下标空间,因此需要先在老分裂节点的子树数组中先从possibleInsertIdx+2下标开始将子树节点往后挪。(ps:往后挪动的子树是跟着挪动的旧节点key 同步进行的,可以尝试想象出这个画面~似乎更好理解)

总结,插入元素非常烧脑,需要对递归很熟悉才能理解整个流程操作。

 

 

 

 

 

 

 

 

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/426382.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】文件权限与类型全解:你的文件安全指南

欢迎来到 CILMY23 的博客 &#x1f3c6;本篇主题为&#xff1a;文件权限与类型全解&#xff1a;你的文件安全指南 &#x1f3c6;个人主页&#xff1a;CILMY23-CSDN博客 &#x1f3c6;系列专栏&#xff1a;Python | C | C语言 | 数据结构与算法 | 贪心算法 | Linux | 算法专题…

激光雷达点云处理—学习随记

一、激光雷达基本概念 激光雷达&#xff08;Light Detection and Ranging&#xff0c;LiDAR&#xff09;&#xff0c;是一种发射激光&#xff08;可见光-近红外&#xff09;于被瞄准物体表面并记录反射光被信号接收器接收到的时间以测定距离的方法。激光雷达通过以下公式确定物…

基于springboot酒店管理系统

酒店管理系统 552酒店管理系统 摘 要 21世纪的今天&#xff0c;随着社会的不断发展与进步&#xff0c;人们对于信息科学化的认识&#xff0c;已由低层次向高层次发展&#xff0c;由原来的感性认识向理性认识提高&#xff0c;管理工作的重要性已逐渐被人们所认识&#xff0c;…

【MySQL】查询语句之inner、left、right、full join 的区别

前言&#xff1a; INNER JOIN 和 OUTER JOIN 是SQL中常用的两种连接方式&#xff0c;用于从两表活多表中提取相关的数据。两者区别主要在于返回的 结果集 如何处理 匹配 与 不匹配 的行。 目录 1、INNER JOIN 2、OUTER JOIN 3、总结 1、INNER JOIN 称为内连接&#xff0c;只…

【Python机器学习】NLP信息提取——命名实体与关系

我们希望计算机能够从文本中提取信息和事实&#xff0c;从而略微理解用户所说的内容。例如&#xff0c;当用户说“提醒我星期一浏览***.org网站”&#xff0c;我们希望这句话触发当天后下一个周一的日程或者提醒的操作。 要触发上述操作&#xff0c;需要知道“我”代表一种特定…

5.内容创作的未来:ChatGPT如何辅助写作(5/10)

引言 在信息爆炸的时代&#xff0c;内容创作已成为连接品牌与受众、传递信息与知识、以及塑造文化与观念的重要手段。随着数字媒体的兴起&#xff0c;内容创作的需求日益增长&#xff0c;对创作者的写作速度和质量提出了更高的要求。人工智能&#xff08;AI&#xff09;技术的…

感谢问界M9一打二十,让我们买到这么便宜的BBA

文 | AUTO芯球 作者 | 雷慢 国产豪华车&#xff0c;终于扬眉吐气了&#xff0c; 你敢信吗&#xff1f;在50万以上豪华车中&#xff0c; 现在问界M9一款车的月销量&#xff0c; 是其他前20名销量的总和&#xff01; 要知道&#xff0c;它的对手是各种宝马、奔驰、雷克萨斯的…

私有化通讯工具:安全、高效、个性化,重塑企业沟通生态

在当今数字化时代&#xff0c;即时通讯已成为企业日常运营中不可或缺的一部分。随着数据安全和隐私保护意识的日益增强&#xff0c;越来越多的企业开始寻求更加安全、可控的沟通方式。私有化聊天工具应运而生&#xff0c;以其独特的核心优势&#xff0c;为企业构建了一个安全、…

VMware vSphere 8.0 Update 3b 发布下载,新增功能概览

VMware vSphere 8.0 Update 3b 发布下载&#xff0c;新增功能概览 vSphere 8.0U3 | ESXi 8.0U3 & vCenter Server 8.0U3 请访问原文链接&#xff1a;https://sysin.org/blog/vmware-vsphere-8-u3/&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页…

【Leetcode】70. 爬楼梯

题目来源 70. 爬楼梯 题目描述 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢&#xff1f; 示例 1&#xff1a; 输入&#xff1a;n 2 输出&#xff1a;2 解释&#xff1a;有两种方法可以爬到楼顶。 1 阶…

webpack5 构建优化方案看这篇就够了!【Node.js进阶】

无论在面试还是内部晋升&#xff0c;webpack 构建优化方案 一直都是非常重要的部分。 webpack5构建加持 一、项目完成目标二、搭建项目1. 安装koa、koa/router &#xff08;如果已经配置可路过&#xff09;2. 创建入口文件3. 安装构建依赖4. 在项目根目录添加 .babelrc 文件5. …

一般在写SQL时需要注意哪些问题,可以提高查询的效率?

很多人写SQL按照自己喜好&#xff0c;没有规则意识&#xff0c;这对于自主查询影响不大&#xff0c;你爱怎么搞就怎么搞&#xff0c;一旦涉及到提交任务或团队共享&#xff0c;就不能乱写了&#xff0c;会浪费资源影响到开发效率&#xff0c;严重的甚至会服务器瘫痪。 提几个关…

进程的重要函数

进程的重要函数: fork函数 了解fork函数 通过调用fork()函数&#xff0c;则会产生一个新的进程。调用fork()函数的进程叫做 父进程&#xff0c;产生的新进程则为子进程。 其编码过程: 1.函数功能: 函数头文件 #include <sys/types.h> #include <unistd.h> 函数…

运用Java实现倒计时功能

这个功能其实是比较好实现的&#xff0c;一般来说java中实现倒计时有两种方法&#xff1a; 1、使用 scheduledexecutorservice创建一个可重复执行的任务&#xff0c;直到时间到&#xff1a; ScheduledExecutorService 是 Java 中一种用于安排延迟或定期任务的工具。我们可以使…

云计算第四阶段------CLOUD Day4---Day6

Cloud DAY4 项目架构图&#xff1a; 环境准备&#xff1a; 主机名称IP地址配置logstash192.168.1.27最低配置4核8G #书接上文&#xff0c;我们在华为云平台租了几台云服务器&#xff0c;这次买一台性能好的服务器&#xff0c;作为logstash软件部署的载体。 今天给小伙伴们带来…

低代码门户技术:构建高效应用的全新方式

什么是低代码门户技术&#xff1f; 低代码门户技术是一种利用低代码平台构建企业门户网站或应用的技术。门户通常是企业内部和外部用户访问信息和应用的集中平台。低代码门户技术通过图形化界面和预置组件&#xff0c;允许用户快速搭建和定制这些门户平台&#xff0c;而无需深…

TCP并发服务器的实现

一请求一线程 问题 当客户端数量较多时&#xff0c;使用单独线程为每个客户端处理请求可能导致系统资源的消耗过大和性能瓶颈。 资源消耗&#xff1a; 线程创建和管理开销&#xff1a;每个线程都有其创建和销毁的开销&#xff0c;特别是在高并发环境中&#xff0c;这种开销…

性能测试的复习3-jmeter的断言、参数化、提取器

一、断言、参数化、提取器 需求&#xff1a; 提取查天气获取城市名请求的响应结果&#xff1a;城市对查天气获取城市名的响应结果进行响应断言和json断言对查天气获取城市名添加用户参数 1、步骤 查看天气获取城市名 json提取器&#xff08;对响应结果提取、另一个接口请求…

简单了解微服务--黑马(在更)

认识微服务 单体架构 不适合大型复杂项目 微服务架构 将单体结构的各个功能模块拆分为多个独立的项目 拆取的独立项目分别开发&#xff0c;在部署的时候也要分别去编译打包&#xff0c;分别去部署&#xff0c;不同的模块部署在不同的服务器上&#xff0c;对外提供不同的功能…

小间距LED显示屏的技术原理分析

在现代显示技术领域&#xff0c;小间距LED显示屏以其卓越的显示效果和灵活的应用场景&#xff0c;逐渐成为市场的新宠。本文将深入探讨小间距LED显示屏的技术原理&#xff0c;分析其在显示领域的应用优势。 A、小间距LED显示屏的基本概念 小间距LED显示屏是指LED灯珠之间的间距…