B树
原理参考《算法导论》，这里只给出代码。针对删除算法，要注意：若x->key[i]下移到y结点(即使x->c[i])，那么是在y结点的尾部添加。若是下移到z结点(即x->c[i+1])，那么一定是在z结点的首部添加。这是因为大小顺序问题，理解了这一点，就很好理解《算法导论》给出的算法描述了。
定义一个B树类
template <int t> class BTree { public: typedef struct _BNode{ _BNode(bool _leaf) :n(0), leaf(_leaf) {} int key[2*t - 1];//2*t-1个关键字 _BNode *c[2*t];//2*t个子节点 bool leaf;//true代表叶子(没有子结点，本身就足以容纳关键数据)，false代表结点 int n;//代表关键字个数 }BNode, *pBNode; BTree() { root = new BNode(true); } void Insert(BNode *x, int k); std::pair<BNode *, int> Seach(BNode *x, int k); std::pair<BNode *, int> Prev(int k); std::pair<BNode *, int> Next(int k); void Delete(BNode *x, int k); void Empty(); void Print(BNode *x);//顺序输出 void Print_tree(BNode *x);//层次输出 BNode *Root() { return root; } ~BTree() { Empty(); delete root;//删除空的root } private: void Split_child(BNode *x, int i, BNode *y); void Insert_directly(BNode *x, int k); BNode *root; };
实例声明
template class BTree<2>;
对应的成员函数实现
Insert函数，插入关键字到B树中，并实现B树平衡
template <int t> void BTree<t>::Insert(typename BTree<t>::BNode *x, int k) { BNode *r = root, *s; if (r->n == 2 * t - 1) { s = new BNode(false); root = s; s->c[0] = r; Split_child(s, 0, r); Insert_directly(s, k); } else Insert_directly(r, k); }
对应的两个辅助函数Split_child, Insert_directly
template<int t> void BTree<t>::Split_child(typename BTree<t>::BNode *x, int i, typename BTree<t>::BNode *y) {//分裂y，并在x->c[i]处插入y结点 int j; BNode *z = new BNode(y->leaf); //z结点，是x结点的右子结点 z->n = t - 1; for (j = 0; j < t - 1; j++) z->key[j] = y->key[j + t];//复制关键字 if (!y->leaf) //y是结点 for (j = 0; j < t; j++) z->c[j] = y->c[j + t];//复制子结点 //y结点，是x结点的左子结点 y->n = t - 1; //在x结点中增加一个子结点z，保证x->n<=2*t-1，并且x结点的i处是y for (j = x->n; j >= i + 1; j--) x->c[j + 1] = x->c[j]; x->c[i + 1] = z; for (j = x->n - 1; j >= i; j--) x->key[j + 1] = x->key[j]; x->key[i] = y->key[t - 1]; x->n++; }
void BTree<t>::Insert_directly(typename BTree<t>::BNode *x, int k) { int i = x->n - 1; if (x->leaf) {//同一高度插入关键字k while (i >= 0 && k < x->key[i]) {//调用此函数前，保证了x->n<2*t-1 x->key[i + 1] = x->key[i]; i--; } x->key[i + 1] = k; x->n++; } else {//结点满了 while (i >= 0 && k < x->key[i]) i--; i = i + 1; if (x->c[i]->n == 2 * t - 1) { Split_child(x, i, x->c[i]); if (k > x->key[i]) i++; } Insert_directly(x->c[i], k); } }
Delete删除函数，本质就是通过结点的合并实现删除关键字，原理参考《算法导论》的描述，可对照我的代码理解。
template <int t> void BTree<t>::Delete(typename BTree<t>::BNode *x, int k) { int i, j; BNode *y, *z; typename std::pair<BNode *, int> p;//<BNode *, index> //检查k是否在x结点中，找到一个至少比关键字k大的位置 for (i = 0; i < x->n; i++) if (x->key[i] >= k) break; y = x->c[i];//y是x->key[i]的左子结点 z = x->c[i + 1];//z是x->key[i]的右子结点 if (x->key[i] == k && i != x->n) {//k在结点x内 if (x->leaf) {//1, x是叶节点，直接删除关键字 for (j = i; j < x->n - 1; j++) x->key[j] = x->key[j + 1]; x->n--; return; } else {//x是结点，分3种情况 //2-a，左子结点y至少包含t个关键字 if (y->n >= t) { p = this->Prev(k);//前驱 x->key[i] = p.first->key[p.second];//前驱关键字替换k关键字 this->Delete(y, x->key[i]); } else if (z->n >= t) {//2-b，右结点z至少包含t个关键字 p = this->Next(k);//后继 x->key[i] = p.first->key[p.second];//后继关键字替换k关键字 this->Delete(z, x->key[i]); } else {//2-c, 左右子结点都只有t-1个关键字 y->key[y->n] = k;//合并关键字k for (j = 0; j < z->n; j++) y->key[y->n + 1 + j] = z->key[j];//合并结点z的所有关键字 if (!y->leaf) {//合并对应的子结点 for (j = 0; j < z->n + 1; j++) y->c[y->n + 1 + j] = z->c[j]; } y->n = y->n + 1 + z->n;//一个关键字k和来自结点z的n个关键字 for (j = i; j < x->n - 1; j++)//剔除关键字k x->key[j] = x->key[j + 1]; for (j = i + 1; j < x->n; j++)//剔除右子结点z x->c[j] = x->c[j + 1]; x->n--; delete z; //如果x是根结点且x经过上述操作后为空 if (x->n == 0 && root == x) { delete x; root = y; } this->Delete(y, k); } } } else {//k不在结点x内，调整B树 if (x->leaf) { printf("关键字%c不存在, 未删除任何结点，但会让B树结构变化，不影响平衡！\n", k); return; } if (y->n == t - 1) {//左子结点只有t-1个关键字 //3-a，邻左或右结点至少有t个关键字(相对于y结点) if (i < x->n && z->n >= t) {//邻右，即z结点 y->key[y->n] = x->key[i];//i处关键字下降至y结点 x->key[i] = z->key[0];//z的某关键字上升到x，并覆盖x->key[i] for (j = 0; j < z->n - 1; j++) z->key[j] = z->key[j + 1];//剔除关键字z->key[0] if (!y->leaf) { y->c[y->n + 1] = z->c[0];//将z的子结点放入y for (j = 0; j < z->n; j++) z->c[j] = z->c[j + 1];//剔除z->c[0] } y->n++; z->n--; } else if (i > 0 && x->c[i - 1]->n >= t) {//邻左，即y结点的左边相邻兄弟i-1 for (j = y->n - 1; j >= 0; j--) y->key[j + 1] = y->key[j];//预留一个位置 y->key[0] = x->key[i - 1];//x结点中的某一个关键字下降到y x->key[i - 1] = x->c[i - 1]->key[x->c[i - 1]->n - 1];//将左邻兄弟i-1的某关键字上升到x，并覆盖x->key[i-1] //由于是将左邻兄弟i-1的最后一个关键字上升，x->c[i-1]->n--控制，所以不需要在剔除关键字和子结点 if (!y->leaf) { for (j = y->n; j >= 0; j--) y->c[j + 1] = y->c[j];//预留一个位置 y->c[0] = x->c[i - 1]->c[x->c[i - 1]->n];//左邻兄弟i-1的子结点加入到y } y->n++; x->c[i - 1]->n--; } else {//3-b，所有相邻兄弟都只有t-1个关键字，则与其中一个兄弟合并(相对于y结点) //当i < x->n，z合并于y结点 if (i >= x->n) {//y合并于x->c[i-1]结点，此操作防止越界 y = x->c[i - 1];//相对于i-1 z = x->c[i]; i--; } y->key[y->n] = x->key[i];//放入y for (j = 0; j < z->n; j++) y->key[y->n + 1 + j] = z->key[j];//合并z if (!y->leaf) {//合并对应的子结点 for (j = 0; j < z->n + 1; j++) y->c[y->n + 1 + j] = z->c[j]; } y->n = y->n + 1 + z->n; for (j = i; j < x->n - 1; j++)//剔除i处的关键字 x->key[j] = x->key[j + 1]; for (j = i + 1; j < x->n; j++)//剔除i+1处的子结点 x->c[j] = x->c[j + 1]; x->n--; delete z; //如果x是根结点且x经过上述操作后为空 if (x->n == 0 && root == x) { delete x; root = y; } } } this->Delete(y, k); } }
输出函数，Print函数是按顺序输出，Print_tree是层次输出，方便大家考察函数结果是否正确。
template <int t> void BTree<t>::Print(typename BTree<t>::BNode *x) { for (int i = 0; i < x->n; i++){ if (!x->leaf) Print(x->c[i]); printf("%-02c ", x->key[i]); } if (!x->leaf) Print(x->c[x->n]); } template <int t> void BTree<t>::Print_tree(typename BTree<t>::BNode *x) { for (int i = 0; i < x->n; i++) printf("%-02c ", x->key[i]); printf("\n"); if (!x->leaf) //结点 for (int i = 0; i <= x->n; i++) Print_tree(x->c[i]); }
Empty函数，所有结点的释放。原理：通过反复删除根节点的第一个关键字，从而达到所有关键字的删除。
template <int t> void BTree<t>::Empty(){ while (root->n != 0) { this->Delete(root, root->key[0]); Print(root); printf("\n"); } }
主函数
int main() { //while (true) {//用于测试是否存在内存泄露 int key[] = { 'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E' }, k = 'O'; BTree<2> btree; for (int i = 0; i < sizeof(key) / sizeof(key[0]); i++) btree.Insert(btree.Root(), key[i]); btree.Print_tree(btree.Root()); std::pair<BTree<2>::BNode *, int> p = btree.Seach(btree.Root(), 'D'); printf("Seaching at %d, %c found\n", p.second, p.first->key[p.second]); btree.Print(btree.Root()); printf("\n"); btree.Delete(btree.Root(), k); printf("After deleting %c...\n", k); btree.Print_tree(btree.Root()); printf("\n"); btree.Print(btree.Root()); printf("\n清理中....\n");
//调用析构函数 //} return 0; }
数据测试
数据录入
int key[] = { 'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E' }
正确的结果图如下：
程序输出的结果
代码均经过测试，结果正确！！！
版权声明：本文为dalgleish原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。