2025年330-B树的查询和插入

330-B树的查询和插入B 树的静态索引 动态搜索结构 n 是当前结点关键码的个数 Ki 代表多个关键码 从小到大排序 如果 P1 有子树 子树的所有关键码均大于 K2 小于 K2 子树的特点 如何建立 B 树 自平衡树 B 树的结点结构 data 的下标 1 2 3 4 用于存放数据

大家好,我是讯享网,很高兴认识大家。

B树的静态索引

在这里插入图片描述
讯享网
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

动态搜索结构

在这里插入图片描述
n是当前结点关键码的个数
Ki代表多个关键码,从小到大排序。
如果P1有子树,子树的所有关键码均大于K2小于K2。
子树的特点:
在这里插入图片描述

如何建立B树

在这里插入图片描述
(自平衡树)
在这里插入图片描述
B树的结点结构
在这里插入图片描述
data的下标1,2,3,4,用于存放数据,0下标是哨兵位,5下标用于分裂
data下标1,2,3,4的存放的关键码依次增大
sub分枝的下标0,1,2,3,4,用于存放分枝

可以看做二叉树。上面的数据(关键码)代表双亲。其关键码大于左孩子而小于右孩子
相当于二叉排序树
如果有左分枝,必要有右分枝。关键码的左右都必须要有分枝
在这里插入图片描述

#include<iostream> using namespace std; #define M 5 //分路数 #define MINITEM (M/2) // 最小分枝数 >=2 #define MAXITEM (M-1) //最大分枝数 typedef char KeyType; typedef struct { 
   } Record;//记录集 typedef struct { 
    KeyType key;//关键码 Record* recptr;//元素类型 }ElemType;// key_value struct BNode { 
    int num;//元素的个数 BNode* parent;//双亲的指针 ElemType data[M + 1];//元素的个数,相当于下标0,1,2,3,4,5,0下标是哨兵位,5下标是分裂用的 BNode* sub[M + 1];//分枝数,0,1,2,3,4,5 };//B树的结点结构 typedef struct { 
    BNode* root;//根节点 int cursize;//当前B树的结点个数 }BTree; BNode* Buynode()//购买节点 { 
    BNode* s = (BNode*)malloc(sizeof(BNode)); if (s == nullptr) exit(1); memset(s, 0, sizeof(BNode)); return s; } void Freenode(BNode* p)//释放结点 { 
    free(p); } 

讯享网

建立B树图(查询,创建)

n是元素的个数,p代表双亲
d是data,s是sub
购买的结点构造如下
在这里插入图片描述
d是key_value,s是分枝

如果我们进行数据的插入
不断插入下列数据

在这里插入图片描述
我们先插入g,是空树,购买一个结点,g插入到data的1号位置。
在这里插入图片描述
我们插入k,要先进行查询,树中有没有这个k,所以查询就是首先把k放到哨兵位(d[0]),进行查询,拿k和g比较,k>g,在1号位置之后插入,也就是插入到2号位置。
在这里插入图片描述

当前,我们的个数是2,最大个数不能超过4。现在是OK的。
我们接着插入数据m,首先把m放到哨兵位,因为当前个数是2,所以从2下标开始比较,m大于k,我们把m放在3号位置。
在这里插入图片描述
我们再接着插入o,首先把o放到哨兵位,因为当前个数是3,所以从3号位置进行比较,o大于m,o放到4号位置,当前个数就是4了。n=4。
在这里插入图片描述
如果我们接着要插入e,把e放入哨兵位,因为当前个数是4,从4号位置开始和o比较,小于o,m,k,g,然后e和e相等,停下来了。我们看s0分枝空不空,如果不空,在分枝下面查,如果是空,则没有查到,e在0位置之后(1号位置)插入,其他的数据后移,n=5了,超过最大个数了,根节点root指向了当前这个结点(如下图)。要进行分裂了。
在这里插入图片描述

分裂的时候要遵循下面3点
在这里插入图片描述
首先购买一个节点,从第3位开始,m/2=2,2+1=3。k,m,o移到新节点的0,1,2
在这里插入图片描述
左右边的数据都是2个。第0里面的不算。
双亲都为空。
再购买一个节点作为根节点。
把k从0位置提到双亲结点的1号位置。
根节点root指向这个新的双亲结点。

