330-B树的查询和插入

我就是我 2022-10-05 01:53 130阅读 0赞

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，用于存放分枝

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

  1. #include<iostream>
  2. using namespace std;
  4. #define M 5 //分路数
  5. #define MINITEM (M/2) // 最小分枝数 >=2
  6. #define MAXITEM (M-1) //最大分枝数
  8. typedef char KeyType;
  9. typedef struct {
  10.     } Record;//记录集
  11. typedef struct
  12. {
  14.     KeyType key;//关键码
  15.     Record* recptr;//元素类型
  16. }ElemType;// key_value
  18. struct BNode
  19. {
  21.     int num;//元素的个数
  22.     BNode* parent;//双亲的指针
  23.     ElemType data[M + 1];//元素的个数，相当于下标0,1,2,3,4,5,0下标是哨兵位，5下标是分裂用的
  24.     BNode* sub[M + 1];//分枝数，0,1,2,3,4,5
  25. };//B树的结点结构
  27. typedef struct
  28. {
  30.     BNode* root;//根节点
  31.     int cursize;//当前B树的结点个数
  32. }BTree;
  34. BNode* Buynode()//购买节点
  35. {
  37.     BNode* s = (BNode*)malloc(sizeof(BNode));
  38.     if (s == nullptr) exit(1);
  39.     memset(s, 0, sizeof(BNode));
  40.     return s;
  41. }
  42. void Freenode(BNode* p)//释放结点
  43. {
  45.     free(p);
  46. }

建立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查询函数

  1. typedef struct
  2. {
  4.     BNode* pnode;//指向一个结点
  5.     int index;//查找的结点在哪个位置
  6.     bool tag;//true;//false
  7. }Result;
  9. Result Find_Key(BTree* ptree, KeyType kx)
  10. {
  12.     Result res = {
  13.      nullptr,-1,false };//初始化
  14.     BNode* p = ptree->root;
  15.     while (p != nullptr)
  16.     {
  18.         p->data[0].key = kx;
  19.         int i = p->num;
  20.         while (kx < p->data[i].key) --i;
  21.         res.pnode = p;
  22.         res.index = i;
  23.         if (i > 0 && kx == p->data[i].key)
  24.         {
  26.             res.tag = true;
  27.             break;
  28.         }
  29.         p=p->sub[i];
  30.     }
  31.     return res;
  32. }

B树的初始化，插入函数

  1. void Init_BTree(BTree* ptree)
  2. {
  4.     assert(ptree != nullptr);
  5.     ptree->root = nullptr;
  6.     ptree->cursize = 0;
  7. }
  8. void Insert_Item(BNode* ptr, int pos, ElemType item, BNode* right)
  9. {
  11.     for (int i = ptr->num; i > pos; --i)
  12.     {
  14.         ptr->data[i + 1] = ptr->data[i];
  15.         ptr->sub[i + 1] = ptr->sub[i];
  16.     }
  17.     ptr->data[pos + 1] = item;
  18.     ptr->sub[pos + 1] = right;
  19.     if (right != nullptr) right->parent = ptr;
  20.     ptr->num + -1;
  21. }
  22. ElemType Move_Right(BNode* ptr, BNode* right)
  23. {
  25.     for (int j = 0, i = MINITEM + 1; i <= ptr->num; ++i, ++j)
  26.     {
  28.         right->data[j] = ptr->data[i];
  29.         right->sub[j] = ptr->sub[i];
  30.         if (right->sub[j] != nullptr)
  31.         {
  33.             right->sub[j]->parent = right;
  34.         }
  35.     }
  36.     ptr->num = MINITEM;
  37.     right->num = MINITEM;
  38.     right->parent = ptr->parent;
  39.     return right->data[0];
  40. }
  41. BNode* MakeRoot(BNode* left, BNode* right, ElemType item)
  42. {
  44.     BNode* newroot = Buynode();
  45.     newroot->data[1] = item;
  46.     newroot->sub[0] = left;
  47.     if (left != nullptr) left->parent = newroot;
  48.     newroot->sub[1] = right;
  49.     if (right != nullptr) right->parent = newroot;
  50.     newroot->num = 1;
  51.     newroot->parent = nullptr;
  52.     return newroot;
  53. }
  55. BNode* Splice(BNode* ptr)
  56. {
  58.     BNode* right = Buynode();
  59.     ElemType item = Move_Right(ptr, right);
  60.     if (ptr->parent == nullptr)
  61.     {
  63.         return MakeRoot(ptr, right, item);
  64.     }
  65.     BNode* pa = ptr->parent;
  66.     int pos = pa->num;
  67.     pa->data[0] = item;
  68.     while (item.key < pa->data[pos].key) --pos;
  70.     Insert_Item(pa, pos, item, right);
  71.     if (pa->num > MAXITEM)
  72.     {
  74.         return Splice(pa);
  75.     }
  76.     else
  77.     {
  79.         return nullptr;
  80.     }
  81. }
  82. bool Insert(BTree* ptree, ElemType item)
  83. {
  85.     assert(ptree != nullptr);
  86.     if (ptree->root == nullptr)
  87.     {
  89.         ptree->root = MakeRoot(NULL, NULL, item);
  90.         return true;
  91.     }
  92.     Result res = Find_Key(ptree, item.key);
  93.     if (res.tag) return false;
  94.     BNode* p = res.pnode;
  95.     int pos = res.index;
  96.     Insert_Item(p, pos, item, nullptr);
  97.     if (p->num > MAXITEM)
  98.     {
  100.         BNode* newroot = Splice(p);
  101.         if (newroot != nullptr)
  102.         {
  104.             ptree->root = newroot;
  105.         }
  106.     }
  107.     ptree->cursize += 1;
  108.     return true;
  109. }

