B树的实现

B树（B-tree）是一种平衡的多路查找树，用于存储和管理大量有序数据。与二叉搜索树不同，B树可以在节点中存储多个关键字，并拥有多个子节点，使得查找、插入和删除操作具有更高的效率。

B树的基本定义：

  • B树的阶数 t 指定了每个节点最多可以拥有 2t - 1 个键值。
  • 叶子节点包含 2t - 1 个键值，内部节点包含 2t - 1 到 2t 个子节点。
  • B树保持平衡，确保查找、插入和删除的时间复杂度为 O(log n)。

B树的特性：

  1. 根节点至少包含 1 个关键字，最多 2t - 1 个。
  2. 非叶子节点包含 2t 个子节点。
  3. 叶子节点具有相同的深度。

B树的操作：

  1. 插入操作：

    • 如果节点满了，就分裂节点。
    • 如果父节点也满了，就递归分裂，直到根节点。

  2. 查找操作：

    • 从根节点开始，按键值进行遍历，找到目标位置。

  3. 删除操作：

    • 如果键值在非叶子节点，找到前驱或后继进行替换。
    • 如果在叶子节点，直接删除并调整。

1. 定义和结构体定义 

#define DEGREE 3
typedef int KEY_VALUE;// 定义B树节点结构体
typedef struct _btree_node {KEY_VALUE *keys;          // 键值数组struct _btree_node **childrens; // 子节点指针int num;                  // 当前节点的键值数量int leaf;                 // 是否为叶子节点：1表示叶子，0表示非叶子
} btree_node;// 定义B树结构体
typedef struct _btree {btree_node *root;    // 根节点int t;               // 阶数
} btree;

 

  • DEGREE：定义B树的阶数，这决定了每个节点的最大子节点数（2t - 1 键值，2t 子节点）。
  • btree_node：每个节点包含：
    • keys：存储键值。
    • childrens：存储子节点指针。
    • num：当前节点中实际的键值数量。
    • leaf：标志当前节点是否是叶子节点。
  • btree：包含B树的根节点和阶数。

2. 节点创建函数 btree_create_node 

btree_node *btree_create_node(int t, int leaf) {btree_node *node = (btree_node *)calloc(1, sizeof(btree_node));if (node == NULL) {return NULL;}node->leaf = leaf;node->keys = (KEY_VALUE *)calloc(1, (2 * t - 1) * sizeof(KEY_VALUE));node->childrens = (btree_node **)calloc(1, (2 * t) * sizeof(btree_node *));node->num = 0;return node;
}

 

  • btree_create_node：创建一个新的B树节点。
  • 参数 t：阶数。
  • 参数 leaf：是否为叶子节点。
  • 返回创建的节点。

3. 节点销毁函数 btree_destroy_node 

void btree_destroy_node(btree_node *node) {if (node) {free(node->childrens);free(node->keys);free(node);}
}

 btree_destroy_node：释放节点内存。

4. B树初始化函数 btree_create 

void btree_create(btree *T, int t) {T->t = t;btree_node *x = btree_create_node(t, 1); // 根节点为叶子节点T->root = x;
}

 btree_create：初始化B树，创建一个根节点为叶子的B树结构。

5. 分裂函数 btree_split_child

void btree_split_child(btree *T, btree_node *x, int i) {int t = T->t;btree_node *y = x->childrens[i];  // 被分裂的节点btree_node *z = btree_create_node(t, y->leaf);  // 新的节点z->num = t - 1;  // 新节点的键值数量// 复制y节点后半部分的键值到z节点for (int j = 0; j < t - 1; j++) {z->keys[j] = y->keys[j + t];}if (y->leaf == 0) {for (int j = 0; j < t; j++) {z->childrens[j] = y->childrens[j + t];}}y->num = t - 1;  // y节点的键值数量调整// 为x节点腾出位置插入新的子节点指针for (int j = x->num; j >= i + 1; j--) {x->childrens[j + 1] = x->childrens[j];}x->childrens[i + 1] = z;// 调整x节点的键值，将分裂出来的键值放到合适位置for (int j = x->num - 1; j >= i; j--) {x->keys[j + 1] = x->keys[j];}x->keys[i] = y->keys[t - 1];x->num += 1;
}

 

  • btree_split_child：分裂节点 x 的第 i 个子节点，确保B树保持平衡。
  • 如果某个节点的子节点满了，就需要将它分裂成两个新的子节点。