在这里插入图片描述
我们再插入s。首先把s放到哨兵位,
在这里插入图片描述
因为当前根节点的个数是1,所以从1号位置开始比较,s大于k,我们看分枝s1空不空,不空,把s再放到哨兵位,
在这里插入图片描述
当前节点的元素个数是2,s从2号位置开始进行比较查询,s大于o,在2号位置之后插入数据,当前节点的个数是3。
在这里插入图片描述
我们再接着插入a
把a放在根节点的哨兵位,当前根节点的个数1,在1号位置比较,a小于k,和0号位置比较,a==a,看s0分枝空不空,不空,把a放在哨兵位,再查找,a小于g,e.等于a。s0是空的,我们把a插入到0位置之后,其他数据后移。当前个数是3。
在这里插入图片描述
我们再插入d,把d放到哨兵位,d小于k,d=d,我们看s0分枝空不空,不空,把d放到哨兵位,d从3位置比较,小于g,e,大于a,我们看分枝s1空不空,空!把数据后移,把d插入到2号位置。
在这里插入图片描述
我们再插入f,首先把f放到根节点的哨兵位,f小于k,f=f,在s0里面查询,放到哨兵位,f小于g,大于e,看s3空不空,空的,只能数据后移,f到4号位置。当前个数是5,超出范围,要进行分裂。我们再购买一个节点。
在这里插入图片描述
把efg移动到新的节点的0,1,2位置。都是同一个双亲。e给双亲,e和k比较,小于k,e=e,k后移,e在1号位置。然后分枝如下
在这里插入图片描述
如果我们插入c,c放在根节点的哨兵位,c小于k,e,c=c,s0不空,我们把c再放入哨兵位,查找,小于d,大于a,子树是空,d后移,我们把c插入到2号位置,
在这里插入图片描述
我们插入b,放到根节点的哨兵位进行查询,有2个数据,b小于k,e,b=b,我们看s0不空,放到哨兵位查询,b小于d,c,大于a,子树为空,c和d后移,在2号位置插入b,
在这里插入图片描述
我们再次插入数据h。
在这里插入图片描述
我们插入q,放到根节点的哨兵位,大于k,从s2查询,放到哨兵位,q小于s,大于o,s往后移,q放在3号位置。变成4个数据了。
在这里插入图片描述
我们再插入p,p大于k,和s比较,小于s,q,大于o,q,s后移,p放在3号位置,变成5个数据了。超出范围,进行分裂,购买一个兄弟结点。pqs移动到新结点的0,1,2,
在这里插入图片描述
我们把p往双亲走,大于k,p放在3号位置。
在这里插入图片描述
3结点4分枝。
我们再插入j,小于p,k,大于e,是s1分枝找,j大于h,放在4号位置。当前4个数据。
在这里插入图片描述
我们插入i,i小于p,k,i大于e,在s1查询,小于j,大于h,插入,已经5个数据了,要分裂。所以购买一个兄弟结点。hij移动到新结点的0,1,2
在这里插入图片描述
把h给双亲,小于p,k,大于e,k,p后移,sub也移动,4个数据5分枝。
在这里插入图片描述
等价下图
在这里插入图片描述

连级分裂

在这里插入图片描述
我们再插入z,大于p,走到s4的地方,大于s,插入s后面。
我们再插入x,大于p,走到s4的地方,小于z,大于s,插入进来。
在这里插入图片描述
我们再插入y,大于p,走到s4的地方,小于z大于x,插入,超过了最大元素的个数,要分裂,把xyz放到新结点的0,1,2,把x提到双亲,放在p的后面,5个数据6个分枝,根超出了!!!
在这里插入图片描述
我们再购买结点,我们把k,p,x放到新结点的0,1,2,3数据3分枝。
在这里插入图片描述
双亲为空,再建立一个结点,k放上去,在1位置,
在这里插入图片描述

B树的found查询函数

