【算法】- 查找 - 多路查找树（B树）

server/2024/10/9 5:56:51/

文章目录

  • 前言
  • 一、多路查找树（B树）
  • 二、2-3树的查找
    • 2-3树查找代码
  • 三、2-3树的插入
    • 2-3树代码
  • 2-3树代码
  • 总结

前言

上次我们学了如何用平衡二叉树来插入和查找。这些算法都是在内存中进行，若我们要操作的数据非常大，大到内存没办法处理，这时我们就需要访问在外部的存储设备中的数据，在每次访问外部数据是都是需要消耗一定的时间，所以我们应该减少访问外部次数，这样效率就会提高，这时也就可以采用B树的结构对数据进行访问。这里我们主讲2-3树

一、多路查找树（B树）

多路查找树：多路查找树，其每一个结点的孩子可以多余两个，且每一个结点处可以存储多个元素。

2-3树的结构体

//创建B树数据结构
typedef struct BTNode
{int keynum;//记录关键字的总个数struct BTNode* parent;//记录双亲结点struct Node//创建结构体数组用于存放关键字数据{int key;//存放关键字struct BTNode* ptr;//存放子树指针int cre;//存放指针向量}note[m+1];
}BTNode,*BTree;//查询结果状态结构体
typedef struct
{int i;//存放下标struct BTNode* pt;//查询到的地址（找到存储当前地址，没找到返回前一个地址）int tag;//查询成功与否标记（1为查找成功 0为查找失败）
}Result;

二、2-3树的查找

2-3树的查找，这里我们采用使用标记found表示找没找到为FALSE为没找到，为TRUE则表示为找到，当通过函数传进来2-3树T，则先判断是不是空树，而且found为FALSE则进行查找操作，查找操作比较简单，对结构体数组note进行遍历用i来存储没找到时前一个的下标，找到时当前的下标，在返回i这就得到了没找到时前一个的下标，这样就方便通过i进入子树进行查找，
如果i>0并且其下标的key值为要找的数值，则找到将found赋值为TRUE,否则这通过i进入其子树进行查找直到为NULL就退出循环。这也就完成了查找操作。

2-3树查找代码

//查询
int Search(BTree T, int key)
{int i = 0;int j;for (j = 1; j <= T->keynum; j++)if (T->note[j].key <= key)i = j;//找到则是key的下标，没找到则是key值上一个的下标return i;
}//查询B树
Result SearchBTree(BTree T, int key)
{int i = 0;BTree q;q = NULL;Result r;int found = FALSE;//标志 用于判断是否被找到while (T && !found){i = Search(T, key);if (i > 0 && T->note[i].key == key)found = TRUE;//被找到赋值为TRUEelse{q = T;T = T->note[i].ptr;//把找到最后一个数值的子树地址给T}}r.i = i;if (found)//如果被找到这记录查询状态{r.pt = T;r.tag = 1;}else{r.pt = q;r.tag = 0;}return r;
}

三、2-3树的插入

通过查找我们得到了，用查找状态的结构体，通过传入(2-3树)T，key(关键字)，i(要插入结点的下标)和p(要插入的地址)。我们这里通过finished来表示是否完成插入，我们先判断T是否为一颗空树，且finished为FALSE就进行插入操作，插入操作也是比较简单，将所有的数据向后移动，直到到了要插入为值，然后就将值赋值就行。插入完后我们还要判断是否上溢出，没有上溢出则将finished赋值为TRUE完成插入，有上溢出则要定义一个分割点取整个数组的中间值，然后就进行分割，用ap指针来接受分割出来的一半，设分割点为s = (m+1)/2（m这里是3），将s+1后面的数值全部赋值给ap指针，再将赋值的数值的双亲结点赋值为ap就行了，这样就完成了分割。再把p的指针赋值为p的双亲结点，这样分割点就完成了上移动。然后就是进行合并，创建一个结点将T和ap分别连接，就行代码较为简单，就是连接完后别忘了把以前的双亲结点赋值为新创建的结点

2-3树代码

