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

文章目录

前言
一、多路查找树（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;
}