B树删除(仅考虑阶数m3的情形注意叶节点合并时需要修改叶节点顺序链表的链接指针下文并未提到)删除仅在叶节点上进行,在叶节点上删除给定关键码后如果叶节点为根节点则删除操作结束(此时删除后的B树可能为空树).如果不为根节点且含有的关键码树ceil(m/2)[ceil表示向上取整]则删除操作结束如果删除的是叶节点最右侧的关键码还需用新的最右侧关键码沿叶节点至根节点的路径向上更新父节点指向叶节点父节点的父节点-指向父节点—–的索引项直到根节点的索引项被更新或被更新的索引项不是节点最右侧索引项为止。如果删除关键码的叶节点不为根节点且关键码数等于ceil(m/2)-1那么如果叶节点有右兄弟节点且右兄弟节点的关键码数大于等于ceil(m/2)1则把右兄弟节点最左侧关键码上移替代指向叶节点索引项中的关键码并把最左侧关键码复制至叶节点最右侧至此删除操作结束。如果右兄弟节点的关键码数等于ceil(m/2)则将被删叶节点完整拼接至右兄弟节点左侧删除叶节点和指向它的索引项然后若父节点为根或父节点不为根且关键码数大于等于ceil(m/2)则结束删除操作否则回溯至父节点继续处理。如果叶节点既无右兄弟节点也无左兄弟节点则删除父节点(根节点)并令根节点指针指向叶节点然后删除操作结束如果叶节点没有右兄弟节点但有左兄弟节点且左兄弟节点关键码数大于等于ceil(m/2)1,则将父节点指向左兄弟节点的索引项中的关键码下移至叶节点最左侧删除左兄弟节点最右侧关键码然后用左兄弟节点新的最右侧关键码填补父节点指向它的索引项中关键码位置随后同样的若叶节点最右侧关键码小于父节点最右侧关键码则向上更新祖先节点索引项然后删除操作结束。如果叶节点没有右兄弟节点但有左兄弟节点且左兄弟节点关键码数等于ceil(m/2)则将左兄弟节点完整拼接至叶节点左侧然后删除左兄弟节点和父节点中指向它的索引项随后若父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束(注意若叶节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项),否则用叶节点最右侧关键码更新父节点最右侧关键码然后回溯至父节点继续处理现设删除操作中当前节点的关键码数为ceil(m/2)-1且不是叶节点。那么如果它有右兄弟且右兄弟关键码数大于等于ceil(m/2)1则把右兄弟最左侧关键码上移取代父节点中指向当前节点的索引项中的关键码并将该关键码复制至当前节点最右侧此外还应将右兄弟最左侧指针移动至当前节点最右侧然后删除操作结束如果它有右兄弟,且右兄弟关键码数等于ceil(m/2),则当前节点拼接至右兄弟最左侧删去当前节点和父节点中指向它的索引项然后父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束否则回溯至父节点进一步处理。若果它没有右兄弟也无左兄弟则删除父节点(根节点)并令根节点指针指向当前节点然后删除操作结束若果它没有右兄弟但有左兄弟且左兄弟关键码数大于等于ceil(m/2)1,则将父节点中指向左兄弟的索引项中的关键码下移至当前节点最左侧删除左兄弟最右侧关键码并将左兄弟最右侧指针移至当前节点最左侧最后用左兄弟新的最右侧关键码填补父节点中指向它的索引项中的关键码所在位置删除操作结束(注意若当前节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项)如果它没有右兄弟但有左兄弟且左兄弟关键码数等于ceil(m/2),则将左兄弟完整拼接至当前节点左侧然后删除左兄弟和父节点中指向它的索引项随后若父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束(注意若当前节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项),否则用叶节点最右侧关键码更新父节点最右侧关键码然后回溯至父节点继续处理B树插入(仅考虑阶数m3的情形注意叶节点分裂时需要修改叶节点顺序链表的链接指针下文并未提到)在空树中插入直接新建根节点并填入关键码并令root和head指针指向根节点即可若在非空树中插入那么通过搜索在叶节点中找到插入位置直接插入若插入后叶节点关键码数小于等于m则插入结束否则叶节点从中间分裂为长度分别为floor((m1)/2)和ceil((m1)/2)的两部分长度为ceil((m1)/2)的部分是分裂后的原叶节点。如果原叶节点没有父节点则创建新根节点左右两关键码为两分裂部分的最大关键码左右两指针分别指向两分裂部分令根节点指针指向新根节点插入结束否则将最大关键码较小的分裂部分的指针及其最大关键码构成的二元组插入至原叶节点父节点中最大关键码较大的分裂部分对应的二元组的左侧父节点关键码指针数加一。如果插入二元组后父节点关键码数小于等于m则插入结束,否则以父节点为当前节点回溯至父节点现设插入过程中当前节点有m1个关键码且不为叶节点则和上述类似将当前节点分裂为长度分别为floor((m1)/2)和ceil((m1)/2)的两部分长度为ceil((m1)/2)的部分是分裂后的原当前节点如果原当前节点没有父节点则创建新根节点左右两关键码为两分裂部分的最大关键码左右两指针分别指向两分裂部分令根节点指针指向新根节点插入结束否则将最大关键码较小的分裂部分的指针及其最大关键码构成的二元组插入至原当前节点父节点中最大关键码较大的分裂部分对应的二元组的左侧父节点关键码指针数加一。如果插入二元组后父节点关键码数小于等于m则插入结束,否则以父节点为当前节点回溯至父节点C代码实现(如有错误欢迎指出)#include iostream #include utility #include stack #include vector #include random #include ctime #include algorithm using namespace std; const int M 4; //B树阶数 template typename T struct BPlusTreeNode { union { pairvectorT, BPlusTreeNodeT** keyandptr; //叶节点指针域和数据域 vectorpairT, BPlusTreeNodeT** keyptrmap; //分支节点索引项集合 }; enum flag { leaf, branch } NodeFlag; //节点标志叶节点or分支节点 BPlusTreeNode(flag N); ~BPlusTreeNode(); }; template typename T BPlusTreeNodeT::BPlusTreeNode(flag N) { NodeFlag N; if (NodeFlag leaf) { keyandptr new pairvectorT, BPlusTreeNodeT*(vectorT(), nullptr); } else { keyptrmap new vectorpairT, BPlusTreeNodeT*(); } } template typename T BPlusTreeNodeT::~BPlusTreeNode() { if (NodeFlag leaf) { delete keyandptr; } else { delete keyptrmap; } } template typename T pairtypename vectorpairT, BPlusTreeNodeT*::iterator, bool SearchBPlusTreeNode(BPlusTreeNodeT* ptr, typename vectorpairT, BPlusTreeNodeT*::iterator d) //返回值尾后表示失败,非尾后即为对应指针 { typename vectorpairT, BPlusTreeNodeT*::iterator m; //实参pair:尾后表示从第一指针后一指针开始搜索,非尾后表示从非尾后后一位置开始搜索 if (d ptr-keyptrmap-end()) { m ptr-keyptrmap-begin(); } else { m d; m; } if (m ptr-keyptrmap-end() || m-second ! nullptr) return { m, true }; return { ptr-keyptrmap-end(), false }; } template typename T T getMaxValueForLeaf(BPlusTreeNodeT* leaf) { typename vectorT::iterator t leaf-keyandptr-first.end() - 1; return *t; } template typename T bool leafKeyFromSmallToBig(BPlusTreeNodeT* leaf) { typename vectorT::iterator before leaf-keyandptr-first.begin(); typename vectorT::iterator after before 1; for (; after ! leaf-keyandptr-first.end(); before after, after) { if (*before *after) return false; } return true; } template typename T bool isBPlusTree(BPlusTreeNodeT* root, BPlusTreeNodeT* head) //判断给定多叉树是否为B树 { struct memory { BPlusTreeNodeT* p; typename vectorpairT, BPlusTreeNodeT*::iterator direction; T nodemin; memory(BPlusTreeNodeT* p, typename vectorpairT, BPlusTreeNodeT*::iterator d) :p(p), direction(d) {} }; T max_value_pre_leaf; BPlusTreeNodeT* leaf_list_run head; BPlusTreeNodeT* ptr root; typename vectorpairT, BPlusTreeNodeT*::iterator d; if (ptr-NodeFlag ! BPlusTreeNodeT::flag::leaf) d ptr-keyptrmap-end(); pairtypename vectorpairT, BPlusTreeNodeT*::iterator, bool t; BPlusTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int level 0; int beforelevel 0; T min; T max; while (true) { if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf ? true : (t SearchBPlusTreeNode(ptr, d)) pairtypename vectorpairT, BPlusTreeNodeT*::iterator, bool(ptr-keyptrmap-end(), true)) { if (ptr dest) { if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf) { if (!(1 ptr-keyandptr-first.size() ptr-keyandptr-first.size() M)) { cout 当前树只有根节点,但根节点子树数量不符合要求,非B树 endl; return false; } if (leafKeyFromSmallToBig(ptr) false) { cout 当前树只有根节点,但根节点关键码没有从小到大排列,非B树 endl; return false; } return true; } else { if (2 ptr-keyptrmap-size() ptr-keyptrmap-size() M) { typename vectorpairT, BPlusTreeNodeT*::iterator temp ptr-keyptrmap-end(); --temp; if (max temp-first) { --temp; if (min temp-first) { return true; } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树根节点子树数量不符合要求,非B树; return false; } } } else { if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf) { level; if (TF false) { beforelevel level; TF true; } else { if (level ! beforelevel) { cout 叶节点不在同一层,非B树 endl; return false; } } if ((M 1) / 2 ptr-keyandptr-first.size() ptr-keyandptr-first.size() M) { if (arrange.top().direction arrange.top().p-keyptrmap-begin()) { arrange.top().nodemin *(ptr-keyandptr-first.begin()); } min *(ptr-keyandptr-first.begin()); max *(--ptr-keyandptr-first.end()); } else { cout 当前树叶节点关键码数量不符合要求,非B树 endl; return false; } if (leafKeyFromSmallToBig(ptr) false) { cout 当前树叶节点关键码没有从小到大排列,非B树 endl; return false; } if (leaf_list_run ! nullptr ptr leaf_list_run) { if (leaf_list_run ! head) { if (*(leaf_list_run-keyandptr-first.begin()) max_value_pre_leaf) { cout 叶节点链表关键码非从小到大排列,非B树 endl; return false; } } max_value_pre_leaf getMaxValueForLeaf(leaf_list_run); leaf_list_run leaf_list_run-keyandptr-second; } else { cout 叶节点链表没有顺序链接所有叶节点,非B树 endl; return false; } } else { if ((M 1) / 2 ptr-keyptrmap-size() ptr-keyptrmap-size() M) { typename vectorpairT, BPlusTreeNodeT*::iterator temp ptr-keyptrmap-end(); --temp; if (max temp-first) { --temp; if (min temp-first) { min arrange.top().nodemin; arrange.pop(); if (arrange.top().direction arrange.top().p-keyptrmap-begin()) arrange.top().nodemin min; } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树分支节点子树数量不符合要求,非B树 endl; return false; } } --level; ptr arrange.top().p; d arrange.top().direction; } } else { if (t.second false) { cout 非叶节点的分支节点存在空子树,非B树 endl; return false; } if (d ptr-keyptrmap-end()) { arrange.push(memory(ptr, ptr-keyptrmap-begin())); ptr ptr-keyptrmap-begin()-second; level; } else { typename vectorpairT, BPlusTreeNodeT*::iterator temp t.first; --temp; if (max temp-first) { if (temp ! ptr-keyptrmap-begin()) { --temp; if (!(min temp-first)) { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } arrange.top().direction t.first; ptr t.first-second; } if (ptr-NodeFlag ! BPlusTreeNodeT::flag::leaf) { d ptr-keyptrmap-end(); } } } if (leaf_list_run ! nullptr) { cout 叶节点链表中叶节点数大于B树中叶节点数,非B树 endl; return false; } } template typename T bool compare(const pairT, BPlusTreeNodeT* left, const pairT, BPlusTreeNodeT* right) { return left.first right.first; } template typename T void updatemax(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, T key) //向上更新父节点索引项关键码 { while (stackforback.empty() false) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; if (temp stackforback.top().first-keyptrmap-end()) --temp; temp-first key; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { break; } stackforback.pop(); } } template typename T pairbool, typename vectorT::iterator BinarySearch(vectorT list, typename vectorT::iterator left, typename vectorT::iterator right, const T key) { while (left right) { int d right - left 1; typename vectorT::iterator mid; if (d % 2 1) { mid left d / 2; } else { mid left (d / 2 - 1); } if (key *mid) { if (mid list.begin()) { return { false, left }; } right mid - 1; } else if (key *mid) { left mid 1; } else { return { true, mid }; } } return { false, left }; } template typename T typename vectorpairT, BPlusTreeNodeT*::iterator Upper_Bound(const T key, vectorpairT, BPlusTreeNodeT* list) { typename vectorpairT, BPlusTreeNodeT*::iterator left list.begin(); typename vectorpairT, BPlusTreeNodeT*::iterator right list.end() - 1; while (left right) { int d right - left 1; typename vectorpairT, BPlusTreeNodeT*::iterator mid; if (d % 2 1) { mid left d / 2; } else { mid left (d / 2 - 1); } if (key (*mid).first) { if (mid list.begin()) { return left; } right mid - 1; } else { left mid 1; } } return left; } templatetypename T bool afterSplit(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* ptr, BPlusTreeNodeT* current) { if (stackforback.top().first-keyptrmap-size() M) { if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { stackforback.pop(); if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf) updatemax(stackforback, ptr-keyandptr-first.back()); else updatemax(stackforback, ptr-keyptrmap-back().first); } return true; } current stackforback.top().first; stackforback.pop(); return false; } template typename T void left_to_right_for_leaf(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { right-keyandptr-first.insert(right-keyandptr-first.begin(), mid-first); left-keyandptr-first.pop_back(); mid-first left-keyandptr-first.back(); } template typename T void right_to_left_for_leaf(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { left-keyandptr-first.push_back(*(right-keyandptr-first.begin())); mid-first *(right-keyandptr-first.begin()); right-keyandptr-first.erase(right-keyandptr-first.begin()); } template typename T void left_to_right_for_branch(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { right-keyptrmap-insert(right-keyptrmap-begin(), left-keyptrmap-back()); left-keyptrmap-pop_back(); mid-first left-keyptrmap-back().first; } template typename T void right_to_left_for_branch(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { left-keyptrmap-push_back(*(right-keyptrmap-begin())); mid-first right-keyptrmap-begin()-first; right-keyptrmap-erase(right-keyptrmap-begin()); } template typename T bool toRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { if (stackforback.top().second stackforback.top().first-keyptrmap-end() - 1) { if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if (stackforback.top().second stackforback.top().first-keyptrmap-end() - 1) { if ((stackforback.top().second 1)-second-keyandptr-first.size() M) { left_to_right_for_leaf(current, (stackforback.top().second 1)-second, stackforback.top().second); return true; } } } else { if (stackforback.top().second stackforback.top().first-keyptrmap-end() - 1) { if ((stackforback.top().second 1)-second-keyptrmap-size() M) { left_to_right_for_branch(current, (stackforback.top().second 1)-second, stackforback.top().second); return true; } } } } return false; } template typename T bool toLeft(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; if (temp ! stackforback.top().first-keyptrmap-begin()) { if (temp stackforback.top().first-keyptrmap-end()) --temp; if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if ((temp - 1)-second-keyandptr-first.size() M) { right_to_left_for_leaf((temp - 1)-second, current, temp - 1); if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { updatemax(stackforback, current-keyandptr-first.back()); } return true; } } else { if ((temp - 1)-second-keyptrmap-size() M) { right_to_left_for_branch((temp - 1)-second, current, temp - 1); if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { updatemax(stackforback, current-keyptrmap-back().first); } return true; } } } return false; } template typename T bool toLeftOrRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { if (toRight(stackforback, current)) return true; if (toLeft(stackforback, current)) return true; return false; } template typename T pairBPlusTreeNodeT*, BPlusTreeNodeT* BPlusInsert(BPlusTreeNodeT* root, BPlusTreeNodeT* head, const T key) //B树插入函数 { if (root nullptr) { root new BPlusTreeNodeT(BPlusTreeNodeT::flag::leaf); head root; root-keyandptr-first.push_back(key); return { root, head }; } else { BPlusTreeNodeT* current root; stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback; while (current-NodeFlag ! BPlusTreeNodeT::flag::leaf) { BPlusTreeNodeT* p nullptr; typename vectorpairT, BPlusTreeNodeT*::iterator scankey Upper_Bound(key, *(current-keyptrmap)); if (scankey current-keyptrmap-end()) { stackforback.push(make_pair(current, scankey)); --scankey; p scankey-second; while (p-NodeFlag ! BPlusTreeNodeT::flag::leaf) { typename vectorpairT, BPlusTreeNodeT*::iterator temp p-keyptrmap-end(); stackforback.push(make_pair(p, temp)); --temp; p temp-second; } current p; break; } if (scankey-first key) { cout 关键码 key 已存在,无法插入 endl; return { root, head }; } stackforback.push(make_pair(current, scankey)); current scankey-second; } { pairbool, typename vectorT::iterator result BinarySearch(current-keyandptr-first, current-keyandptr-first.begin(), current-keyandptr-first.end() - 1, key); if (result.first false) { current-keyandptr-first.insert(result.second, key); if (current-keyandptr-first.size() M) { if (current ! root key current-keyandptr-first.back()) updatemax(stackforback, current-keyandptr-first.back()); return { root, head }; } if (stackforback.empty() false) { if (toLeftOrRight(stackforback, current)) return { root, head }; } BPlusTreeNodeT* ptr new BPlusTreeNodeT(BPlusTreeNodeT::flag::leaf); ptr-keyandptr-first.insert(ptr-keyandptr-first.end(), current-keyandptr-first.end() - (M 1) / 2, current-keyandptr-first.end()); current-keyandptr-first.erase(current-keyandptr-first.end() - (M 1) / 2, current-keyandptr-first.end()); ptr-keyandptr-second current-keyandptr-second; current-keyandptr-second ptr; if (stackforback.empty() true) { root new BPlusTreeNodeT(BPlusTreeNodeT::flag::branch); root-keyptrmap-push_back(make_pair(current-keyandptr-first.back(), current)); root-keyptrmap-push_back(make_pair(ptr-keyandptr-first.back(), ptr)); return { root, head }; } typename vectorT::iterator temp ptr-keyandptr-first.end() - 1; if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { stackforback.top().first-keyptrmap-insert(stackforback.top().second, make_pair(*temp, ptr)); stackforback.top().second stackforback.top().first-keyptrmap-end(); (stackforback.top().second - 2)-first *(current-keyandptr-first.end() - 1); } else { stackforback.top().second stackforback.top().first-keyptrmap-insert(stackforback.top().second 1, make_pair(*temp, ptr)); --stackforback.top().second; stackforback.top().second-first *(current-keyandptr-first.end() - 1); } if (afterSplit(stackforback, ptr, current)) return { root, head }; while (true) { if (stackforback.empty() false) { if (toLeftOrRight(stackforback, current)) return { root, head }; } BPlusTreeNodeT* ptr new BPlusTreeNodeT(BPlusTreeNodeT::flag::branch); ptr-keyptrmap-insert(ptr-keyptrmap-end(), current-keyptrmap-end() - (M 1) / 2, current-keyptrmap-end()); current-keyptrmap-erase(current-keyptrmap-end() - (M 1) / 2, current-keyptrmap-end()); if (stackforback.empty() true) { root new BPlusTreeNodeT(BPlusTreeNodeT::flag::branch); root-keyptrmap-push_back(make_pair(current-keyptrmap-back().first, current)); root-keyptrmap-push_back(make_pair(ptr-keyptrmap-back().first, ptr)); return { root, head }; } typename vectorpairT, BPlusTreeNodeT*::iterator temp ptr-keyptrmap-end() - 1; if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { stackforback.top().first-keyptrmap-insert(stackforback.top().second, make_pair(temp-first, ptr)); stackforback.top().second stackforback.top().first-keyptrmap-end(); (stackforback.top().second - 2)-first current-keyptrmap-back().first; } else { stackforback.top().second stackforback.top().first-keyptrmap-insert(stackforback.top().second 1, make_pair(temp-first, ptr)); --stackforback.top().second; stackforback.top().second-first current-keyptrmap-back().first; } if (afterSplit(stackforback, ptr, current)) return { root, head }; } } else { cout 关键码 key 已存在,无法插入 endl; return { root, head }; } } } } template typename T bool afterMerge(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* root, BPlusTreeNodeT* current, const typename vectorpairT, BPlusTreeNodeT*::iterator temp, const T key) { if (stackforback.top().first root || stackforback.top().first-keyptrmap-size() (M 1) / 2) { if (stackforback.top().first root root-keyptrmap-size() 1) { BPlusTreeNodeT* temp_ptr root-keyptrmap-front().second; delete root; root temp_ptr; } else { if (current nullptr) { if (temp-second-NodeFlag BPlusTreeNodeT::flag::leaf) { if (temp-second-keyandptr-first.back() key) { stackforback.pop(); updatemax(stackforback, temp-second-keyandptr-first.back()); } } else { if (temp-second-keyptrmap-back().first key) { stackforback.pop(); updatemax(stackforback, temp-second-keyptrmap-back().first); } } } } return true; } current stackforback.top().first; stackforback.pop(); return false; } template typename T bool borrowFromRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if (temp-second-keyandptr-first.size() (M 1) / 2 1) { right_to_left_for_leaf(current, temp-second, stackforback.top().second); return true; } } else { if (temp-second-keyptrmap-size() (M 1) / 2 1) { right_to_left_for_branch(current, temp-second, stackforback.top().second); return true; } } } return false; } template typename T bool borrowFromLeft(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current, const T key) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; if (temp ! stackforback.top().first-keyptrmap-begin()) { --temp; if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if (temp-second-keyandptr-first.size() (M 1) / 2 1) { left_to_right_for_leaf(temp-second, current, temp); if (current-keyandptr-first.back() key) updatemax(stackforback, current-keyandptr-first.back()); return true; } } else { if (temp-second-keyptrmap-size() (M 1) / 2 1) { left_to_right_for_branch(temp-second, current, temp); if (current-keyptrmap-back().first key) updatemax(stackforback, current-keyptrmap-back().first); return true; } } } return false; } template typename T bool borrowFromLeftOrRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current, const T key) { if (borrowFromRight(stackforback, current)) return true; if (borrowFromLeft(stackforback, current, key)) return true; return false; } template typename T pairBPlusTreeNodeT*, BPlusTreeNodeT* BPlusDelete(BPlusTreeNodeT* root, BPlusTreeNodeT* head, const T key) //B树删除函数,root根节点指针,head叶节点顺序链头节点指针 { BPlusTreeNodeT* current root; stackpairBPlusTreeNodeT*, vectorpairT, BPlusTreeNodeT*::iterator stackforback; while (current-NodeFlag ! BPlusTreeNodeT::flag::leaf) { typename vectorpairT, BPlusTreeNodeT*::iterator scankey Upper_Bound(key, *(current-keyptrmap)); if (scankey current-keyptrmap-end()) { cout 关键码不存在删除失败 endl; return { root, head }; } stackforback.push(make_pair(current, scankey)); current scankey-second; } { pairbool, typename vectorT::iterator result BinarySearch(current-keyandptr-first, current-keyandptr-first.begin(), current-keyandptr-first.end() - 1, key); if (result.first false) { cout 关键码不存在删除失败 endl; return { root, head }; } current-keyandptr-first.erase(result.second); } if (stackforback.empty() true) { if (current-keyandptr-first.empty() true) { delete current; return { nullptr, nullptr }; } return { current, current }; } if (current-keyandptr-first.size() (M 1) / 2) { if (current-keyandptr-first.back() key) updatemax(stackforback, current-keyandptr-first.back()); return { root, head }; } if (borrowFromLeftOrRight(stackforback, current, key)) { return { root, head }; } typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { current-keyandptr-first.insert(current-keyandptr-first.end(), temp-second-keyandptr-first.begin(), temp-second-keyandptr-first.end()); current-keyandptr-second temp-second-keyandptr-second; delete temp-second; stackforback.top().first-keyptrmap-erase(temp); stackforback.top().second-first current-keyandptr-first.back(); } else { temp temp - 2; temp-second-keyandptr-first.insert(temp-second-keyandptr-first.end(), current-keyandptr-first.begin(), current-keyandptr-first.end()); temp-second-keyandptr-second current-keyandptr-second; temp-first temp-second-keyandptr-first.back(); delete current; current nullptr; stackforback.top().first-keyptrmap-erase(stackforback.top().second); } if (afterMerge(stackforback, root, current, temp, key)) return { root, head }; while (true) { if (borrowFromLeftOrRight(stackforback, current, key)) { return { root, head }; } typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { current-keyptrmap-insert(current-keyptrmap-end(), temp-second-keyptrmap-begin(), temp-second-keyptrmap-end()); delete temp-second; stackforback.top().second-first current-keyptrmap-back().first; stackforback.top().first-keyptrmap-erase(temp); } else { temp temp - 2; temp-second-keyptrmap-insert(temp-second-keyptrmap-end(), current-keyptrmap-begin(), current-keyptrmap-end()); temp-first temp-second-keyptrmap-back().first; delete current; stackforback.top().first-keyptrmap-erase(stackforback.top().second); typename vectorpairT, BPlusTreeNodeT*::iterator it temp-second-keyptrmap-end() - 1; current nullptr; } if (afterMerge(stackforback, root, current, temp, key)) return { root, head }; } } int main() { const int N 2000; vectorint seq(N); for (int i 0; i N; i) { seq[i] i 1; } shuffle(seq.begin(), seq.end(), default_random_engine()); BPlusTreeNodeint* root nullptr; BPlusTreeNodeint* head nullptr; for (vectorint::const_iterator p seq.cbegin(); p ! seq.cend(); p) { cout 插入节点 *p endl; pairBPlusTreeNodeint*, BPlusTreeNodeint* temp BPlusInsert(root, head, *p); root temp.first; head temp.second; if (isBPlusTree(root, head)) { cout 当前树为B树 endl; } else { cout 错误,当前树不为B树! endl; exit(-1); } cout endl; } for (vectorint::const_iterator p seq.cbegin(); p ! seq.cend(); p) { cout 删除节点 *p endl; pairBPlusTreeNodeint*, BPlusTreeNodeint* temp BPlusDelete(root, head, *p); root temp.first; head temp.second; if (root nullptr head nullptr) cout NULL; else { if (isBPlusTree(root, head)) { cout 当前树为B树 endl; } else { cout 错误,当前树不为B树! endl; exit(-1); } } cout endl; } return 0; }
B+树的插入与删除
B树删除(仅考虑阶数m3的情形注意叶节点合并时需要修改叶节点顺序链表的链接指针下文并未提到)删除仅在叶节点上进行,在叶节点上删除给定关键码后如果叶节点为根节点则删除操作结束(此时删除后的B树可能为空树).如果不为根节点且含有的关键码树ceil(m/2)[ceil表示向上取整]则删除操作结束如果删除的是叶节点最右侧的关键码还需用新的最右侧关键码沿叶节点至根节点的路径向上更新父节点指向叶节点父节点的父节点-指向父节点—–的索引项直到根节点的索引项被更新或被更新的索引项不是节点最右侧索引项为止。如果删除关键码的叶节点不为根节点且关键码数等于ceil(m/2)-1那么如果叶节点有右兄弟节点且右兄弟节点的关键码数大于等于ceil(m/2)1则把右兄弟节点最左侧关键码上移替代指向叶节点索引项中的关键码并把最左侧关键码复制至叶节点最右侧至此删除操作结束。如果右兄弟节点的关键码数等于ceil(m/2)则将被删叶节点完整拼接至右兄弟节点左侧删除叶节点和指向它的索引项然后若父节点为根或父节点不为根且关键码数大于等于ceil(m/2)则结束删除操作否则回溯至父节点继续处理。如果叶节点既无右兄弟节点也无左兄弟节点则删除父节点(根节点)并令根节点指针指向叶节点然后删除操作结束如果叶节点没有右兄弟节点但有左兄弟节点且左兄弟节点关键码数大于等于ceil(m/2)1,则将父节点指向左兄弟节点的索引项中的关键码下移至叶节点最左侧删除左兄弟节点最右侧关键码然后用左兄弟节点新的最右侧关键码填补父节点指向它的索引项中关键码位置随后同样的若叶节点最右侧关键码小于父节点最右侧关键码则向上更新祖先节点索引项然后删除操作结束。如果叶节点没有右兄弟节点但有左兄弟节点且左兄弟节点关键码数等于ceil(m/2)则将左兄弟节点完整拼接至叶节点左侧然后删除左兄弟节点和父节点中指向它的索引项随后若父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束(注意若叶节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项),否则用叶节点最右侧关键码更新父节点最右侧关键码然后回溯至父节点继续处理现设删除操作中当前节点的关键码数为ceil(m/2)-1且不是叶节点。那么如果它有右兄弟且右兄弟关键码数大于等于ceil(m/2)1则把右兄弟最左侧关键码上移取代父节点中指向当前节点的索引项中的关键码并将该关键码复制至当前节点最右侧此外还应将右兄弟最左侧指针移动至当前节点最右侧然后删除操作结束如果它有右兄弟,且右兄弟关键码数等于ceil(m/2),则当前节点拼接至右兄弟最左侧删去当前节点和父节点中指向它的索引项然后父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束否则回溯至父节点进一步处理。若果它没有右兄弟也无左兄弟则删除父节点(根节点)并令根节点指针指向当前节点然后删除操作结束若果它没有右兄弟但有左兄弟且左兄弟关键码数大于等于ceil(m/2)1,则将父节点中指向左兄弟的索引项中的关键码下移至当前节点最左侧删除左兄弟最右侧关键码并将左兄弟最右侧指针移至当前节点最左侧最后用左兄弟新的最右侧关键码填补父节点中指向它的索引项中的关键码所在位置删除操作结束(注意若当前节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项)如果它没有右兄弟但有左兄弟且左兄弟关键码数等于ceil(m/2),则将左兄弟完整拼接至当前节点左侧然后删除左兄弟和父节点中指向它的索引项随后若父节点为根节点或父节点不为根节点且关键码数大于等于ceil(m/2)则删除操作结束(注意若当前节点最右侧关键码小于父节点最右侧关键码则应向上更新祖先节点索引项),否则用叶节点最右侧关键码更新父节点最右侧关键码然后回溯至父节点继续处理B树插入(仅考虑阶数m3的情形注意叶节点分裂时需要修改叶节点顺序链表的链接指针下文并未提到)在空树中插入直接新建根节点并填入关键码并令root和head指针指向根节点即可若在非空树中插入那么通过搜索在叶节点中找到插入位置直接插入若插入后叶节点关键码数小于等于m则插入结束否则叶节点从中间分裂为长度分别为floor((m1)/2)和ceil((m1)/2)的两部分长度为ceil((m1)/2)的部分是分裂后的原叶节点。如果原叶节点没有父节点则创建新根节点左右两关键码为两分裂部分的最大关键码左右两指针分别指向两分裂部分令根节点指针指向新根节点插入结束否则将最大关键码较小的分裂部分的指针及其最大关键码构成的二元组插入至原叶节点父节点中最大关键码较大的分裂部分对应的二元组的左侧父节点关键码指针数加一。如果插入二元组后父节点关键码数小于等于m则插入结束,否则以父节点为当前节点回溯至父节点现设插入过程中当前节点有m1个关键码且不为叶节点则和上述类似将当前节点分裂为长度分别为floor((m1)/2)和ceil((m1)/2)的两部分长度为ceil((m1)/2)的部分是分裂后的原当前节点如果原当前节点没有父节点则创建新根节点左右两关键码为两分裂部分的最大关键码左右两指针分别指向两分裂部分令根节点指针指向新根节点插入结束否则将最大关键码较小的分裂部分的指针及其最大关键码构成的二元组插入至原当前节点父节点中最大关键码较大的分裂部分对应的二元组的左侧父节点关键码指针数加一。如果插入二元组后父节点关键码数小于等于m则插入结束,否则以父节点为当前节点回溯至父节点C代码实现(如有错误欢迎指出)#include iostream #include utility #include stack #include vector #include random #include ctime #include algorithm using namespace std; const int M 4; //B树阶数 template typename T struct BPlusTreeNode { union { pairvectorT, BPlusTreeNodeT** keyandptr; //叶节点指针域和数据域 vectorpairT, BPlusTreeNodeT** keyptrmap; //分支节点索引项集合 }; enum flag { leaf, branch } NodeFlag; //节点标志叶节点or分支节点 BPlusTreeNode(flag N); ~BPlusTreeNode(); }; template typename T BPlusTreeNodeT::BPlusTreeNode(flag N) { NodeFlag N; if (NodeFlag leaf) { keyandptr new pairvectorT, BPlusTreeNodeT*(vectorT(), nullptr); } else { keyptrmap new vectorpairT, BPlusTreeNodeT*(); } } template typename T BPlusTreeNodeT::~BPlusTreeNode() { if (NodeFlag leaf) { delete keyandptr; } else { delete keyptrmap; } } template typename T pairtypename vectorpairT, BPlusTreeNodeT*::iterator, bool SearchBPlusTreeNode(BPlusTreeNodeT* ptr, typename vectorpairT, BPlusTreeNodeT*::iterator d) //返回值尾后表示失败,非尾后即为对应指针 { typename vectorpairT, BPlusTreeNodeT*::iterator m; //实参pair:尾后表示从第一指针后一指针开始搜索,非尾后表示从非尾后后一位置开始搜索 if (d ptr-keyptrmap-end()) { m ptr-keyptrmap-begin(); } else { m d; m; } if (m ptr-keyptrmap-end() || m-second ! nullptr) return { m, true }; return { ptr-keyptrmap-end(), false }; } template typename T T getMaxValueForLeaf(BPlusTreeNodeT* leaf) { typename vectorT::iterator t leaf-keyandptr-first.end() - 1; return *t; } template typename T bool leafKeyFromSmallToBig(BPlusTreeNodeT* leaf) { typename vectorT::iterator before leaf-keyandptr-first.begin(); typename vectorT::iterator after before 1; for (; after ! leaf-keyandptr-first.end(); before after, after) { if (*before *after) return false; } return true; } template typename T bool isBPlusTree(BPlusTreeNodeT* root, BPlusTreeNodeT* head) //判断给定多叉树是否为B树 { struct memory { BPlusTreeNodeT* p; typename vectorpairT, BPlusTreeNodeT*::iterator direction; T nodemin; memory(BPlusTreeNodeT* p, typename vectorpairT, BPlusTreeNodeT*::iterator d) :p(p), direction(d) {} }; T max_value_pre_leaf; BPlusTreeNodeT* leaf_list_run head; BPlusTreeNodeT* ptr root; typename vectorpairT, BPlusTreeNodeT*::iterator d; if (ptr-NodeFlag ! BPlusTreeNodeT::flag::leaf) d ptr-keyptrmap-end(); pairtypename vectorpairT, BPlusTreeNodeT*::iterator, bool t; BPlusTreeNodeT* const dest ptr; stackmemory arrange; bool TF false; int level 0; int beforelevel 0; T min; T max; while (true) { if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf ? true : (t SearchBPlusTreeNode(ptr, d)) pairtypename vectorpairT, BPlusTreeNodeT*::iterator, bool(ptr-keyptrmap-end(), true)) { if (ptr dest) { if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf) { if (!(1 ptr-keyandptr-first.size() ptr-keyandptr-first.size() M)) { cout 当前树只有根节点,但根节点子树数量不符合要求,非B树 endl; return false; } if (leafKeyFromSmallToBig(ptr) false) { cout 当前树只有根节点,但根节点关键码没有从小到大排列,非B树 endl; return false; } return true; } else { if (2 ptr-keyptrmap-size() ptr-keyptrmap-size() M) { typename vectorpairT, BPlusTreeNodeT*::iterator temp ptr-keyptrmap-end(); --temp; if (max temp-first) { --temp; if (min temp-first) { return true; } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树根节点子树数量不符合要求,非B树; return false; } } } else { if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf) { level; if (TF false) { beforelevel level; TF true; } else { if (level ! beforelevel) { cout 叶节点不在同一层,非B树 endl; return false; } } if ((M 1) / 2 ptr-keyandptr-first.size() ptr-keyandptr-first.size() M) { if (arrange.top().direction arrange.top().p-keyptrmap-begin()) { arrange.top().nodemin *(ptr-keyandptr-first.begin()); } min *(ptr-keyandptr-first.begin()); max *(--ptr-keyandptr-first.end()); } else { cout 当前树叶节点关键码数量不符合要求,非B树 endl; return false; } if (leafKeyFromSmallToBig(ptr) false) { cout 当前树叶节点关键码没有从小到大排列,非B树 endl; return false; } if (leaf_list_run ! nullptr ptr leaf_list_run) { if (leaf_list_run ! head) { if (*(leaf_list_run-keyandptr-first.begin()) max_value_pre_leaf) { cout 叶节点链表关键码非从小到大排列,非B树 endl; return false; } } max_value_pre_leaf getMaxValueForLeaf(leaf_list_run); leaf_list_run leaf_list_run-keyandptr-second; } else { cout 叶节点链表没有顺序链接所有叶节点,非B树 endl; return false; } } else { if ((M 1) / 2 ptr-keyptrmap-size() ptr-keyptrmap-size() M) { typename vectorpairT, BPlusTreeNodeT*::iterator temp ptr-keyptrmap-end(); --temp; if (max temp-first) { --temp; if (min temp-first) { min arrange.top().nodemin; arrange.pop(); if (arrange.top().direction arrange.top().p-keyptrmap-begin()) arrange.top().nodemin min; } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } else { cout 当前树分支节点子树数量不符合要求,非B树 endl; return false; } } --level; ptr arrange.top().p; d arrange.top().direction; } } else { if (t.second false) { cout 非叶节点的分支节点存在空子树,非B树 endl; return false; } if (d ptr-keyptrmap-end()) { arrange.push(memory(ptr, ptr-keyptrmap-begin())); ptr ptr-keyptrmap-begin()-second; level; } else { typename vectorpairT, BPlusTreeNodeT*::iterator temp t.first; --temp; if (max temp-first) { if (temp ! ptr-keyptrmap-begin()) { --temp; if (!(min temp-first)) { cout 当前树不是 M 路搜索树,非B树 endl; return false; } } } else { cout 当前树不是 M 路搜索树,非B树 endl; return false; } arrange.top().direction t.first; ptr t.first-second; } if (ptr-NodeFlag ! BPlusTreeNodeT::flag::leaf) { d ptr-keyptrmap-end(); } } } if (leaf_list_run ! nullptr) { cout 叶节点链表中叶节点数大于B树中叶节点数,非B树 endl; return false; } } template typename T bool compare(const pairT, BPlusTreeNodeT* left, const pairT, BPlusTreeNodeT* right) { return left.first right.first; } template typename T void updatemax(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, T key) //向上更新父节点索引项关键码 { while (stackforback.empty() false) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; if (temp stackforback.top().first-keyptrmap-end()) --temp; temp-first key; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { break; } stackforback.pop(); } } template typename T pairbool, typename vectorT::iterator BinarySearch(vectorT list, typename vectorT::iterator left, typename vectorT::iterator right, const T key) { while (left right) { int d right - left 1; typename vectorT::iterator mid; if (d % 2 1) { mid left d / 2; } else { mid left (d / 2 - 1); } if (key *mid) { if (mid list.begin()) { return { false, left }; } right mid - 1; } else if (key *mid) { left mid 1; } else { return { true, mid }; } } return { false, left }; } template typename T typename vectorpairT, BPlusTreeNodeT*::iterator Upper_Bound(const T key, vectorpairT, BPlusTreeNodeT* list) { typename vectorpairT, BPlusTreeNodeT*::iterator left list.begin(); typename vectorpairT, BPlusTreeNodeT*::iterator right list.end() - 1; while (left right) { int d right - left 1; typename vectorpairT, BPlusTreeNodeT*::iterator mid; if (d % 2 1) { mid left d / 2; } else { mid left (d / 2 - 1); } if (key (*mid).first) { if (mid list.begin()) { return left; } right mid - 1; } else { left mid 1; } } return left; } templatetypename T bool afterSplit(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* ptr, BPlusTreeNodeT* current) { if (stackforback.top().first-keyptrmap-size() M) { if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { stackforback.pop(); if (ptr-NodeFlag BPlusTreeNodeT::flag::leaf) updatemax(stackforback, ptr-keyandptr-first.back()); else updatemax(stackforback, ptr-keyptrmap-back().first); } return true; } current stackforback.top().first; stackforback.pop(); return false; } template typename T void left_to_right_for_leaf(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { right-keyandptr-first.insert(right-keyandptr-first.begin(), mid-first); left-keyandptr-first.pop_back(); mid-first left-keyandptr-first.back(); } template typename T void right_to_left_for_leaf(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { left-keyandptr-first.push_back(*(right-keyandptr-first.begin())); mid-first *(right-keyandptr-first.begin()); right-keyandptr-first.erase(right-keyandptr-first.begin()); } template typename T void left_to_right_for_branch(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { right-keyptrmap-insert(right-keyptrmap-begin(), left-keyptrmap-back()); left-keyptrmap-pop_back(); mid-first left-keyptrmap-back().first; } template typename T void right_to_left_for_branch(BPlusTreeNodeT* left, BPlusTreeNodeT* right, const typename vectorpairT, BPlusTreeNodeT*::iterator mid) { left-keyptrmap-push_back(*(right-keyptrmap-begin())); mid-first right-keyptrmap-begin()-first; right-keyptrmap-erase(right-keyptrmap-begin()); } template typename T bool toRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { if (stackforback.top().second stackforback.top().first-keyptrmap-end() - 1) { if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if (stackforback.top().second stackforback.top().first-keyptrmap-end() - 1) { if ((stackforback.top().second 1)-second-keyandptr-first.size() M) { left_to_right_for_leaf(current, (stackforback.top().second 1)-second, stackforback.top().second); return true; } } } else { if (stackforback.top().second stackforback.top().first-keyptrmap-end() - 1) { if ((stackforback.top().second 1)-second-keyptrmap-size() M) { left_to_right_for_branch(current, (stackforback.top().second 1)-second, stackforback.top().second); return true; } } } } return false; } template typename T bool toLeft(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; if (temp ! stackforback.top().first-keyptrmap-begin()) { if (temp stackforback.top().first-keyptrmap-end()) --temp; if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if ((temp - 1)-second-keyandptr-first.size() M) { right_to_left_for_leaf((temp - 1)-second, current, temp - 1); if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { updatemax(stackforback, current-keyandptr-first.back()); } return true; } } else { if ((temp - 1)-second-keyptrmap-size() M) { right_to_left_for_branch((temp - 1)-second, current, temp - 1); if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { updatemax(stackforback, current-keyptrmap-back().first); } return true; } } } return false; } template typename T bool toLeftOrRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { if (toRight(stackforback, current)) return true; if (toLeft(stackforback, current)) return true; return false; } template typename T pairBPlusTreeNodeT*, BPlusTreeNodeT* BPlusInsert(BPlusTreeNodeT* root, BPlusTreeNodeT* head, const T key) //B树插入函数 { if (root nullptr) { root new BPlusTreeNodeT(BPlusTreeNodeT::flag::leaf); head root; root-keyandptr-first.push_back(key); return { root, head }; } else { BPlusTreeNodeT* current root; stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback; while (current-NodeFlag ! BPlusTreeNodeT::flag::leaf) { BPlusTreeNodeT* p nullptr; typename vectorpairT, BPlusTreeNodeT*::iterator scankey Upper_Bound(key, *(current-keyptrmap)); if (scankey current-keyptrmap-end()) { stackforback.push(make_pair(current, scankey)); --scankey; p scankey-second; while (p-NodeFlag ! BPlusTreeNodeT::flag::leaf) { typename vectorpairT, BPlusTreeNodeT*::iterator temp p-keyptrmap-end(); stackforback.push(make_pair(p, temp)); --temp; p temp-second; } current p; break; } if (scankey-first key) { cout 关键码 key 已存在,无法插入 endl; return { root, head }; } stackforback.push(make_pair(current, scankey)); current scankey-second; } { pairbool, typename vectorT::iterator result BinarySearch(current-keyandptr-first, current-keyandptr-first.begin(), current-keyandptr-first.end() - 1, key); if (result.first false) { current-keyandptr-first.insert(result.second, key); if (current-keyandptr-first.size() M) { if (current ! root key current-keyandptr-first.back()) updatemax(stackforback, current-keyandptr-first.back()); return { root, head }; } if (stackforback.empty() false) { if (toLeftOrRight(stackforback, current)) return { root, head }; } BPlusTreeNodeT* ptr new BPlusTreeNodeT(BPlusTreeNodeT::flag::leaf); ptr-keyandptr-first.insert(ptr-keyandptr-first.end(), current-keyandptr-first.end() - (M 1) / 2, current-keyandptr-first.end()); current-keyandptr-first.erase(current-keyandptr-first.end() - (M 1) / 2, current-keyandptr-first.end()); ptr-keyandptr-second current-keyandptr-second; current-keyandptr-second ptr; if (stackforback.empty() true) { root new BPlusTreeNodeT(BPlusTreeNodeT::flag::branch); root-keyptrmap-push_back(make_pair(current-keyandptr-first.back(), current)); root-keyptrmap-push_back(make_pair(ptr-keyandptr-first.back(), ptr)); return { root, head }; } typename vectorT::iterator temp ptr-keyandptr-first.end() - 1; if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { stackforback.top().first-keyptrmap-insert(stackforback.top().second, make_pair(*temp, ptr)); stackforback.top().second stackforback.top().first-keyptrmap-end(); (stackforback.top().second - 2)-first *(current-keyandptr-first.end() - 1); } else { stackforback.top().second stackforback.top().first-keyptrmap-insert(stackforback.top().second 1, make_pair(*temp, ptr)); --stackforback.top().second; stackforback.top().second-first *(current-keyandptr-first.end() - 1); } if (afterSplit(stackforback, ptr, current)) return { root, head }; while (true) { if (stackforback.empty() false) { if (toLeftOrRight(stackforback, current)) return { root, head }; } BPlusTreeNodeT* ptr new BPlusTreeNodeT(BPlusTreeNodeT::flag::branch); ptr-keyptrmap-insert(ptr-keyptrmap-end(), current-keyptrmap-end() - (M 1) / 2, current-keyptrmap-end()); current-keyptrmap-erase(current-keyptrmap-end() - (M 1) / 2, current-keyptrmap-end()); if (stackforback.empty() true) { root new BPlusTreeNodeT(BPlusTreeNodeT::flag::branch); root-keyptrmap-push_back(make_pair(current-keyptrmap-back().first, current)); root-keyptrmap-push_back(make_pair(ptr-keyptrmap-back().first, ptr)); return { root, head }; } typename vectorpairT, BPlusTreeNodeT*::iterator temp ptr-keyptrmap-end() - 1; if (stackforback.top().second stackforback.top().first-keyptrmap-end()) { stackforback.top().first-keyptrmap-insert(stackforback.top().second, make_pair(temp-first, ptr)); stackforback.top().second stackforback.top().first-keyptrmap-end(); (stackforback.top().second - 2)-first current-keyptrmap-back().first; } else { stackforback.top().second stackforback.top().first-keyptrmap-insert(stackforback.top().second 1, make_pair(temp-first, ptr)); --stackforback.top().second; stackforback.top().second-first current-keyptrmap-back().first; } if (afterSplit(stackforback, ptr, current)) return { root, head }; } } else { cout 关键码 key 已存在,无法插入 endl; return { root, head }; } } } } template typename T bool afterMerge(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* root, BPlusTreeNodeT* current, const typename vectorpairT, BPlusTreeNodeT*::iterator temp, const T key) { if (stackforback.top().first root || stackforback.top().first-keyptrmap-size() (M 1) / 2) { if (stackforback.top().first root root-keyptrmap-size() 1) { BPlusTreeNodeT* temp_ptr root-keyptrmap-front().second; delete root; root temp_ptr; } else { if (current nullptr) { if (temp-second-NodeFlag BPlusTreeNodeT::flag::leaf) { if (temp-second-keyandptr-first.back() key) { stackforback.pop(); updatemax(stackforback, temp-second-keyandptr-first.back()); } } else { if (temp-second-keyptrmap-back().first key) { stackforback.pop(); updatemax(stackforback, temp-second-keyptrmap-back().first); } } } } return true; } current stackforback.top().first; stackforback.pop(); return false; } template typename T bool borrowFromRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if (temp-second-keyandptr-first.size() (M 1) / 2 1) { right_to_left_for_leaf(current, temp-second, stackforback.top().second); return true; } } else { if (temp-second-keyptrmap-size() (M 1) / 2 1) { right_to_left_for_branch(current, temp-second, stackforback.top().second); return true; } } } return false; } template typename T bool borrowFromLeft(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current, const T key) { typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; if (temp ! stackforback.top().first-keyptrmap-begin()) { --temp; if (current-NodeFlag BPlusTreeNodeT::flag::leaf) { if (temp-second-keyandptr-first.size() (M 1) / 2 1) { left_to_right_for_leaf(temp-second, current, temp); if (current-keyandptr-first.back() key) updatemax(stackforback, current-keyandptr-first.back()); return true; } } else { if (temp-second-keyptrmap-size() (M 1) / 2 1) { left_to_right_for_branch(temp-second, current, temp); if (current-keyptrmap-back().first key) updatemax(stackforback, current-keyptrmap-back().first); return true; } } } return false; } template typename T bool borrowFromLeftOrRight(stackpairBPlusTreeNodeT*, typename vectorpairT, BPlusTreeNodeT*::iterator stackforback, BPlusTreeNodeT* current, const T key) { if (borrowFromRight(stackforback, current)) return true; if (borrowFromLeft(stackforback, current, key)) return true; return false; } template typename T pairBPlusTreeNodeT*, BPlusTreeNodeT* BPlusDelete(BPlusTreeNodeT* root, BPlusTreeNodeT* head, const T key) //B树删除函数,root根节点指针,head叶节点顺序链头节点指针 { BPlusTreeNodeT* current root; stackpairBPlusTreeNodeT*, vectorpairT, BPlusTreeNodeT*::iterator stackforback; while (current-NodeFlag ! BPlusTreeNodeT::flag::leaf) { typename vectorpairT, BPlusTreeNodeT*::iterator scankey Upper_Bound(key, *(current-keyptrmap)); if (scankey current-keyptrmap-end()) { cout 关键码不存在删除失败 endl; return { root, head }; } stackforback.push(make_pair(current, scankey)); current scankey-second; } { pairbool, typename vectorT::iterator result BinarySearch(current-keyandptr-first, current-keyandptr-first.begin(), current-keyandptr-first.end() - 1, key); if (result.first false) { cout 关键码不存在删除失败 endl; return { root, head }; } current-keyandptr-first.erase(result.second); } if (stackforback.empty() true) { if (current-keyandptr-first.empty() true) { delete current; return { nullptr, nullptr }; } return { current, current }; } if (current-keyandptr-first.size() (M 1) / 2) { if (current-keyandptr-first.back() key) updatemax(stackforback, current-keyandptr-first.back()); return { root, head }; } if (borrowFromLeftOrRight(stackforback, current, key)) { return { root, head }; } typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { current-keyandptr-first.insert(current-keyandptr-first.end(), temp-second-keyandptr-first.begin(), temp-second-keyandptr-first.end()); current-keyandptr-second temp-second-keyandptr-second; delete temp-second; stackforback.top().first-keyptrmap-erase(temp); stackforback.top().second-first current-keyandptr-first.back(); } else { temp temp - 2; temp-second-keyandptr-first.insert(temp-second-keyandptr-first.end(), current-keyandptr-first.begin(), current-keyandptr-first.end()); temp-second-keyandptr-second current-keyandptr-second; temp-first temp-second-keyandptr-first.back(); delete current; current nullptr; stackforback.top().first-keyptrmap-erase(stackforback.top().second); } if (afterMerge(stackforback, root, current, temp, key)) return { root, head }; while (true) { if (borrowFromLeftOrRight(stackforback, current, key)) { return { root, head }; } typename vectorpairT, BPlusTreeNodeT*::iterator temp stackforback.top().second; temp; if (temp ! stackforback.top().first-keyptrmap-end()) { current-keyptrmap-insert(current-keyptrmap-end(), temp-second-keyptrmap-begin(), temp-second-keyptrmap-end()); delete temp-second; stackforback.top().second-first current-keyptrmap-back().first; stackforback.top().first-keyptrmap-erase(temp); } else { temp temp - 2; temp-second-keyptrmap-insert(temp-second-keyptrmap-end(), current-keyptrmap-begin(), current-keyptrmap-end()); temp-first temp-second-keyptrmap-back().first; delete current; stackforback.top().first-keyptrmap-erase(stackforback.top().second); typename vectorpairT, BPlusTreeNodeT*::iterator it temp-second-keyptrmap-end() - 1; current nullptr; } if (afterMerge(stackforback, root, current, temp, key)) return { root, head }; } } int main() { const int N 2000; vectorint seq(N); for (int i 0; i N; i) { seq[i] i 1; } shuffle(seq.begin(), seq.end(), default_random_engine()); BPlusTreeNodeint* root nullptr; BPlusTreeNodeint* head nullptr; for (vectorint::const_iterator p seq.cbegin(); p ! seq.cend(); p) { cout 插入节点 *p endl; pairBPlusTreeNodeint*, BPlusTreeNodeint* temp BPlusInsert(root, head, *p); root temp.first; head temp.second; if (isBPlusTree(root, head)) { cout 当前树为B树 endl; } else { cout 错误,当前树不为B树! endl; exit(-1); } cout endl; } for (vectorint::const_iterator p seq.cbegin(); p ! seq.cend(); p) { cout 删除节点 *p endl; pairBPlusTreeNodeint*, BPlusTreeNodeint* temp BPlusDelete(root, head, *p); root temp.first; head temp.second; if (root nullptr head nullptr) cout NULL; else { if (isBPlusTree(root, head)) { cout 当前树为B树 endl; } else { cout 错误,当前树不为B树! endl; exit(-1); } } cout endl; } return 0; }