书写主函数检测

  1. #include<iostream>
  2. #include<assert.h>
  3. using namespace std;
  5. #define M 5 //分路数
  6. #define MINITEM (M/2) // 最小分枝数 >=2
  7. #define MAXITEM (M-1) //最大分枝数
  9. typedef char KeyType;
  10. typedef struct {
  11.     } Record;//记录集
  12. typedef struct
  13. {
  15.     KeyType key;//关键码
  16.     Record* recptr;//元素类型
  17. }ElemType;// key_value
  19. struct BNode
  20. {
  22.     int num;//元素的个数
  23.     BNode* parent;//双亲的指针
  24.     ElemType data[M + 1];//元素的个数，相当于下标0,1,2,3,4,5,0下标是哨兵位，5下标是分裂用的
  25.     BNode* sub[M + 1];//分枝数，0,1,2,3,4,5
  26. };//B树的结点结构
  28. typedef struct
  29. {
  31.     BNode* root;//根节点
  32.     int cursize;//当前B树的结点个数
  33. }BTree;
  35. typedef struct
  36. {
  38.     BNode* pnode;//指向一个结点
  39.     int index;//查找的结点在哪个位置
  40.     bool tag;//true;//false
  41. }Result;
  43. BNode* Buynode()//购买节点
  44. {
  46.     BNode* s = (BNode*)malloc(sizeof(BNode));
  47.     if (s == nullptr) exit(1);
  48.     memset(s, 0, sizeof(BNode));
  49.     return s;
  50. }
  51. void Freenode(BNode* p)//释放结点
  52. {
  54.     free(p);
  55. }
  58. Result Find_Key(BTree* ptree, KeyType kx)
  59. {
  61.     Result res = {
  62.      nullptr,-1,false };//初始化
  63.     BNode* p = ptree->root;
  64.     while (p != nullptr)
  65.     {
  67.         p->data[0].key = kx;
  68.         int i = p->num;
  69.         while (kx < p->data[i].key) --i;
  70.         res.pnode = p;
  71.         res.index = i;
  72.         if (i > 0 && kx == p->data[i].key)
  73.         {
  75.             res.tag = true;
  76.             break;
  77.         }
  78.         p=p->sub[i];
  79.     }
  80.     return res;
  81. }
  83. void Init_BTree(BTree* ptree)
  84. {
  86.     assert(ptree != nullptr);
  87.     ptree->root = nullptr;
  88.     ptree->cursize = 0;
  89. }
  90. void Insert_Item(BNode* ptr, int pos, ElemType item, BNode* right)
  91. {
  93.     for (int i = ptr->num; i > pos; --i)
  94.     {
  96.         ptr->data[i + 1] = ptr->data[i];
  97.         ptr->sub[i + 1] = ptr->sub[i];
  98.     }
  99.     ptr->data[pos + 1] = item;
  100.     ptr->sub[pos + 1] = right;
  101.     if (right != nullptr) right->parent = ptr;
  102.     ptr->num +=1;
  103. }
  104. ElemType Move_Right(BNode* ptr, BNode* right)
  105. {
  107.     for (int j = 0, i = MINITEM + 1; i <= ptr->num; ++i, ++j)
  108.     {
  110.         right->data[j] = ptr->data[i];
  111.         right->sub[j] = ptr->sub[i];
  112.         if (right->sub[j] != nullptr)
  113.         {
  115.             right->sub[j]->parent = right;
  116.         }
  117.     }
  118.     ptr->num = MINITEM;
  119.     right->num = MINITEM;
  120.     right->parent = ptr->parent;
  121.     return right->data[0];
  122. }
  123. BNode* MakeRoot(BNode* left, BNode* right, ElemType item)
  124. {
  126.     BNode* newroot = Buynode();
  127.     newroot->data[1] = item;
  128.     newroot->sub[0] = left;
  129.     if (left != nullptr) left->parent = newroot;
  130.     newroot->sub[1] = right;
  131.     if (right != nullptr) right->parent = newroot;
  132.     newroot->num = 1;
  133.     newroot->parent = nullptr;
  134.     return newroot;
  135. }
  137. BNode* Splice(BNode* ptr)
  138. {
  140.     BNode* right = Buynode();
  141.     ElemType item = Move_Right(ptr, right);
  142.     if (ptr->parent == nullptr)
  143.     {
  145.         return MakeRoot(ptr, right, item);
  146.     }
  147.     BNode* pa = ptr->parent;
  148.     int pos = pa->num;
  149.     pa->data[0] = item;
  150.     while (item.key < pa->data[pos].key) --pos;
  152.     Insert_Item(pa, pos, item, right);
  153.     if (pa->num > MAXITEM)
  154.     {
  156.         return Splice(pa);
  157.     }
  158.     else
  159.     {
  161.         return nullptr;
  162.     }
  163. }
  164. bool Insert(BTree* ptree, ElemType item)
  165. {
  167.     assert(ptree != nullptr);
  168.     if (ptree->root == nullptr)
  169.     {
  171.         ptree->root = MakeRoot(NULL, NULL, item);
  172.         ptree->cursize+=1;
  173.         return true;
  174.     }
  175.     Result res = Find_Key(ptree, item.key);
  176.     if (res.tag) return false;
  177.     BNode* p = res.pnode;
  178.     int pos = res.index;
  179.     Insert_Item(p, pos, item, nullptr);
  180.     if (p->num > MAXITEM)
  181.     {
  183.         BNode* newroot = Splice(p);
  184.         if (newroot != nullptr)
  185.         {
  187.             ptree->root = newroot;
  188.         }
  189.     }
  190.     ptree->cursize += 1;
  191.     return true;
  192. }
  194. int main()
  195. {
  197.     char str[] = {
  198.      "qwertyuiopasdfghjklkzxcvbnm" };
  199.     int len = strlen(str);
  200.     BTree myt;
  201.     Init_BTree(&myt);
  202.     for (int i = 0; i < len; ++i)
  203.     {
  205.         ElemType item = {
  206.      str[i],nullptr };
  207.         cout << Insert(&myt, item);
  208.     }
  209.     Result res = Find_Key(&myt, 'x');
  210.     return 0;
  212. }

