[Data Structure] B-tree (B-Tree)

B-tree
In 1970, R.Bayer and E.mccreight proposed a tree suitable for external search, which is a balanced polytree. Called B-tree. (B-tree is written in some places. Be careful not to misread
as “B minus tree”)
A B-tree of order M (M>2) is a balanced M-way balanced search tree , Can be an empty tree or satisfy the following properties:
1. The root node has at least two children
2. Each non-root node has [,M] children
3. Each non-root node has [-1,M-1] keywords, arranged in ascending order
4. The value of the child node between key[i] and key[i+1] is between key[i], key[i+ 1] between
5. All leaf nodes are on the same layer

ps: is rounded up< /p>

B-tree is a highly balanced tree

Here is an explanation with M=3 as an example

For example, a tree has an array int arr[]={3,4, 10, 15, 16, 20, 30, 35, 36, 40, 45, 46, 50, 76, 77}; then its structure is as shown below

B-tree insertion

For example, insert 20 30 10 and the drawing analysis is as follows

< span style="font-size:18px">

Source code

#pragma once#include #include using namespace std;templatestruct BTreeNode{ K _keys[M];//Keyword array, one more for easy decomposition BTreeNode* _subs[M+1];//Pointer array connecting subtree BTreeNode* _parent; int size;//Number of keywords BTreeNode() :size(0) ,_parent(NULL) {size_t i=0; for (i=0;iclass BTree{ typedef BTreeNode Node;public: BTree(): _root(NULL) {} pair Find(const K& key) {Node* cur=_root; Node* parent=NULL; while(cur) {int i=0; while(isize ) {if(cur->_keys[i]_keys[i]>key) {break;} else//Find a key {return pair(cur,i);}} parent=cur; cur=cur->_subs[i];} return pair (parent,-1);//If no keyword is found, return -1;} bool Insert(const K& key) {if(_root==NULL)//Insert empty tree {_root=new Node ; _root->_keys[0]=key; _root->size=1; return true;} pair ret=Find(key); if(ret.second!=-1)//If not Insert if found, do not insert if found return false; Node* cur=ret.first; K newkey=key; Node* sub=NULL; while(1) {InsertKey(cur,newkey,sub); if(cur->size size/2;//After inserting, M is full and splitting Node* tmp=new Node; int j=0; for(int i=mid+1;isize;++i)//copy key and children, split continuously {tmp->_keys[j]=cur->_keys[i]; if (cur- >_subs[i]) {tmp->_subs[j]=cur->_subs[i]; tmp->_subs[j+1]=sub; cur->_subs[i]=NULL; tmp->_subs[ j]->_parent=tmp; tmp->_subs[j+1]->_parent=tmp;} tmp->size++; cur->_keys[i]=K(); cur->size--; j++; } if(cur->_parent==NULL)//Split to the root node {_root=new Node; _root->_keys[0]=cur->_keys[mid]; _root->_subs[0]=cur; _root ->_subs[1]=tmp; _root->size++; cur->_keys[mid] =K(); cur->size--; cur->_parent=_root; tmp->_parent=_root; return true;} //not split to the root node newkey=cur->_keys[mid]; cur-> _keys[mid]=K(); cur->size--; sub=tmp; cur=cur->_parent;//Move up} return true;} void Inorder() {_Inorder(_root); cout<size-1; while (i>=0) {if(node->_keys[i]>key) {node->_keys[i+1]=node->_keys[i]; node->_subs[i+2]=node->_subs[i+1]; --i;} else {break;}} node->_keys[i+1]= key; node->_subs[i+2]=sub; if(sub) sub->_parent=node; node->size++;} void _Inorder(Node* root)// After printing a subtree, then recursively print the next step {if(root==NULL) return; _Inorder(root->_subs[0]); for (int i=0;isize;i++) {/ / _Inorder(root->_subs[i]); cout<_keys[i]<<" ";} for(int i=1;i_subs [i]);} }private: Node* _root;};void testBTree(){ BTree bt; int arr[]={53, 75, 139, 49, 145, 36, 101}; for (i nt i=0;i
 
#include "BTree.h"#include int main(){ testBTree(); system("pause") ; return 0;}
 The middle order traversal result is