讯享网typedef struct { 
    BNode* pnode;//指向一个结点 int index;//查找的结点在哪个位置 bool tag;//true;//false }Result; Result Find_Key(BTree* ptree, KeyType kx) { 
    Result res = { 
    nullptr,-1,false };//初始化 BNode* p = ptree->root; while (p != nullptr) { 
    p->data[0].key = kx; int i = p->num; while (kx < p->data[i].key) --i; res.pnode = p; res.index = i; if (i > 0 && kx == p->data[i].key) { 
    res.tag = true; break; } p=p->sub[i]; } return res; } 

B树的初始化,插入函数

void Init_BTree(BTree* ptree) { 
    assert(ptree != nullptr); ptree->root = nullptr; ptree->cursize = 0; } void Insert_Item(BNode* ptr, int pos, ElemType item, BNode* right) { 
    for (int i = ptr->num; i > pos; --i) { 
    ptr->data[i + 1] = ptr->data[i]; ptr->sub[i + 1] = ptr->sub[i]; } ptr->data[pos + 1] = item; ptr->sub[pos + 1] = right; if (right != nullptr) right->parent = ptr; ptr->num + -1; } ElemType Move_Right(BNode* ptr, BNode* right) { 
    for (int j = 0, i = MINITEM + 1; i <= ptr->num; ++i, ++j) { 
    right->data[j] = ptr->data[i]; right->sub[j] = ptr->sub[i]; if (right->sub[j] != nullptr) { 
    right->sub[j]->parent = right; } } ptr->num = MINITEM; right->num = MINITEM; right->parent = ptr->parent; return right->data[0]; } BNode* MakeRoot(BNode* left, BNode* right, ElemType item) { 
    BNode* newroot = Buynode(); newroot->data[1] = item; newroot->sub[0] = left; if (left != nullptr) left->parent = newroot; newroot->sub[1] = right; if (right != nullptr) right->parent = newroot; newroot->num = 1; newroot->parent = nullptr; return newroot; } BNode* Splice(BNode* ptr) { 
    BNode* right = Buynode(); ElemType item = Move_Right(ptr, right); if (ptr->parent == nullptr) { 
    return MakeRoot(ptr, right, item); } BNode* pa = ptr->parent; int pos = pa->num; pa->data[0] = item; while (item.key < pa->data[pos].key) --pos; Insert_Item(pa, pos, item, right); if (pa->num > MAXITEM) { 
    return Splice(pa); } else { 
    return nullptr; } } bool Insert(BTree* ptree, ElemType item) { 
    assert(ptree != nullptr); if (ptree->root == nullptr) { 
    ptree->root = MakeRoot(NULL, NULL, item); return true; } Result res = Find_Key(ptree, item.key); if (res.tag) return false; BNode* p = res.pnode; int pos = res.index; Insert_Item(p, pos, item, nullptr); if (p->num > MAXITEM) { 
    BNode* newroot = Splice(p); if (newroot != nullptr) { 
    ptree->root = newroot; } } ptree->cursize += 1; return true; } 

书写主函数检测

