数据结构【C语言】B树查找、插入、删除以及代码实现

衣食无忧博客 2024-01-29 1 0

文章目录

B树基本原理查找插入删除

代码实现

B树

基本原理

B树是一种平衡的多路查找树，结点最大的孩子数目称为B树的阶。例如2-3树是3阶B树，2-3-4树是4阶b树。一个m阶B树具有如下属性：

如果根结点不是叶子结点，则其至少有两颗子树。每一个非根的分支结点都有k-1个元素和k个孩子，其中ceil(m/2) ≤ k ≤ m。每一个叶子结点m都有k-1个元素，其中ceil(m/2) ≤ k ≤ m。所有叶子结点都位于同一层次。所有分支结点包含下列信息数据（n，

A_0

A0，

K_1

K1，

A_1

A1，

K_2

K2，

A_2

A2，…，

K_n

Kn，

A_n

An），其中：

K_i

Ki（i=1，2，…，n）为关键字，且

K_i

Ki <

K_i+1

Ki+1（i=1，2，…，n-1）；

A_i

Ai（i=0，1，2，…，n）为指向子树根结点的指针，且指针

−

A_i-1

Ai−1所指子树中所有结点的关键字均小于

K_i

Ki（i=1，2，…，n），

A_n

An所指子树中所有结点的关键字均大于

K_n

Kn，n（ceil(m/2)-1 ≤ n ≤ m-1）为关键字的个数（或n+1为子树的个数）。

查找

在m阶B树T上查找关键字Key，从根结点找起，在每个结点内做遍历查找，找到对应的关键字则返回对应关键字在结点中的序号，以及指向该结点的指针。若未找到，则返回关键字所在区间的子树的指针，继续在子树中查找。

插入

先依据查找算法找到对应关键字应在B树中的所在的位置，并将key值插入。检查该结点关键字个数是否超出规定（ceil(m/2) ≤ keyNum ≤ m-1）。若超出，则以结点中间关键字为界，之前的作为中间关键字的左子树，之后的作为中间关键字的右子树。将中间关键字插入到结点的父亲结点的相应位置。继续检查父亲结点的关键字个数是否满足要求。

删除

先依据查找算法找到对应关键字在B树中所在的位置。之后，判断该结点是否为叶子结点。

若是叶子结点：先直接删除该关键字，之后对该结点进行平衡判断，看关键字数目是否满足要求。若不是叶子结点：则判断该关键字的左子树或右子树是否富有（即关键字数目 > ceil(m/2)）。若左子树富有，则将左子树中提取最大关键字放到该结点中替换要删除的关键字。若右子树富有，则将右子树中提取最小关键字放到该结点中替换要删除的关键字。若左右子树都不富有，则合并左右子树。然后删除结点的关键字，再对该结点进行平衡判断。

平衡判断：若该结点的关键字数目不满足最小要求。则找到该关键字的右兄弟结点或左兄弟结点看是否富有。若右兄弟富有则进行左旋操作，若左兄弟富有则进行右旋操作。若都不富有，则将该结点和其左右兄弟的其中一个以及父亲结点中的分隔符合并。

代码实现

* @Author: Xyh4ng

* @Date: 2023-01-02 20:24:30

* @LastEditors: Xyh4ng

* @LastEditTime: 2023-01-05 20:17:06

* @Description:

#include

#define M 3 // B树的阶

#define MIN_KEYNUM (M + 1) / 2 - 1

typedef struct BTreeNode

{

int keyNum; // 结点中关键字的数量

struct BTreeNode *parent; // 指向双亲结点

struct Node // 存放关键字以及其孩子节点指针，正常结点最多存放m个孩子，但在插入判断时会多存放一个

{

int key;

struct BTreeNode *ptr;

} node[M + 1]; // key的0号单元未使用

} BTreeNode, *BTree;

typedef struct Result

{

int tag; // 查找成功的标志

BTreeNode *pt; // 指向查找到的结点

int i; // 结点在关键字中的序号

} Result;

int Search(BTree T, int K)

