BTree的插入和查找算法分析

本文主要是介绍BTree的插入和查找算法分析，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1.什么叫BTree？

2.BTree的性质

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

1. 根节点至少有两个孩子（孩子为NULL也算作孩子的数量）

2. 每个非根节点有[M/2,M]个孩子（注意孩子与关键字的关系，n个key，n+1孩子）

3. 每个非根节点有[M/2 - 1,M - 1]个关键字，并且以升序排列(这样才能进行查找)

4. key[i]和key[i+1]之间的孩子节点的值介于key[i]、key[i+1]之间

5. 所有的叶子节点都在同一层（整棵树的高度一致）

3.BTree结点的定义

template<class K,class V,size_t M>
//非类型的模板参数在推演时变成常量
//M阶树的孩子个数为	[M/2,M]		个孩子
//M阶树的关键字个数为	[M/2-1,M-1]	个关键字,且为升序排列
struct BTreeNode
{//将数组的大小预留出一位是为了便于分裂pair<K, V> _kvs[M];					//kvs数组,存放kvBTreeNode<K, V, M>* _parent;		   //指向父结点的指针，便于分裂BTreeNode<K, V, M>* _subs[M + 1];	  //指向孩子结点的指针数组size_t _size;				         //kvs数量,有效数据个数BTreeNode():_parent(NULL), _size(0){for (size_t i = 0; i < M + 1; i++){_subs[i] = NULL;}}
};

pair<Node* ,int>  Find(const K& key){Node* cur = _root;Node* parent = NULL;size_t index = 0;while (cur != NULL){index = 0;while (index < cur->_size){if (cur->_kvs[index].first == key){return make_pair(cur, -1);}else if (cur->_kvs[index].first > key){break;}else{++index;}}parent = cur;cur = cur->_subs[index];}//BTree并不需要在空位置插入，一个结点可以有多个关键字//当这个结点的孩子为空，没找到关键字时，就可以插入了return make_pair(parent, index);}

5.插入算法的实现

	bool Insert(const pair<K, V> & kv){if (_root == NULL){_root = new Node();_root->_kvs[0] = kv;_root->_subs[0] = NULL;_root->_subs[1] = NULL;_root->_size++;}pair<Node*, int> ret = this->Find(kv.first);if (ret.second == -1)return false;//要插入位置的结点Node* cur = ret.first;Node* parent = cur->_parent;Node* sub = NULL;pair<K, V> newKV = kv;while (1){this->InsertKV(cur, newKV, sub);if (cur->_size < M){return true;}//走到这里表示结点存放的kv已经满了,需要分裂Node* brother = new Node();int mid = M / 2;int i = mid + 1;int j = 0;//将中间结点之后的数据复制给兄弟结点for (; i < M; i++){brother->_kvs[j] = cur->_kvs[i];brother->_size++;cur->_size--;if (cur->_subs[i] != NULL){cur->_subs[i]->_parent = brother;brother->_subs[j] = cur->_subs[i];cur->_subs[i] = NULL;}j++;}if (cur->_subs[i] != NULL)cur->_subs[i]->_parent = brother;brother->_subs[j] = cur->_subs[i];cur->_subs[i] = NULL;//如果已经到根结点if (parent == NULL){Node* root = new Node();root->_kvs[0] = cur->_kvs[mid];root->_subs[0] = cur;cur->_parent = root;cur->_size--;root->_subs[1] = brother;brother->_parent = root;_root = root;_root->_size++;return true;}//将中间结点上移newKV = cur->_kvs[mid];cur->_size--;cur = parent;parent = cur->_parent;sub = brother;}}void InsertKV(Node* cur,const pair<K, V>& kv,Node* sub){size_t index = 0;for (; index < cur->_size; index++){if (kv.first < cur->_kvs[index].first)break;}for (size_t i = cur->_size ; i > index; i--){cur->_kvs[i] = cur->_kvs[i - 1];cur->_subs[i + 1] = cur->_subs[i];}cur->_kvs[index] = kv;cur->_subs[index + 1] = sub;if (sub != NULL){sub->_parent = cur;}cur->_size++;return;}

6.中序遍历的实现

void InOrder(){_InOrder(_root);}void _InOrder(Node* root){if (root == NULL)return;size_t i = 0;for (; i < root->_size; i++){_InOrder(root->_subs[i]);cout << root->_kvs[i].first << " ：" << root->_kvs[i].second << endl;}_InOrder(root->_subs[i]);}

7.测试用例

8.BTree的应用

这篇关于BTree的插入和查找算法分析的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！