前言
上次我们学了如何用平衡二叉树来插入和查找。这些算法都是在内存中进行，若我们要操作的数据非常大，大到内存没办法处理，这时我们就需要访问在外部的存储设备中的数据，在每次访问外部数据是都是需要消耗一定的时间，所以我们应该减少访问外部次数，这样效率就会提高，这时也就可以采用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;//被找到赋值为TRUE
else
{
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;//被找到赋值为TRUE
else
{
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);
else
printf("没找到");
printf("\n");
return 0;
}
总结
B树的应用，在内外存交换数据次数频繁，这就可以利用B树来增加效率