{

int i = 0;

for (int j = 1; j <= T->keyNum; j++)

{

if (T->node[j].key <= K)

{

i = j;

}

return i;

}

/* 在m阶B树T上查找关键字K，返回结果(pt,i,tag)。若查找成功，则特征值tag=1，指针pt所指结点中第i个关键字等于K；否则特征值tag=0，等于K的关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间。 */

Result SearchBTree(BTree T, int K)

{

BTree p = T, q = NULL; /* 初始化，p指向待查结点，q指向p的双亲 */

int found = 0;

int index = 0;

Result r;

while (p && !found)

{

index = Search(p, K); // p->node[index].key ≤ K < p->node[index+1].key

if (index > 0 && p->node[index].key == K)

found = 1;

else

{

q = p;

p = p->node[index].ptr;

}

r.i = index;

if (found) // 查找成功

{

r.tag = 1;

r.pt = p;

}

else

{

r.tag = 0;

r.pt = q;

}

return r;

}

void Insert(BTree *q, int key, BTree ap, int i)

{

for (int j = (*q)->keyNum; j > i; j--) // 空出(*q)->node[i+1]

{

(*q)->node[j + 1] = (*q)->node[j];

}

(*q)->node[i + 1].key = key;

(*q)->node[i + 1].ptr = ap;

(*q)->keyNum++;

}

// 将结点q分裂成两个结点，mid之前的结点保留，mid之后结点移入新生结点ap

void Split(BTree *q, BTree *ap)

{

int mid = (M + 1) / 2;

*ap = (BTree)malloc(sizeof(BTreeNode));

(*ap)->node[0].ptr = (*q)->node[mid].ptr;

if ((*ap)->node[0].ptr)

{

(*ap)->node[0].ptr->parent = *ap;

}

for (int i = mid + 1; i <= M; i++)

{

(*ap)->node[i - mid] = (*q)->node[i];

if ((*ap)->node[i - mid].ptr)

{

(*ap)->node[i - mid].ptr->parent = *ap;

}

(*ap)->keyNum = M - mid;

(*ap)->parent = (*q)->parent;

(*q)->keyNum = mid - 1;

}

// 生成含信息(T,r,ap)的新的根结点&T，原T和ap为子树指针

void NewRoot(BTree *T, int key, BTree ap)

{

BTree p;

p = (BTree)malloc(sizeof(BTreeNode));

p->node[0].ptr = *T; // 根结点孩子数最小为2，则将T作为左孩子，ap作为右孩子

*T = p;

if ((*T)->node[0].ptr)

{

(*T)->node[0].ptr->parent = *T;

}

(*T)->parent = NULL;

(*T)->keyNum = 1;

(*T)->node[1].key = key;

(*T)->node[1].ptr = ap;

if ((*T)->node[1].ptr)

{

(*T)->node[1].ptr->parent = *T;

}

/* 在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K的指针r。若引起结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B树。 */

void InseartBTree(BTree *T, int key, BTree q, int i)

{

BTree ap = NULL;

int finished = 0;

int rx = key; // 需要插入的关键字的值

int mid;

while (q && !finished)

{

Insert(&q, rx, ap, i);

if (q->keyNum < M)

finished = 1;

else // 结点关键字数超出规定

{

int mid = (M + 1) / 2; // 结点的中间关键字序号

rx = q->node[mid].key;

Split(&q, &ap); // 将q->key[mid+1..M],q->ptr[mid..M]移入新结点*ap

q = q->parent;

if (q)

i = Search(q, rx);

}

if (!finished)

{

NewRoot(T, rx, ap);

}

void Delete(BTree *q, int index)

{

for (int i = index; i <= (*q)->keyNum; i++)

{

(*q)->node[index] = (*q)->node[index + 1];

}

(*q)->keyNum--;

}

void LeftRotation(BTree *q, BTree *p, int i)

{

// 将父亲结点转移至q结点的末尾

(*q)->keyNum++;

(*q)->node[(*q)->keyNum].key = (*p)->node[i + 1].key;

// 将q结点的右兄弟的第一个关键字转移至父亲结点的分隔符位置

BTree rightBroPtr = (*p)->node[i + 1].ptr;

(*p)->node[i + 1].key = rightBroPtr->node[1].key;

// 将右结点的关键字前移

for (int j = 1; j < rightBroPtr->keyNum; j++)

{

rightBroPtr->node[j] = rightBroPtr->node[j + 1];

}

rightBroPtr->keyNum--;

}

void RightRotation(BTree *q, BTree *p, int i)

{

// 将q结点向后移动空出第一个关键字的位置

for (int j = (*q)->keyNum; j >= 1; j--)

{

(*q)->node[j + 1] = (*q)->node[j];

}

// 将父亲结点移动至q结点的第一个关键字的位置

(*q)->node[1].key = (*p)->node[i].key;

(*q)->node[1].ptr = NULL;

(*q)->keyNum++;

// 将左兄弟结点的最后一个关键字移动至父亲结点的分隔符位置

BTree leftBroPtr = (*p)->node[i - 1].ptr;

(*p)->node[i].key = leftBroPtr->node[leftBroPtr->keyNum].key;

leftBroPtr->keyNum--;

}

void BalanceCheck(BTree *q, int key);

void MergeNode(BTree *q, BTree *p, int i)

{

BTree rightBroPtr = NULL, leftBroPtr = NULL;

if (i + 1 <= (*p)->keyNum)

{

rightBroPtr = (*p)->node[i + 1].ptr;

}

if (i - 1 >= 0)

{

leftBroPtr = (*p)->node[i - 1].ptr;

}

if (rightBroPtr)

{

// 将父亲结点的分隔符移动至q结点的最后

(*q)->keyNum++;

(*q)->node[(*q)->keyNum].key = (*p)->node[i + 1].key;

// 将右兄弟结点都移动到q结点上

(*q)->node[(*q)->keyNum].ptr = rightBroPtr->node[0].ptr;

for (int j = 1; j <= rightBroPtr->keyNum; j++)

{

(*q)->keyNum++;

(*q)->node[(*q)->keyNum] = rightBroPtr->node[j];

}

// 将父亲结点的分隔符删除

int key = (*p)->node[i + 1].key;

for (int j = i + 1; j < (*p)->keyNum; j++)

{

(*p)->node[j] = (*p)->node[j + 1];

}

(*p)->keyNum--;

if (!(*p)->parent && !(*p)->keyNum)

{

// 判断父亲结点是否为根结点，且关键字为空

// 让q结点作为根结点

(*q)->parent = NULL;

(*p) = (*q);

}

BalanceCheck(p, key);

}

else if (leftBroPtr)

{

// 将父亲结点的分隔符移动至左兄弟结点的最后

leftBroPtr->keyNum++;

leftBroPtr->node[leftBroPtr->keyNum].key = (*p)->node[i].key;

// 将q结点都移动到左兄弟结点上

leftBroPtr->node[leftBroPtr->keyNum].ptr = (*q)->node[0].ptr;

for (int j = 1; j <= (*q)->keyNum; j++)

{

leftBroPtr->keyNum++;

leftBroPtr->node[leftBroPtr->keyNum] = (*q)->node[j];

}

// 将父亲结点的分隔符删除

int key = (*p)->node[i].key;

for (int j = i; j < (*p)->keyNum; j++)

{

(*p)->node[j] = (*p)->node[j + 1];

}

(*p)->keyNum--;

if (!(*p)->parent && !(*p)->keyNum)

{

// 判断父亲结点是否为根结点，且关键字为空

// 让q结点作为根结点

(*q)->parent = NULL;

(*p) = (*q);

}

BalanceCheck(p, key);

}

void BalanceCheck(BTree *q, int key)

{

if ((*q)->keyNum < MIN_KEYNUM) // 该结点不满足最小关键字数目要求

{

BTree p = (*q)->parent;

int i = Search(p, key); // 找到q结点在父亲结点中的索引

if (i + 1 <= p->keyNum && p->node[i + 1].ptr->keyNum > MIN_KEYNUM) // 看q结点的右兄弟是否存在多余结点

{

LeftRotation(q, &p, i);

}

else if (i - 1 >= 0 && p->node[i - 1].ptr->keyNum > MIN_KEYNUM) // 看q结点的左兄弟是否存在多余结点

{

RightRotation(q, &p, i);

}

else // q结点的左右兄弟都不存在多余结点

{

// 将q结点和其左右兄弟的其中一个以及父亲结点中的分隔符合并

MergeNode(q, &p, i);

}

void MergeBro(BTree *left, BTree *right)

{

if (!(*left)->node[((*left)->keyNum)].ptr)

{

// 如果左子树为叶子结点

(*left)->node[(*left)->keyNum].ptr = (*right)->node[0].ptr;

for (int j = 1; j <= (*right)->keyNum; j++)

{

(*left)->keyNum++;

(*left)->node[(*left)->keyNum] = (*right)->node[j];

}

else

{

// 左子树不是叶子结点，则先将左子树最后一个子结点和右子树第一个子结点合并

MergeBro(&(*left)->node[(*left)->keyNum].ptr, &(*right)->node[0].ptr);

for (int j = 1; j <= (*right)->keyNum; j++)

{

(*left)->keyNum++;

(*left)->node[(*left)->keyNum] = (*right)->node[j];

}

// 合并完对左子树关键字数目进行判断

if ((*left)->keyNum >= M)

{

int mid = (M + 1) / 2; // 结点的中间关键字序号

int rx = (*left)->node[mid].key;

BTree ap = NULL;

Split(&(*left), &ap); // 将q->key[mid+1..M],q->ptr[mid..M]移入新结点*ap

BTree p = (*left)->parent;

int i = Search(p, rx);

Insert(&p, rx, ap, i);

}

void DeleteBTreeNode(BTree *T, int key)

{

Result res = SearchBTree(*T, key);

if (res.tag) // 查找成功

{

// 判断该结点是否是叶子结点

if (!res.pt->node[res.i].ptr)

{

// 若是叶子结点，则直接删除，然后对该结点进行平衡判断

Delete(&res.pt, res.i);

BalanceCheck(&res.pt, key);

}

else

{

// 若不是叶子节点

BTree leftChildPtr = res.pt->node[res.i - 1].ptr;

BTree rightChildPtr = res.pt->node[res.i].ptr;

if (leftChildPtr->keyNum > MIN_KEYNUM) // 左子树富有，则将左子树中提取最大值放到该结点中替换要删除的关键字

{

res.pt->node[res.i].key = leftChildPtr->node[leftChildPtr->keyNum].key;

leftChildPtr->keyNum--;

}

else if (rightChildPtr->keyNum > MIN_KEYNUM) // 右子树富有，则将右子树中提取最小值放到该结点中替换要删除的关键字

{

res.pt->node[res.i].key = rightChildPtr->node[1].key;

for (int j = 1; j < rightChildPtr->keyNum; j++)

{

rightChildPtr->node[j] = rightChildPtr->node[j + 1];

}

rightChildPtr->keyNum--;

}

else // 左右子树都不富有，则合并左右子树

{

MergeBro(&leftChildPtr, &rightChildPtr);

// 删除结点的关键字

res.i = Search(res.pt, key); // 合并结点可能会改变结点中关键字的次序，重新查序

for (int j = res.i; j < res.pt->keyNum; j++)

{

res.pt->node[j] = res.pt->node[j + 1];

}

res.pt->keyNum--;

// 对结点进行平衡判断

BalanceCheck(&res.pt, key);

}

else // 查找失败

{

printf("您删除的元素不存在");

}

int main()

{

int r[16] = {22, 16, 41, 58, 8, 11, 12, 16, 17, 9, 23, 13, 52, 58, 59, 61};

BTree T = NULL;

Result s;

int i;

for (int i = 0; i < 16; i++)

{

s = SearchBTree(T, r[i]);

if (!s.tag)

InseartBTree(&T, r[i], s.pt, s.i);

}

while (1)

{

printf("\n请输入要删除的关键字: ");

scanf("%d", &i);

DeleteBTreeNode(&T, i);

}

参考文章

评论可见，请评论后查看内容，谢谢！！！评论后请刷新页面。

本文由用户于 2024-01-29 发布在夸智网，如有疑问，请联系我们。
本文链接：https://www.kuazhi.com/post/712889162.html

夸智网

数据结构【C语言】B树查找、插入、删除以及代码实现

工地人工智能机器人

b树 sql mysql B+树与索引

发表评论取消回复

夸智网

数据结构 【C语言】B树查找、插入、删除以及代码实现

工地人工智能机器人

b树 sql mysql B+树与索引

相关文章

发表评论取消回复

数据结构【C语言】B树查找、插入、删除以及代码实现