//插入操作
void insert(BTree* T, int key, int i, BTree ap)
{int j;for (j = (*T)->keynum; j > i; j--){(*T)->note[j + 1] = (*T)->note[j];}(*T)->note[i + 1].key = key;(*T)->note[i + 1].cre = key;(*T)->note[i + 1].ptr = ap;(*T)->keynum++;
}//分割
void split(BTree* T, BTree* ap)
{int s = (m + 1) / 2;int i;*ap = (BTree)malloc(sizeof(BTNode));(*ap)->note[0].ptr = (*T)->note[s].ptr;for (i = s + 1; i <= m; i++){(*ap)->note[i - s] = (*T)->note[i];if ((*ap)->note[i - s].ptr)(*ap)->note[i - s].ptr->parent = *ap;}(*ap)->keynum = m - s;(*ap)->parent = (*T)->parent;(*T)->keynum = s - 1;
}//创建新结点
void NewRoot(BTree* T, int key, BTree ap)
{BTree p;p = (BTree)malloc(sizeof(BTNode));p->note[0].ptr = *T;*T = p;if ((*T)->note[0].ptr)(*T)->note[0].ptr->parent = *T;(*T)->parent = NULL;(*T)->note[1].key = key;(*T)->note[1].cre = key;(*T)->keynum = 1;(*T)->note[1].ptr = ap;if ((*T)->note[1].ptr)(*T)->note[1].ptr->parent = *T;}//插入B树
void InsertBTree(BTree* T, int key, BTree p, int i)
{int s;int rx = key;BTree ap = NULL;int finished = FALSE;//标记 判断是否已经完成插入while (p && !finished)//T不为空 并且没有被插入则进行插入操作{insert(&p,rx,i,ap);if (p->keynum < m)finished = TRUE;//插入成功else{s = (m + 1) / 2;//设置分割点rx = p->note[s].key;split(&p,&ap);//进行分割p = p->parent;if (p)i = Search(p, key);}}if (!finished)NewRoot(T,rx ,ap);
}

2-3树代码