6. 非满节点插入函数 btree_insert_nonfull 

void btree_insert_nonfull(btree *T, btree_node *x, KEY_VALUE k) {int i = x->num - 1;if (x->leaf == 1) {// 从后往前找到合适的插入位置while (i >= 0 && x->keys[i] > k) {x->keys[i + 1] = x->keys[i];i--;}x->keys[i + 1] = k;x->num += 1;}else {while (i >= 0 && x->keys[i] > k) {i--;}if (x->childrens[i + 1]->num == (2 * (T->t)) - 1) {btree_split_child(T, x, i + 1);if (k > x->keys[i + 1]) {i++;}}btree_insert_nonfull(T, x->childrens[i + 1], k);}
}

 

  • btree_insert_nonfull：向非满的节点插入键值 k。
  • 如果插入位置满了，则需要分裂对应的子节点，确保节点和树结构的平衡。

7. B树插入函数 btree_insert 

void btree_insert(btree *T, KEY_VALUE key) {btree_node *r = T->root;if (r->num == 2 * T->t - 1) {btree_node *node = btree_create_node(T->t, 0); // 创建新的根节点if (node == NULL) {return;  // 内存分配失败处理}T->root = node;node->childrens[0] = r;btree_split_child(T, node, 0);int i = 0;if (node->keys[0] < key) {i++;}btree_insert_nonfull(T, node->childrens[i], key);}else {btree_insert_nonfull(T, r, key);}
}

 

  • btree_insert：插入一个键值 key。
  • 如果根节点满了，就创建一个新的根节点，进行分裂并插入新节点。

8. 中序遍历函数 btree_traverse

void btree_traverse(btree_node *x) {for (int i = 0; i < x->num; i++) {if (x->leaf == 0) {btree_traverse(x->childrens[i]);}printf("%d ", x->keys[i]);}if (x->leaf == 0) {btree_traverse(x->childrens[x->num]);}
}

btree_traverse：递归地中序遍历B树。

 

9. 打印B树结构 btree_print

void btree_print(btree *T, btree_node *node, int layer) {if (node) {printf("\nlayer = %d keynum = %d is_leaf = %d\n", layer, node->num, node->leaf);for (int i = 0; i < node->num; i++) {printf("%d ", node->keys[i]);}printf("\n");layer++;for (int i = 0; i <= node->num; i++) {if (node->childrens[i]) {btree_print(T, node->childrens[i], layer);}}}else {printf("the tree is empty\n");}
}

btree_print：打印B树的结构，展示每个节点的层级和键值。

10. 删除函数 btree_delete_key 

void btree_delete_key(btree *T, btree_node *node, KEY_VALUE key) {if (node == NULL) {return;}int idx = 0;while (idx < node->num && key > node->keys[idx]) {idx++;}if (idx < node->num && key == node->keys[idx]) {if (node->leaf) {for (int i = idx; i < node->num - 1; i++) {node->keys[i] = node->keys[i + 1];}node->keys[node->num - 1] = 0;node->num--;if (node->num == 0) {free(node);T->root = NULL;}}else {// Find predecessor or successorbtree_node *child = node->childrens[idx];if (child->num >= T->t) {btree_node *left = node->childrens[idx];node->keys[idx] = left->keys[left->num - 1];btree_delete_key(T, left, left->keys[left->num - 1]);}else {// Merge and deletebtree_merge(T, node, idx);btree_delete_key(T, node->childrens[idx], key);}}}else {btree_node *child = node->childrens[idx];if (child && child->num == T->t - 1) {btree_node *left = NULL, *right = NULL;if (idx > 0) {left = node->childrens[idx - 1];}if (idx < node->num) {right = node->childrens[idx + 1];}if ((left && left->num >= T->t) || (right && right->num >= T->t)) {int richR = 0;if (right) {richR = 1;}if (left && right) {richR = (right->num > left->num) ? 1 : 0;}if (right && right->num >= T->t && richR) {// Borrow from rightchild->keys[child->num] = node->keys[idx];child->childrens[child->num + 1] = right->childrens[0];child->num++;node->keys[idx] = right->keys[0];for (int i = 0; i < right->num - 1; i++) {right->keys[i] = right->keys[i + 1];right->childrens[i] = right->childrens[i + 1];}right->keys[right->num - 1] = 0;right->childrens[right->num] = NULL;right->num--;}else {// Borrow from leftfor (int i = child->num; i > 0; i--) {child->keys[i] = child->keys[i - 1];child->childrens[i + 1] = child->childrens[i];}child->childrens[1] = child->childrens[0];child->childrens[0] = left->childrens[left->num];child->keys[0] = node->keys[idx - 1];child->num++;node->keys[idx - 1] = left->keys[left->num - 1];left->keys[left->num - 1] = 0;left->childrens[left->num] = NULL;left->num--;}}else if ((!left || (left->num == T->t - 1)) && (!right || (right->num == T->t - 1))) {if (left && left->num == T->t - 1) {btree_merge(T, node, idx - 1);child = left;}else if (right && right->num == T->t - 1) {btree_merge(T, node, idx);}}}btree_delete_key(T, child, key);}
}

 

  • btree_delete_key：在B树中删除指定的键值 key。
  • 通过递归的方式调整树结构，维护B树的平衡。

 11. B树删除函数 btree_delete

int btree_delete(btree *T, KEY_VALUE key) {if (!T->root) {return -1; // 树为空}btree_delete_key(T, T->root, key);if (T->root->num == 0) {btree_node *temp = T->root;T->root = T->root->childrens[0];free(temp);}return 0; // 删除成功
}

 btree_delete：外部接口，删除B树中的一个键值。

12. 示例主函数 main 

int main() {btree T;btree_create(&T, DEGREE); // 创建B树，阶数为3btree_insert(&T, 10);btree_insert(&T, 20);btree_insert(&T, 5);btree_insert(&T, 6);btree_insert(&T, 15);btree_insert(&T, 25);printf("B-tree traversal: ");btree_traverse(T.root); // 中序遍历输出btree_delete(&T, 15);    // 删除键值15printf("\nAfter deletion: ");btree_traverse(T.root); // 中序遍历输出btree_print(&T, T.root, 0); // 打印B树结构return 0;
}

 

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

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

相关文章

RK3506开发板：智能硬件领域的新选择，带来卓越性能与低功耗

RK3506开发板：智能硬件领域的新选择，带来卓越性能与低功耗

在现代智能硬件开发中&#xff0c;选择一款性能稳定、功耗低的开发板是确保产品成功的关键。Rockchip最新推出的RK3506芯片&#xff0c;凭借其卓越的能效比、多功能扩展性和优秀的实时性能&#xff0c;已经成为智能家电、工业控制、手持终端等领域的热门选择。而基于RK3506的Ar…
阅读更多...
【AIGC-ChatGPT进阶副业提示词】星际占卜师：探索星象能量的艺术【限时免费阅读，一天之后自动进入进阶课程】

【AIGC-ChatGPT进阶副业提示词】星际占卜师：探索星象能量的艺术【限时免费阅读，一天之后自动进入进阶课程】

引言 在这个数字化的时代&#xff0c;我们创造了一个独特的角色 —— 星际占卜师。这不仅是一个简单的运势预测工具&#xff0c;更是一个融合了玄学、预言和能量解读的智能向导。通过精心设计的系统提示词和独特的画境生成机制&#xff0c;星际占卜师能够为用户带来沉浸式的占…
阅读更多...
机器学习之PCA降维

机器学习之PCA降维

主成分分析&#xff08;PCA&#xff0c;Principal Component Analysis&#xff09; 主成分分析&#xff08;PCA&#xff09;是一种常见的无监督学习技术&#xff0c;广泛应用于数据降维、数据可视化以及特征提取等任务。PCA的目标是通过线性变换将数据从高维空间映射到低维空间…
阅读更多...
SOTA简繁中文拼写检查工具：FASPell Chinese Spell Checker 论文

SOTA简繁中文拼写检查工具：FASPell Chinese Spell Checker 论文

拼写纠正系列 NLP 中文拼写检测实现思路 NLP 中文拼写检测纠正算法整理 NLP 英文拼写算法&#xff0c;如果提升 100W 倍的性能&#xff1f; NLP 中文拼写检测纠正 Paper java 实现中英文拼写检查和错误纠正&#xff1f;可我只会写 CRUD 啊&#xff01; 一个提升英文单词拼…
阅读更多...
Visual Studio Code历史版本下载

Visual Studio Code历史版本下载

本章教程&#xff0c;介绍如何找到Visual Studio Code的历史版本官方下载地址。 一、历史版本下载地址 下载地址&#xff1a;https://code.visualstudio.com/updates/ 二、常用版本下载地址 August 2017 (version 1.16)&#xff1a;https://code.visualstudio.com/updates/v1_…
阅读更多...
Kubernetes(k8s)离线部署DolphinScheduler3.2.2

Kubernetes(k8s)离线部署DolphinScheduler3.2.2

1.环境准备 1.1 集群规划 本次安装环境为&#xff1a;3台k8s现有的postgreSql数据库zookeeper服务 1.2 下载及介绍 DolphinScheduler-3.2.2官网&#xff1a;https://dolphinscheduler.apache.org/zh-cn/docs/3.2.2 官网安装文档&#xff1a;https://dolphinscheduler.apach…
阅读更多...
【自动化测试】windows下安装Selenium浏览器界面测试工具

【自动化测试】windows下安装Selenium浏览器界面测试工具

Date: 2024.12.23 10:15:53 author: lijianzhan 简述&#xff1a;这篇教程详细介绍了如何在Windows环境下安装selenium&#xff0c;并设置Chrome浏览器驱动。什么是Selenium&#xff1f;Selenium是一个基于浏览器的自动化测试工具&#xff0c;它提供了一种跨平台、跨浏览器的端…
阅读更多...
如何在 Ubuntu 22.04 上安装 phpMyAdmin

如何在 Ubuntu 22.04 上安装 phpMyAdmin

简介 PHPMyAdmin 是在 Ubuntu 22.04 上管理 MySQL 数据库的绝佳选择。它是一个流行的工具&#xff0c;拥有简单、高效且用户友好的基于 Web 的界面&#xff0c;让你能够轻松地管理 MySQL 数据库。因此&#xff0c;许多开发人员、数据库管理员和网站所有者都信任 PHPMyAdmin 来…
阅读更多...
大数据-256 离线数仓 - Atlas 数据仓库元数据管理 正式安装 启动服务访问 Hive血缘关系导入

大数据-256 离线数仓 - Atlas 数据仓库元数据管理 正式安装 启动服务访问 Hive血缘关系导入

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; Java篇开始了&#xff01; 目前开始更新 MyBatis&#xff0c;一起深入浅出&#xff01; 目前已经更新到了&#xff1a; Hadoop&#xff0…
阅读更多...
[Python3] Sanic中间件

[Python3] Sanic中间件

在 Sanic 中&#xff0c;中间件&#xff08;middleware&#xff09;是指在请求和响应之间执行的代码。它们是一个非常强大的工具&#xff0c;用于处理请求的预处理、响应的后处理、全局错误处理、日志记录、认证、权限校验、跨域资源共享&#xff08;CORS&#xff09;等任务。中…
阅读更多...
使用 OpenCV 绘制线条和矩形

使用 OpenCV 绘制线条和矩形

OpenCV 是一个功能强大的计算机视觉库&#xff0c;它不仅提供了丰富的图像处理功能&#xff0c;还支持图像的绘制。绘制简单的几何图形&#xff08;如线条和矩形&#xff09;是 OpenCV 中常见的操作。在本篇文章中&#xff0c;我们将介绍如何使用 OpenCV 在图像上绘制线条和矩形…
阅读更多...
操作系统课程设计

操作系统课程设计

摘 要 本项目旨在深入设计与实现一套基于Java的模拟操作系统&#xff0c;模拟和实现常见操作系统的核心功能&#xff0c;包括进程管理、内存分配与调度、高效的文件系统和多样化设备的管理。通过该模拟操作系统的开发&#xff0c;探索计算机操作系统的基础理论与实际工程细节…
阅读更多...
css改变输入右下角图标

css改变输入右下角图标

前言 正常情况下&#xff0c;HTML textarea 多行文本输入框会存如下图所示图标&#xff0c; 用户可拉动它改变高度&#xff0c;这是我们不想看到的&#xff0c;所以要去掉它。 去掉后&#xff1a; 解决方案 设置 resize 属性即可&#xff0c;如下代码所示&#xff1a; <…
阅读更多...
HTML-CSS（day01）

HTML-CSS（day01）

W3C标准&#xff1a; W3C&#xff08; World Wide Web Consortium&#xff0c;万维网联盟&#xff09; W3C是万维网联盟&#xff0c;这个组成是用来定义标准的。他们规定了一个网页是由三部分组成&#xff0c;分别是&#xff1a; 三个组成部分&#xff1a;&#xff08;1&…
阅读更多...
2024-12-24 NO1. XR Interaction ToolKit 环境配置

2024-12-24 NO1. XR Interaction ToolKit 环境配置

文章目录 1 软件配置2 安装 XRToolKit3 配置 OpenXR4 安装示例场景5 运行测试 1 软件配置 Unity 版本&#xff1a;Unity6000.0.26 ​ 2 安装 XRToolKit 创建新项目&#xff08;URP 3D&#xff09;&#xff0c;点击进入 Asset Store。 进入“Unity Registry”页签&#xff0…
阅读更多...
C语言基础——指针（4）

C语言基础——指针（4）

一&#xff0e; 字符指针变量 字符指针变量的使用和整型指针变量的使用方法相似&#xff0c;以下是其基本使用方法的例子&#xff1a; &#xff08;1&#xff09;字符指针变量还有一种使用方法&#xff1a; const char* p "abcd" 需…
阅读更多...
week 11 - BCNF

week 11 - BCNF

1. More on functional dependencies (功能依赖的更多内容) Lossless decomposition (无损分解) 研究如何在分解表的过程中不丢失信息&#xff0c;也就是说&#xff0c;通过分解后的表可以无损地重建原始表。 2. BCNF (Boyce-Codd Normal Form, BCNF范式) &#xff08;1&…
阅读更多...
嵌入式学习-QT-Day06

嵌入式学习-QT-Day06

嵌入式学习-QT-Day06 六、多窗口编程 1、QMessageBox 消息对话框 2、QWidget类 3、parent参数 4、堆栈窗口&#xff08;QStackedWidget&#xff09; 5、新建自定义窗口类 6、对象传值 6.1 父对象 → 子对象 6.2 子对象 → 父对象 7、事件机制 8、QMainWindow主窗口类 8.1 QMenu…
阅读更多...
《战神：诸神黄昏》游戏运行时提示找不到gamede.dll文件怎么办？gamede.dll丢失的修复指南

《战神：诸神黄昏》游戏运行时提示找不到gamede.dll文件怎么办？gamede.dll丢失的修复指南

在沉浸于《战神&#xff1a;诸神黄昏》的壮阔世界时&#xff0c;突然弹出的“找不到gamede.dll文件”错误提示可能会让玩家措手不及。作为一名经验丰富的软件开发从业者&#xff0c;我深知这类问题对游戏体验的影响。今天&#xff0c;我将为大家详细解析gamede.dll文件丢失的原…
阅读更多...
1.系统学习-线性回归

1.系统学习-线性回归

系统学习-线性回归 前言线性回归介绍误差函数梯度下降梯度下降示例 回归问题常见的评价函数1. MAE, mean absolutely error2. MSE, mean squared error3. R square &#xff08;决定系数或R方&#xff09; 机器学习建模流程模型正则化拓展阅读作业 链接: 2.系统学习-逻辑回归 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023