c++B-Tree的操作-创新互联
#include创新互联建站主营盐城网站建设的网络公司,主营网站建设方案,成都App制作,盐城h5成都小程序开发搭建,盐城网站营销推广欢迎盐城等地区企业咨询using namespace std; template struct BTreeNode { K _keys[M]; BTreeNode* _subs[M + 1]; BTreeNode* _parent; size_t _size; BTreeNode(const K& key) :_parent(NULL) , _size(0) { for (int i = 0; i < M; ++i) { _keys[i] = 0; } for (int i = 0; i <= M; ++i) { _subs[i] = NULL; } _keys[_size++] = key; } ~BTreeNode(){}; }; template class BTree { public: typedef BTreeNode Node; BTree() :_root(NULL) {} pair Find(const K& key) { if (_root == NULL) { return pair (NULL, -1); } Node* prev = NULL; Node* cur = _root; while (cur) { int i = 0; for (; i < (int)cur->_size; ) { if (key>cur->_keys[i]) ++i; else if (key < cur->_keys[i]){ break; } else return pair (cur, i); } prev = cur; cur = cur->_subs[i]; } return pair (prev, -1); } bool Insert(const K& key) { if (_root == NULL) { _root = new Node(key); return true; } pair ret = Find(key); if (ret.second != -1) return false; Node* cur = ret.first; Node* prev = NULL; int i = cur->_size; while (i > ret.second&&key _keys[i-1]) { cur->_keys[i ] = cur->_keys[i-1]; --i; } cur->_keys[i] = key; ++cur->_size; if (cur->_size < M) return true; int mid = M / 2; //K newKey = key; while (1){ Node* newNode = NULL; //cout << M << endl; while (mid < M - 1) { if (newNode == NULL) newNode = new Node(cur->_keys[mid + 1]); else newNode->_keys[newNode->_size++] = cur->_keys[mid + 1]; cur->_keys[mid + 1] = 0; newNode->_subs[newNode->_size - 1] = cur->_subs[mid+1]; if (cur->_subs[mid+1]) (cur->_subs[mid+1])->_parent = newNode; cur->_subs[++mid] = NULL; newNode->_subs[newNode->_size] = cur->_subs[mid+1];; if (cur->_subs[mid+1]) (cur->_subs[mid+1])->_parent = newNode; cur->_subs[mid+1] = NULL; --cur->_size; } //cur->_subs[M / 2 + 1] = newNode; prev = cur->_parent; if (prev == NULL) { prev = new Node(cur->_keys[M / 2]); cur->_keys[M / 2] = 0; prev->_subs[0] = cur; prev->_subs[1] = newNode; cur->_parent = prev; newNode->_parent = prev; --cur->_size; _root = prev; return true; } i = prev->_size - 1; while (i >= 0 && prev->_keys[i] > cur->_keys[M / 2]) { prev->_keys[i + 1] = prev->_keys[i]; prev->_subs[i + 2] = prev->_subs[i+1]; --i; } prev->_keys[i + 1] = cur->_keys[M / 2]; prev->_subs[i + 2] = newNode; newNode->_parent = prev; cur->_subs[M / 2 + 1] = NULL; cur->_keys[M / 2] = 0; ++prev->_size; --cur->_size; cur = prev; prev = cur->_parent; mid = M / 2; if (cur->_size < M) return true; } return true; } bool Remove(const K& key) { if (_root == NULL) return false; pair ret = Find(key); if (ret.second == -1) return false; Node* cur = ret.first; Node* prev = NULL; int index = ret.second; int pindex = 0; K newKey = key; while (cur) { prev = cur->_parent;//获取父节点 if (cur->_subs[index] == NULL)//叶子节点 { if (cur->_size >= M / 2){//节点key 数量 >= M/2,直接删除 for (int i = index; i < (int)cur->_size; ++i) { cur->_keys[i] = cur->_keys[i + 1]; } cur->_size--; return true; } if (prev == NULL)//父为空 只有一个节点 { if (cur->_size == 1)//只有一个key 删除后 释放节点 _root制空 { _root = NULL; delete cur; } else//否则删除 key 移动其他 { for (int i = index; i < (int)cur->_size; ++i) { cur->_keys[i] = cur->_keys[i + 1]; } } return true; } else//父不为空 { int dev = 0; for (; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1) { if (prev->_subs[dev] == cur) break; } if (dev !=0 && (int)prev->_subs[dev - 1]->_size > M / 2)//cur不为prev最左sub 找左边替代 { Node* tmp = prev->_subs[dev - 1]; cur->_keys[index] = prev->_keys[dev - 1]; prev->_keys[dev - 1] = tmp->_keys[tmp->_size-1]; tmp->_keys[tmp->_size - 1] = 0; tmp->_size--; return true; } if (dev != (int)prev->_size && (int)(prev->_subs[dev + 1]->_size) > M / 2)//不为最右 找右替代 { Node* tmp = prev->_subs[dev + 1]; cur->_keys[index] = prev->_keys[dev ]; prev->_keys[dev ] = tmp->_keys[0]; tmp->_keys[tmp->_size - 1] = 0; for (int i = 0; i <(int) tmp->_size; ++i) { tmp->_keys[i] = tmp->_keys[i + 1]; } tmp->_size--; return true; } for (int i = index; i < (int)cur->_size; ++i) { cur->_keys[i] = cur->_keys[i + 1]; } cur->_size--; //需要合并 Node* ppNode = NULL; while (1){ if (dev != 0) { ppNode = prev->_parent; Node* sub = prev->_subs[dev - 1]; sub->_keys[sub->_size++] = prev->_keys[dev - 1]; for (int i = 0; i <(int)cur->_size;++i) { sub->_keys[sub->_size++] = cur->_keys[i]; } for (int i = dev - 1; i < (int)prev->_size; ++i) { prev->_keys[i] = prev->_keys[i + 1]; prev->_subs[i + 1] = prev->_subs[i + 2]; } if (sub->_subs[0] == NULL){ delete cur; } else { sub->_subs[sub->_size] = cur; cur->_parent = sub; } if ((int)prev->_size-- >1) return true; else { if (ppNode==NULL) { _root = sub; sub->_parent = NULL; delete prev; return true; } else { sub->_parent = prev->_parent; memcpy(prev, sub, sizeof(Node)); delete sub; cur = prev; prev = ppNode; for (dev=0; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1) { if (prev->_subs[dev] == cur) break; } return true; } } } else { ppNode = prev->_parent; Node* sub = prev->_subs[dev +1]; cur->_keys[cur->_size++] = prev->_keys[dev]; for (int i = 0; i <(int)sub->_size;++i) { cur->_keys[cur->_size++] = sub->_keys[i]; } for (int i = dev ; i < (int)prev->_size; ++i) { prev->_keys[i] = prev->_keys[i + 1]; prev->_subs[i + 1] = prev->_subs[i + 2]; } if (cur->_subs[0] == NULL){ delete sub; } else { cur->_subs[cur->_size] = sub; sub->_parent = cur; } if ((int)prev->_size-- >1) return true; else { if (ppNode == NULL) { _root = cur; cur->_parent = NULL; delete prev; return true; } else { cur->_parent = prev->_parent; memcpy(prev, cur, sizeof(Node)); delete cur; cur = prev; prev = ppNode; for (dev = 0; dev <= (int)prev->_size; ++dev)//判断删除操作的节点在父节点的关键字的位置(0--m-1) { if (prev->_subs[dev] == cur) break; } return true; } } } } } } else//不为叶子 { if (cur->_subs[index + 1]->_size >0)//找右孩子最小替代删除 { Node* sub = cur->_subs[index + 1]; while (sub->_subs[0]) { sub = sub->_subs[0]; } cur->_keys[index] = sub->_keys[0]; cur = sub; index = 0; } else if (cur->_subs[index]->_size >0)//找左孩子大替代 { Node* sub = cur->_subs[index]; int size=sub->_size; while (sub->_subs[0]){ size = sub->_size; sub = sub->_subs[size]; } cur->_keys[index] = sub->_keys[size - 1]; cur = sub; index = (int)sub->_size; } else { delete cur->_subs[index]; delete cur->_subs[index + 1]; cur->_subs[index] = NULL; cur->_subs[index] = NULL; } } } return true; } void Traverse() { _Traverse(_root); cout << endl; } private: void _Traverse(Node* root) { if (root == NULL) return; int i = 0; for (; i <(int) root->_size; ++i) { if (i == 0) _Traverse(root->_subs[0]); cout << root->_keys[i]<<" "; _Traverse(root->_subs[i+1]); } } Node* _root; };
另外有需要云服务器可以了解下创新互联scvps.cn,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。
当前文章:c++B-Tree的操作-创新互联
文章URL:http://scyanting.com/article/hdiih.html