讯享网#include<iostream> #include<assert.h> using namespace std; #define M 5 //分路数 #define MINITEM (M/2) // 最小分枝数 >=2 #define MAXITEM (M-1) //最大分枝数 typedef char KeyType; typedef struct { 
   } Record;//记录集 typedef struct { 
    KeyType key;//关键码 Record* recptr;//元素类型 }ElemType;// key_value struct BNode { 
    int num;//元素的个数 BNode* parent;//双亲的指针 ElemType data[M + 1];//元素的个数,相当于下标0,1,2,3,4,5,0下标是哨兵位,5下标是分裂用的 BNode* sub[M + 1];//分枝数,0,1,2,3,4,5 };//B树的结点结构 typedef struct { 
    BNode* root;//根节点 int cursize;//当前B树的结点个数 }BTree; typedef struct { 
    BNode* pnode;//指向一个结点 int index;//查找的结点在哪个位置 bool tag;//true;//false }Result; BNode* Buynode()//购买节点 { 
    BNode* s = (BNode*)malloc(sizeof(BNode)); if (s == nullptr) exit(1); memset(s, 0, sizeof(BNode)); return s; } void Freenode(BNode* p)//释放结点 { 
    free(p); } Result Find_Key(BTree* ptree, KeyType kx) { 
    Result res = { 
    nullptr,-1,false };//初始化 BNode* p = ptree->root; while (p != nullptr) { 
    p->data[0].key = kx; int i = p->num; while (kx < p->data[i].key) --i; res.pnode = p; res.index = i; if (i > 0 && kx == p->data[i].key) { 
    res.tag = true; break; } p=p->sub[i]; } return res; } void Init_BTree(BTree* ptree) { 
    assert(ptree != nullptr); ptree->root = nullptr; ptree->cursize = 0; } void Insert_Item(BNode* ptr, int pos, ElemType item, BNode* right) { 
    for (int i = ptr->num; i > pos; --i) { 
    ptr->data[i + 1] = ptr->data[i]; ptr->sub[i + 1] = ptr->sub[i]; } ptr->data[pos + 1] = item; ptr->sub[pos + 1] = right; if (right != nullptr) right->parent = ptr; ptr->num +=1; } ElemType Move_Right(BNode* ptr, BNode* right) { 
    for (int j = 0, i = MINITEM + 1; i <= ptr->num; ++i, ++j) { 
    right->data[j] = ptr->data[i]; right->sub[j] = ptr->sub[i]; if (right->sub[j] != nullptr) { 
    right->sub[j]->parent = right; } } ptr->num = MINITEM; right->num = MINITEM; right->parent = ptr->parent; return right->data[0]; } BNode* MakeRoot(BNode* left, BNode* right, ElemType item) { 
    BNode* newroot = Buynode(); newroot->data[1] = item; newroot->sub[0] = left; if (left != nullptr) left->parent = newroot; newroot->sub[1] = right; if (right != nullptr) right->parent = newroot; newroot->num = 1; newroot->parent = nullptr; return newroot; } BNode* Splice(BNode* ptr) { 
    BNode* right = Buynode(); ElemType item = Move_Right(ptr, right); if (ptr->parent == nullptr) { 
    return MakeRoot(ptr, right, item); } BNode* pa = ptr->parent; int pos = pa->num; pa->data[0] = item; while (item.key < pa->data[pos].key) --pos; Insert_Item(pa, pos, item, right); if (pa->num > MAXITEM) { 
    return Splice(pa); } else { 
    return nullptr; } } bool Insert(BTree* ptree, ElemType item) { 
    assert(ptree != nullptr); if (ptree->root == nullptr) { 
    ptree->root = MakeRoot(NULL, NULL, item); ptree->cursize+=1; return true; } Result res = Find_Key(ptree, item.key); if (res.tag) return false; BNode* p = res.pnode; int pos = res.index; Insert_Item(p, pos, item, nullptr); if (p->num > MAXITEM) { 
    BNode* newroot = Splice(p); if (newroot != nullptr) { 
    ptree->root = newroot; } } ptree->cursize += 1; return true; } int main() { 
    char str[] = { 
    "qwertyuiopasdfghjklkzxcvbnm" }; int len = strlen(str); BTree myt; Init_BTree(&myt); for (int i = 0; i < len; ++i) { 
    ElemType item = { 
    str[i],nullptr }; cout << Insert(&myt, item); } Result res = Find_Key(&myt, 'x'); return 0; } 

在这里插入图片描述

B树的中序遍历

在这里插入图片描述
中序遍历
abcdefghijkmopqsxyz
2数据3分枝

void InOrder(BNode* p) { 
    if (p == nullptr) return; InOrder(p->sub[0]); for (int i = 1; i <= p->num; ++i) { 
    cout << p->data[i].key << " "; InOrder(p->sub[i]); } } void Inorder_BTree(BTree* ptree) { 
    assert(ptree != nullptr); InOrder(ptree->root); cout << endl; } 

主函数如下

讯享网int main() { 
    char str[] = { 
    "qwertyuiopasdfghjklkzxcvbnm" }; int len = strlen(str); BTree myt; Init_BTree(&myt); for (int i = 0; i < len; ++i) { 
    ElemType item = { 
    str[i],nullptr }; cout << Insert(&myt, item); } Inorder_BTree(&myt); Result res = Find_Key(&myt, 'x'); return 0; } 

运行截图如下

在这里插入图片描述

小讯
上一篇 2025-04-09 20:03
下一篇 2025-04-02 20:35

相关推荐

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/81987.html