在这里插入图片描述

B树的中序遍历

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

  1. void InOrder(BNode* p)
  2. {
  4.     if (p == nullptr) return;
  5.     InOrder(p->sub[0]);
  6.     for (int i = 1; i <= p->num; ++i)
  7.     {
  9.         cout << p->data[i].key << " ";
  10.         InOrder(p->sub[i]);
  11.     }
  12. }
  13. void Inorder_BTree(BTree* ptree)
  14. {
  16.     assert(ptree != nullptr);
  17.     InOrder(ptree->root);
  18.     cout << endl;
  19. }

主函数如下

  1. int main()
  2. {
  4.     char str[] = {
  5.      "qwertyuiopasdfghjklkzxcvbnm" };
  6.     int len = strlen(str);
  7.     BTree myt;
  8.     Init_BTree(&myt);
  9.     for (int i = 0; i < len; ++i)
  10.     {
  12.         ElemType item = {
  13.      str[i],nullptr };
  14.         cout << Insert(&myt, item);
  15.     }
  16.     Inorder_BTree(&myt);
  17.     Result res = Find_Key(&myt, 'x');
  18.     return 0;
  19. }

运行截图如下

在这里插入图片描述

发表评论

表情：
评论列表 （有 0 条评论，130人围观）

还没有评论，来说两句吧...

相关阅读

    相关 B树、B+树和B*树

    一 B树的介绍 B-tree树即B树，B即Balanced，平衡的意思。有人把B-tree翻译成B-树，容易让人产生误解。会以为B-树是一种树，而B树又是另一种树。实际上

    Myth丶恋晨Myth丶恋晨/ 0 赞/ 668 阅读