#define _CRT_SECURE_NO_WARNINGS 1#define m 3
#define N 17
#define FALSE 0
#define TRUE 1#include <iostream>
#include <stdlib.h>
using namespace std;//创建B树数据结构
typedef struct BTNode
{int keynum;//记录关键字的总个数struct BTNode* parent;//记录双亲结点struct Node//创建结构体数组用于存放关键字数据{int key;//存放关键字struct BTNode* ptr;//存放子树指针int cre;//存放指针向量}note[m+1];
}BTNode,*BTree;//查询结果状态结构体
typedef struct
{int i;//存放下标struct BTNode* pt;//查询到的地址（找到存储当前地址，没找到返回前一个地址）int tag;//查询成功与否标记（1为查找成功 0为查找失败）
}Result;//查询
int Search(BTree T, int key)
{int i = 0;int j;for (j = 1; j <= T->keynum; j++)if (T->note[j].key <= key)i = j;//找到则是key的下标，没找到则是key值上一个的下标return i;
}//查询B树
Result SearchBTree(BTree T, int key)
{int i = 0;BTree q;q = NULL;Result r;int found = FALSE;//标志 用于判断是否被找到while (T && !found){i = Search(T, key);if (i > 0 && T->note[i].key == key)found = TRUE;//被找到赋值为TRUEelse{q = T;T = T->note[i].ptr;//把找到最后一个数值的子树地址给T}}r.i = i;if (found)//如果被找到这记录查询状态{r.pt = T;r.tag = 1;}else{r.pt = q;r.tag = 0;}return r;
}//插入操作
void insert(BTree* T, int key, int i, BTree ap)
{int j;for (j = (*T)->keynum; j > i; j--){(*T)->note[j + 1] = (*T)->note[j];}(*T)->note[i + 1].key = key;(*T)->note[i + 1].cre = key;(*T)->note[i + 1].ptr = ap;(*T)->keynum++;
}//分割
void split(BTree* T, BTree* ap)
{int s = (m + 1) / 2;int i;*ap = (BTree)malloc(sizeof(BTNode));(*ap)->note[0].ptr = (*T)->note[s].ptr;for (i = s + 1; i <= m; i++){(*ap)->note[i - s] = (*T)->note[i];if ((*ap)->note[i - s].ptr)(*ap)->note[i - s].ptr->parent = *ap;}(*ap)->keynum = m - s;(*ap)->parent = (*T)->parent;(*T)->keynum = s - 1;
}//创建新结点
void NewRoot(BTree* T, int key, BTree ap)
{BTree p;p = (BTree)malloc(sizeof(BTNode));p->note[0].ptr = *T;*T = p;if ((*T)->note[0].ptr)(*T)->note[0].ptr->parent = *T;(*T)->parent = NULL;(*T)->note[1].key = key;(*T)->note[1].cre = key;(*T)->keynum = 1;(*T)->note[1].ptr = ap;if ((*T)->note[1].ptr)(*T)->note[1].ptr->parent = *T;}//插入B树
void InsertBTree(BTree* T, int key, BTree p, int i)
{int s;int rx = key;BTree ap = NULL;int finished = FALSE;//标记 判断是否已经完成插入while (p && !finished)//T不为空 并且没有被插入则进行插入操作{insert(&p,rx,i,ap);if (p->keynum < m)finished = TRUE;//插入成功else{s = (m + 1) / 2;//设置分割点rx = p->note[s].key;split(&p,&ap);//进行分割p = p->parent;if (p)i = Search(p, key);}}if (!finished)NewRoot(T,rx ,ap);}void print(BTNode c, int i) /*  TraverseDSTable()调用的函数  */
{printf("(%d)", c.note[i].key);
}int main()
{int i;BTree T;T = NULL;//初始化B树Result s;//存放查询结果int r[N] = { 22,16,41,58,8,11,12,16,17,22,23,31,41,52,58,59,61 };//待查询插入数组for (i = 0; i < N; i++){s = SearchBTree(T, r[i]);//查找B树if (!s.tag)//如果没找到则进行插入操作{InsertBTree(&T, r[i], s.pt, s.i);}}printf("\n请输入待查找记录的关键字: ");scanf("%d", &i);s = SearchBTree(T, i);if (s.tag)print(*(s.pt), s.i);elseprintf("没找到");printf("\n");return 0;
}

总结

B树的应用，在内外存交换数据次数频繁，这就可以利用B树来增加效率


http://www.ppmy.cn/server/129128.html

相关文章

无人机高精度地形测量技术详解！

无人机高精度地形测量技术详解！

一、无人机技术 无人机作为搭载各种高精度传感器的平台&#xff0c;能够在不同高度和角度进行灵活飞行&#xff0c;覆盖各种复杂地形和环境&#xff0c;实现地表信息的全方位获取。 二、高精度传感器技术 GPS/GLONASS等卫星定位系统&#xff1a;无人机通过卫星定位系统实现高…
阅读更多...
聚观早报 | 苹果重磅更新；OpenAI推出ChatGPT Canvas

聚观早报 | 苹果重磅更新；OpenAI推出ChatGPT Canvas

聚观早报每日整理最值得关注的行业重点事件&#xff0c;帮助大家及时了解最新行业动态&#xff0c;每日读报&#xff0c;就读聚观365资讯简报。 整理丨Cutie 10月1日消息 苹果重磅更新 OpenAI推出ChatGPT Canvas Meta发布Movie Gen iQOO 13影像规格曝光 华为HarmonyOS N…
阅读更多...
S2B2C商城如何保证系统安全

S2B2C商城如何保证系统安全

前言 S2B2C商城系统通过一系列安全措施来保证系统的安全性&#xff0c;确保用户数据和交易信息的安全。以下是对这些安全措施的详细解析&#xff1a; 一、数据安全 加密技术&#xff1a;采用先进的加密技术和安全防范措施&#xff0c;保护用户数据和交易信息的安全&#xff…
阅读更多...
MySql表结构设计

MySql表结构设计

创建 create table 表名(字段1 字段类型 [约束] [comment 字段1注释],...) [comment 表注释];约束是作用于表中字段上的规则&#xff0c;用于限制存储在表中的数据。它的目的是保证数据库中数据的正确性、有效性和完整性。 约束描述关键字非空约束限制该字段不能为nullnot nu…
阅读更多...
JavaEE一条龙学习----前端体系介绍（一）

JavaEE一条龙学习----前端体系介绍（一）

随着AI技术的发展&#xff0c;人工智能大模型百花齐放&#xff0c;使得一些简单但耗时&#xff0c;复杂但重复的业务功能慢慢的交由人工智能完成&#xff0c;这对IT行业产生极大冲击&#xff0c;在其中&#xff0c;前端的唱衰人人可见&#xff0c;这使得后端程序员为了生计不得…
阅读更多...
【ubuntu】修改用户名、主机名、主文件夹名、登录名、密码

【ubuntu】修改用户名、主机名、主文件夹名、登录名、密码

目录 1.他们是什么 2.修改方法 2.1 修改用户密码 2.2 修改主机名 2.2.1 切换到root用户 2.2.2 修改名称 2.3 修改用户名 主文件夹名 登录名 2.2.1 sudoers 2.2.2 passwd 2.2.3 shadow 2.2.4 group 2.2.5 修改主文件夹名 3.重启 1.他们是什么 &#xff08;1&#xf…
阅读更多...
刷题训练之解决 FloodFill 算法

刷题训练之解决 FloodFill 算法

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;熟练掌握解决 FloodFill 算法。 > 毒鸡汤&#xff1a;学习&#xff0c;学习&#xff0c;再学习 ! 学&#xff0c;然后知不足。 > 专栏选自&#…
阅读更多...
【JavaEE】JVM

【JavaEE】JVM

&#x1f525;个人主页&#xff1a; 中草药 &#x1f525;专栏&#xff1a;【Java】登神长阶 史诗般的Java成神之路 &#x1f4d4; 一.概念 Java虚拟机&#xff08;JVM, Java Virtual Machine&#xff09;是Java平台的核心组件&#xff0c;它使得Java程序可以在任何安装了JVM的…
阅读更多...
最新文章

Copyright @ 2022~2023