B-树的插入和遍历

B-树是一种平衡的多叉树，一颗M阶(M>2)的B树，是一颗平衡的M路平衡搜索树，可以是空树或者满足下列性质：

1. 根节点至少有两个孩子 2. 每个非根节点有[ [M/2],M]个孩子 3. 每个非根节点有[ [M/2] -1,M-1]个关键字，并且以升序排列 4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间 5. 所有的叶子节点都在同一层 ps： [M/2]是向上取整

先看看B-树节点的结构:

template<class K,size_t M = 3> struct BTreeNode { K _key[M]; //关键字 BTreeNode<K, M>* _subs[M + 1]; //孩子 BTreeNode<K, M>* _parent; size_t _size; //实际关键字个数 BTreeNode() :_parent(NULL) , _size(0) { memset(_subs, 0, sizeof(_subs)); } };

插入的几种情况:

1.没有节点，即root == NULL;

这个是最简单，直接创建一个节点，将key值放入；

if (_root == NULL) { _root = new Node; _root->_key[0] = key; _root->_size++; } 2.有节点，找到要插入的位置，进行插入。完毕之后必须进行是否需要进行分裂的判断。分裂保证第2，3条性质。分裂完后继续判断父亲是否需要分裂，直到找到不需要分裂的位置结束。

3.每次插入一个key都会带一个子节点（NULL）。以保证孩子比key多一个的性质；向上调整时，也可以看作是向父亲接待你插入一个新的key，所带子节点为分裂出来的节点(newNode)。

插入代码实现：

bool Insert(const K &key) { //没有节点 if (_root == NULL) { _root = new Node; _root->_key[0] = key; _root->_size++; } //找到key的节点 pair<Node*,int> ret = Find(key); if (ret.second >= 0) { return false; //已存在，不需要插入 } //进行插入 K newKey = key; Node *cur = ret.first; Node *sub = NULL; while (1) { InsertKey(newKey, cur, sub); //在cur节点插入一个newKey ,所带的孩子为sub //判断分裂 if (cur->_size < M) { return true; } //开始分裂 Node *newNode = new Node; size_t mid = M / 2; int index = 0; //构造分裂出来的newNode size_t i = mid + 1; for (; i < cur->_size; i++) { //提取mid后面的数据到newNode中:key，左边孩子 newNode->_key[index] = cur->_key[i]; newNode->_size++; newNode->_subs[index] = cur->_subs[i]; ++index; if (cur->_subs[i]) { Node *sb = cur->_subs[i]; cur->_subs[i] = NULL; sb->_parent = newNode; } } newNode->_subs[index] = cur->_subs[i]; cur->_size = cur->_size - newNode->_size - 1; if (cur->_subs[i]) { Node *sb = cur->_subs[i]; cur->_subs[i] = NULL; sb->_parent = newNode; } if (cur->_parent == NULL) //分裂的节点是第一个节点 { _root = new Node; _root->_key[0] = cur->_key[mid]; _root->_subs[0] = cur; cur->_parent = _root; _root->_subs[1] = newNode; newNode->_parent = _root; _root->_size++; return true; } else //分裂的节点有父亲节点，需要判断父亲节点是否分裂 { newKey = cur->_key[mid]; cur = cur->_parent; sub = newNode; } } }上述就说完了插入，下面来看看中序遍历:

遍历就十分简单，直接看代码

void _Inorder(Node *root) { if (root == NULL) { return; } int i = 0; for (; i < root->_size; i++) //遍历所有的key才是这个节点遍历完 { _Inorder(root->_subs[i]); cout << root->_key[i] << " "; } _Inorder(root->_subs[i]); }

总体实现代码：

//B-树 template<class K,size_t M = 3> struct BTreeNode { K _key[M]; //关键字 BTreeNode<K, M>* _subs[M + 1]; //孩子 BTreeNode<K, M>* _parent; size_t _size; //实际关键字个数 BTreeNode() :_parent(NULL) , _size(0) { memset(_subs, 0, sizeof(_subs)); } }; template<class K,size_t M = 3> class BTree { typedef BTreeNode<K, M> Node; public: BTree() :_root(NULL) {} bool Insert(const K &key) { //没有节点 if (_root == NULL) { _root = new Node; _root->_key[0] = key; _root->_size++; } //找到key的节点 pair<Node*,int> ret = Find(key); if (ret.second >= 0) { return false; //已存在，不需要插入 } //进行插入 K newKey = key; Node *cur = ret.first; Node *sub = NULL; while (1) { InsertKey(newKey, cur, sub); //判断分裂 if (cur->_size < M) { return true; } //开始分裂 Node *newNode = new Node; size_t mid = M / 2; int index = 0; //构造分裂出来的newNode size_t i = mid + 1; for (; i < cur->_size; i++) { //提取mid后面的数据到newNode中:key，左边孩子 newNode->_key[index] = cur->_key[i]; newNode->_size++; newNode->_subs[index] = cur->_subs[i]; ++index; if (cur->_subs[i]) { Node *sb = cur->_subs[i]; cur->_subs[i] = NULL; sb->_parent = newNode; } } newNode->_subs[index] = cur->_subs[i]; cur->_size = cur->_size - newNode->_size - 1; if (cur->_subs[i]) { Node *sb = cur->_subs[i]; cur->_subs[i] = NULL; sb->_parent = newNode; } if (cur->_parent == NULL) { _root = new Node; _root->_key[0] = cur->_key[mid]; _root->_subs[0] = cur; cur->_parent = _root; _root->_subs[1] = newNode; newNode->_parent = _root; _root->_size++; return true; } else { newKey = cur->_key[mid]; cur = cur->_parent; sub = newNode; } } } void InsertKey(const K &key, Node *cur, Node *sub) //cur要被差的节点，sub为key所带的孩子 { assert(cur); int end = cur->_size - 1; while (end >= 0) { if (cur->_key[end] < key) { break; } else //后移 { cur->_key[end + 1] = cur->_key[end]; cur->_subs[end + 2] = cur->_subs[end + 1]; } end--; } //找到插入位置; cur->_key[end + 1] = key; cur->_subs[end + 2] = sub; cur->_size++; if (sub) sub->_parent = cur; } pair<Node*, int> Find(const K &key) { Node *cur = _root; Node *parent = NULL; while (cur) { size_t i = 0; for (; i < cur->_size;) { if (cur->_key[i] < key) { ++i; } else if (cur->_key[i] > key) { break; } else //key已经出现在树中 { return make_pair(cur, 0); } } parent = cur; cur = cur->_subs[i]; } return make_pair(parent, -1); //没有找到key } void Inorder() { _Inorder(_root); } protected: void _Inorder(Node *root) { if (root == NULL) { return; } int i = 0; for (; i < root->_size; i++) { _Inorder(root->_subs[i]); cout << root->_key[i] << " "; } _Inorder(root->_subs[i]); } protected: Node *_root; };