hao3100590
- 浏览: 128678 次
- 性别:
- 来自: 成都
-
最新评论
-
yi_chao_jiang：
你好，多谢分享，问个问题，在上传数据的时候判断文件是否有上传记 ...
断点续传和下载原理分析 -
a41606709：
为什么我的tabhost显示不出来？ 怎么设置在全部页面中让他 ...
TabActivity中的Tab标签详细设置 -
Zero颴：
大神篇,思路,配图都很清晰,perfect!
Android事件模型之interceptTouchEvnet ,onTouchEvent关系正解 -
QAZ503602501：
牛死人了！！！
B-树 -
mengsina：
很牛的文档。数学功底好啊
Android Matrix理论与应用详解
1.什么是B-树？
这个在我的前一篇博客中已经详细的阐释过：
http://hao3100590.iteye.com/blog/1576846
具体的了解，好好看看这篇文章就可以了！
2.实现关键问题分析
a.B-树删除原则
见下图：
当然总结起来，大的方面就3点，具体的细节就没有做多大的说明，在下面具体实现的时候会说明
b.B-树的递归和非递归遍历
对于非递归遍历，比较麻烦，自己需要按照下面图中所示的方式来遍历B-树，输出的关键字大小从小到大排列，但是对于递归却相当简单，这里非递归没有利用栈来实现，所以注意！
c.B-树删除伪代码
见下图：
d.具体删除之借详细演示
如下图：
3.关键函数说明
void insertList(T a[], int n, T x, int *p);
void deleteList(T *a, int n, int p);
void insertPoint(Node<T> *a[], int n, Node<T>* p, int pos);
void deletePoint(Node<T> *a[], int n, int p);
上面四个函数是实现插入和删除在Node中的关键字数组和指针数组的插入删除操作（就是数组删除）
下面的函数主要就是对插入和删除的操作
//插入的时候分裂提升结点p
Node<T>* divideTree(Node<T>* &root, Node<T>* &p);
//修改结点p的所有孩子结点的父节点为p，因为当删除的时候，父亲节点也可能改变
void modifyParent(Node<T>* &p);
//查询结点p在结点parent中的位置，或者关键字在结点parent中的位置（寻找插入位置或者查找）
int position(Node<T>* parent, Node<T>* p, T key);
//parent为p的双亲，从兄弟借元素（如果兄弟可借，否则什么都不做）,pos是p中待删除元素的位置
bool borrowFromSib(Node<T>* &parent, Node<T>* p, int pos);
//从parent的儿子中借一个然后删除parent中一个关键字（pos是parent待删除位置）
bool borrowFromSon(Node<T>* &parent, int pos);
//合并在parent中位置在pos处关键字的左右儿子,如果key[pos]是待删除的则设置flag=true
void mergeSib(Node<T>* &parent, int pos, bool flag);
//删除的时候递归合并操作
void recursionMerge(Node<T>* &p)；
//合并结点q到p中（当删除的时候用）
void merge2Node(Node<T>* &p, Node<T>* q);
4。代码实现
a.btree.h
//B树（B-树）的头文件定义
#ifndef BTREE_H
#define BTREE_H
const int M=20;
template<class T>
struct Node{
int keyNum; //the number of key
T key[M]; //the array of key
Node<T>* parent;//point to parent
Node<T>* son[M];//point to sons
//construct function! very important!!!!!!!!!!!
Node(){
parent = 0;
for(int i=0; i<M; i++){
key[i] = 0;
son[i] = 0;
}
}
};
template<class T>
class BTree{
public:
BTree(int m);
//m:B-树的阶，长度为n的数组a
BTree(int m, T a[], int n);
~BTree();
Node<T>* insertBT(T x);
//void insertBT(Node<T>* &root, T x, int pos);//递归还没做出来
Node<T>* deleteBT(T x);
//x是查询关键字；pos是x在结点中的位置；p为k所在结点的双亲结点，如果没找到，也返回失败的叶子结点
Node<T>* search(T x, int *pos, Node<T>* &p);
int height();
void printBT(); //非递归打印
void printBT(Node<T>* root); //递归打印
Node<T>* getRoot();
private:
int m; //m阶B-树
Node<T>* root;
void create(Node<T>* &root);
void release(Node<T>* &root);
void insertList(T a[], int n, T x, int *p); //将x插入有序数组a（递增）,p为插入位置
void insertPoint(Node<T> *a[], int n, Node<T>* p, int pos); //将节点指针p插入指针数组a的位置pos
void deleteList(T *a, int n, int p); //删除数组中位置是p的数据
void deletePoint(Node<T> *a[], int n, int p); //删除数组中位置是p的结点
Node<T>* divideTree(Node<T>* &root, Node<T>* &p); //分裂提升结点p
void modifyParent(Node<T>* &p); //修改结点p的所有孩子结点的父节点为p
//删除需要用的函数
int position(Node<T>* parent, Node<T>* p, T key); //查询结点p在结点parent中的位置，或者关键字在结点parent中的位置
bool borrowFromSib(Node<T>* &parent, Node<T>* p, int pos); //parent为p的双亲，从兄弟借元素（如果兄弟可借，否则什么都不做）,pos是p中待删除元素的位置
bool borrowFromSon(Node<T>* &parent, int pos); //从parent的儿子中借一个然后删除parent中一个关键字（pos是parent待删除位置）
void mergeSib(Node<T>* &parent, int pos, bool flag); //合并在parent中位置在pos处关键字的左右儿子,如果key[pos]是待删除的则设置flag=true
void recursionMerge(Node<T>* &p); //递归合并
void merge2Node(Node<T>* &p, Node<T>* q); //合并结点q到p中
};
#endif
b.btree.cpp
#include <iostream>
#include "btree.h"
using namespace std;
template<class T>
BTree<T>::BTree(int m){
this->m = m;
root = NULL;
create(root);
}
template<class T>
BTree<T>::BTree(int m, T a[], int n){
this->m = m;
root = NULL;
if(n<=0) return;
for(int i=0; i<n; i++){
insertBT(a[i]);
}
}
template<class T>
BTree<T>::~BTree(){
release(root);
}
template<class T>
Node<T>* BTree<T>::getRoot(){
return root;
}
/**
*插入的原则是分裂-提升
*对于m阶子树的：根（非叶子）关键字个数是 1~m-1；非根关键字个数 m/2的上界-1~m-1
*一旦超过这个范围就执行分裂
*/
template<class T>
Node<T>* BTree<T>::insertBT(T x){
Node<T>* r = root;
Node<T>* p = NULL;
int pos = 0; //待插入位置
if(!root){
root = new Node<T>;
root->keyNum = 1;
root->parent = NULL;
//注：结构体key和son都会自己初始化为空
(root->key)[0] = x;
}else{
//如果树中还没有x，就插入；否则，什么都不做，返回
r = search(x, &pos, p);
if(!r){
insertList(p->key, p->keyNum, x, &pos);
p->keyNum++;
}else{
return root;
}
//查看刚才插入的结点p是否达到上界，如果达到关键字上界，就分裂-提升
//分裂-提升：将中间的key拿出来，提升到父结点，然后两边的key分成两个单独的结点，直到root结点
if(p->keyNum >= m){
cout<<"分裂-提升"<<endl;
Node<T>* parent = divideTree(root, p);
while(parent && parent->keyNum >= m){
cout<<"继续提升！"<<endl;
parent = divideTree(root, parent);
}
}
}
return root;
}
//删除，就依据两个原则：借和下降-合并(注：一下降就可能造成其父节点不足，需递归向上)
template<class T>
Node<T>* BTree<T>::deleteBT(T x){
Node<T>* r = root;
Node<T>* p = NULL;
int pos = 0; //待插入位置
int t = 0;
if(!r) return NULL;
else{
r = search(x, &pos, p);
if(!r) return NULL; //搜索x，如果没找到，返回空
else{
int low = m%2==0 ? m/2-1 : m/2;
//1.************************如果待删除的结点是叶子结点************************
if(!r->son[0]){
//1.1.--------如果该结点充足，则直接删除结点--------------------
if(r->keyNum > low){
deleteList(r->key, r->keyNum, pos);
r->keyNum--;
}
//1.2.--------如果该结点不足，兄弟可借(向左或者右兄弟借)--------
else if(p){ //p是当前结点r的父结点
int ps = position(p, r, 0);
bool b = borrowFromSib(p, r, pos);
//1.3.--------如果该节点不足，且兄弟不可借，则下降-合并------------
if(!b){
//将r和其兄弟合并
deleteList(r->key, r->keyNum, pos);
r->keyNum--;
mergeSib(p, ps, false);
if(p->keyNum < low){
cout<<"递归合并"<<endl;
//删除后，其上层不够,递归合并
recursionMerge(p);
}
}
}else{ //p，即r的父为空，则该节点就只有根结点(是叶子并且没有双亲)
deleteList(r->key, r->keyNum, pos);
r->keyNum--;
}
}
//2.***********************如果待删除的结点非叶子***********************
else{
//int ps = positon(p, r, 0);
//2.1.如果儿子可借，则从儿子借
bool b = borrowFromSon(r, pos);
if(b) cout<<"从儿子借\n";
//2.2.如果儿子不可借，则看兄弟是否可借
if(!b){
//2.2.1.如果兄弟可借，则从兄弟借
b = borrowFromSib(p, r, pos);
if(b) cout<<"从兄弟借\n";
//2.2.2.如果兄弟不可借，下降-合并
if(!b){
mergeSib(r, pos, true);
if(r->keyNum < low){
//删除后，其上层不够,递归合并
recursionMerge(r);
}
}
}
}
}
}
return root;
}
/**
* x :待查询关键字；
* *pos :x在结点中的位置，如果没有，就是待插入位置
* *p :返回x所在结点的双亲结点，如果没找到，也返回失败的当前结点
* 返回查找到的节点，如果没有返回空
*/
template<class T>
Node<T>* BTree<T>::search(T x, int *pos, Node<T>* &p){
Node<T>* r = root;
p = NULL;
int n, i;
while(r){
n = r->keyNum;
i = 0;
//找到指针所在位置或指针
if(x<r->key[0]){//就是第一个儿子指针
*pos = 0;
p = r;
r = r->son[0];
}else{//后面位置
while(i<n && x>r->key[i]) i++;
if(x == r->key[i]){
*pos = i;
p = r->parent;
return r;
}else{
p = r;
r = r->son[i];
}
*pos = i;
}
}
//如果r是空的话，说明没有找到
return r;
}
template<class T>
int BTree<T>::height(){
int h = 0;
Node<T>* r = root;
while(r){
h++;
r = r->son[0];
}
return h;
}
/**
*非递归打印
*根据B-树的特点，遍历顺序是关键字从小到大的顺序遍历
*
*/
template<class T>
void BTree<T>::printBT(){
Node<T>* r = root;
bool isLeaf = true; //是否是最下层结点
while(r && r->son[0]){ //如果非一层，则找到起始的结点（最左下结点）
r = r->son[0];
}
Node<T>* pre = NULL; //结点r的遍历前缀结点
int k = 0;
while(r){
if(isLeaf){ //如果是最下层结点,遍历所有结点，之后r指向其父节点
for(int j=0; j<r->keyNum; j++){
cout<<r->key[j]<<" ";
}
pre = r;
r = r->parent;
}else{ //如果不是最下结点，则需要打印其中一个关键字，之后r指向下一个儿子结点
int keyNum = r->keyNum;
for(k=0; k<=keyNum; k++){ //注意这里：儿子指针个数=关键字个数+1
if(r->son[k] == pre){
if(k != keyNum){
cout<<r->key[k]<<" ";
pre = r;
r = r->son[k+1];
}
break;
}
}
//root的一个儿子结点结束，开始另一个，则先要找到其最下层左边第一个结点开始遍历(但是只有两层除外)
if(pre == root && r->son[0]){ //pre是根节点，并且r不是最底层节点
while(r && r->son[0]){ //使找到起始的结点（最左下结点）
r = r->son[0];
}
}
//如果是keyNum+1说明当前结点以及指向了最后儿子结点，遍历完了所有儿子，r之后指向其父
else if(k == keyNum){
pre = r;
r = r->parent;
}
}
//判断当前结点是不是最下层结点
if(r){
if(!r->son[0]) isLeaf = true;
else isLeaf = false;
}
}
}
template<class T>
void BTree<T>::create(Node<T>* &root){
T ch;
cout<<"输入B-树数据(#结束)"<<endl;
while(cin>>ch){
if(ch == '#') break;
insertBT(ch);
}
}
template<class T>
void BTree<T>::insertList(T *a, int n, T x, int *p){
int i=0;//待插入位置
int k=n;
if(x<a[0]){
i = 0;
}else{
while(i<n && x>a[i]) i++;
}
//插入
while(k != i){
a[k] = a[k-1];
k --;
}
a[i] = x;
*p = i;
}
//插入节点指针到son数组
template<class T>
void BTree<T>::insertPoint(Node<T> *a[], int n, Node<T>* p, int pos){
if(!p) return;
int k = n;
//插入
while(k != pos){
a[k] = a[k-1];
k --;
}
a[pos] = p;
}
template<class T>
void BTree<T>::deleteList(T *a, int n, int p){
if(p<0 || p>=n) return;
int k = p;
//删除
while(k != n-1){
a[k] = a[k+1];
k ++;
}
}
template<class T>
void BTree<T>::deletePoint(Node<T> *a[], int n, int p){
if(p<0 || p>=n) return;
int k = p;
//Node<T>* r = a[p];
//删除
while(k != n-1){
a[k] = a[k+1];
k ++;
}
//delete r;
}
/**
* *parent:结点p的父亲结点
* *p :待查询的结点p
* key :待查询的关键字key
* 返回p在parent的位置; 或者key在parent的位置; 如果没找到返回-1
* 注：如果p空，则是按关键字查询，否则是按结点查询（优先结点p查询，不能同时查询两个）
*/
template<class T>
int BTree<T>::position(Node<T>* parent, Node<T>* p, T key){
int pos = 0;
if(!parent) return -1;
int n = parent->keyNum;
//按关键字查询
if(p == NULL){
while(pos < n && key != parent->key[pos]) pos++;
if(pos == n) pos = -1;
}else{
if(p->parent != parent) throw "输入不合法";
while(pos <= n && p != parent->son[pos]) pos++;
if(pos == n+1) pos = -1;
}
return pos;
}
/**
* 分裂-提升结点p（注：由B-树的特点可以知道，插入的结点必定是在最低的结点（即没有叶子结点），增长是自底向上增长）
* *root ：根结点
* *p ：待分裂结点
* 返回 ：分裂后的父节点
* 注意 ：在分裂过程一定不要忘了修改结点的父亲
*/
template<class T>
Node<T>* BTree<T>::divideTree(Node<T>* &root, Node<T>* &p){
int mid = 0;
Node<T>* parent = NULL;
Node<T>* t;
if(p && p->keyNum >= m){
mid = (p->keyNum)/2; //找到结点p关键字的中间位置
parent = p->parent; //找到结点p的父节点，如果存在，则插入父节点；否则，新建节点，作为新父节点
if(!parent){ //无父亲
int i=0;
//新根结点
Node<T>* r = new Node<T>;
r = new Node<T>;
r->keyNum = 1;
r->parent = NULL;
r->key[0] = p->key[mid];
//右结点
Node<T>* right = new Node<T>;
right->keyNum = (p->keyNum)-1-mid;
right->parent = r;
for(i=0; i<mid; i++){
right->key[i] = p->key[mid+1+i];
right->son[i] = p->son[mid+1+i];
}
right->son[i] = p->son[mid+1+i];
//左结点
Node<T>* left = new Node<T>;
left->keyNum = mid;
left->parent = r;
for(i=0; i<left->keyNum; i++){
left->key[i] = p->key[i];
left->son[i] = p->son[i];
}
left->son[i] = p->son[i];
(r->son)[0] = left;
(r->son)[1] = right;
modifyParent(left);
modifyParent(right);
root = r;
parent = r;
}else{ //有父亲
//右结点
int i;
Node<T>* right = new Node<T>;
right->keyNum = (p->keyNum)-1-mid;
right->parent = parent;
for(i=0; i<mid; i++){
right->key[i] = p->key[mid+1+i];
right->son[i] = p->son[mid+1+i];
}
right->son[i] = p->son[mid+1+i];
//左结点
Node<T>* left = new Node<T>;
left->keyNum = mid;
left->parent = parent;
for(i=0; i<left->keyNum; i++){
left->key[i] = p->key[i];
left->son[i] = p->son[i];
}
left->son[i] = p->son[i];
int pos = 0;
//修改父节点
insertList(parent->key, parent->keyNum, p->key[mid], &pos);
parent->keyNum++;
//在父的son数组中插入新结点的左右指针
//注意：首先应该用left替换pos位置的废弃指针———因为它指向的节点提升了，然后插入right
parent->son[pos] = left;
insertPoint(parent->son, parent->keyNum+1, right, pos+1);
modifyParent(left);
modifyParent(right);
}
delete p;
}
return parent;
}
/**
*当分裂-提升之后修改结点的父亲
*p : 已经经过分裂-提升之后的新的双亲
*需要修改的是p的所有儿子的双亲，不在是原来的双亲（已经delete）
*/
template<class T>
void BTree<T>::modifyParent(Node<T>* &p){
//p存在并且有孩子
if(p && p->son[0]){
for(int i=0; i<p->keyNum+1; i++){
p->son[i]->parent = p;
}
}
}
//递归删除
template<class T>
void BTree<T>::release(Node<T>* &root){
if(root){
for(int i=0; i<=root->keyNum; i++){
release(root->son[i]);
}
delete root;
}
}
//递归打印
template<class T>
void BTree<T>::printBT(Node<T>* root){
if(root){
for(int i=0; i<root->keyNum; i++){
printBT(root->son[i]);
cout<<root->key[i]<<" ";
}
printBT(root->son[root->keyNum]);
}
}
/**
* 从兄弟借元素(如果存在，否则什么都不做)
* parent: p的父节点
* p ：有待删除元素的节点
* ps : 待删除元素在p中的位置
*注：parent是p的双亲
*如果存在兄弟可借，则借并返回true，否则false
*/
template<class T>
bool BTree<T>::borrowFromSib(Node<T>* &parent, Node<T>* p, int ps){
bool flag = false, haveSon = false;
if(!p) return flag;
if(p->parent != parent) throw "输入参数有误！";
Node<T>* r, *s;
T k;
int low = m%2==0 ? m/2-1 : m/2;
int pos = position(parent, p, 0);
int i = 0, t=0;
//先找到可借的兄弟
for(i=0; i<=parent->keyNum; i++){
r = parent->son[i];
if(r->keyNum > low){
flag = true;
break;
}
}
if(r->son[0]) haveSon = true;
if(i <= parent->keyNum){
if(i>pos){//找到的兄弟位于p的右边
do{
k = parent->key[i-1];
parent->key[i-1] = r->key[0];
deleteList(r->key, r->keyNum, 0);
s = r->son[0];
deletePoint(r->son, r->keyNum+1, 0);
r->keyNum--;
i--;
r = parent->son[i];
insertList(r->key, r->keyNum, k, &t);
r->keyNum++;
insertPoint(r->son, r->keyNum+1, s, r->keyNum);
}while(r != p);
//插入的位置都是在尾部，故而不用管t
if(haveSon){
mergeSib(p, ps, true);
}else{
deleteList(r->key, r->keyNum, ps);
r->keyNum--;
}
}else{ //位于左边
do{
k = parent->key[i];
parent->key[i] = r->key[r->keyNum-1];
deleteList(r->key, r->keyNum, r->keyNum-1);
s = r->son[r->keyNum];
deletePoint(r->son, r->keyNum+1, r->keyNum);
r->keyNum--;
i++;
r = parent->son[i];
insertList(r->key, r->keyNum, k, &t);
r->keyNum++;
insertPoint(r->son, r->keyNum+1, s, 0);
}while(r != p);
//插在待删除位置前(这是肯定满足的，因为插入的时候都是0位置)
if(t <= ps) ps++;
if(haveSon){
mergeSib(p, ps, true);
}else{
deleteList(r->key, r->keyNum, ps);
r->keyNum--;
}
}
}
return flag;
}
/**
*功能 ：删除父亲结点元素，如果儿子充足，则从儿子借
*parent：待删除元素所在结点
*pos ：待删除元素的位置
*返回 ：如果找到合适son就执行操作并返回true，否则false
*/
template<class T>
bool BTree<T>::borrowFromSon(Node<T>* &parent, int pos){
bool flag = false;
bool haveSon = false;
if(!parent || pos<0 || pos>=parent->keyNum) throw "参数有误！";
if(!parent->son[0]) return flag;
Node<T>* r, *s;
T k;
int low = m%2==0 ? m/2-1 : m/2;
//寻找合适的儿子
int i=0,t=0;
for(i=0; i<=parent->keyNum; i++){
r = parent->son[i];
if(r->keyNum > low){
flag = true;
break;
}
}
if(r->son[0]) haveSon = true;
if(i <= parent->keyNum){
if(i>pos){//如果儿子在右边
while(i != pos+1){
k = parent->key[i-1];
parent->key[i-1] = r->key[0];
deleteList(r->key, r->keyNum, 0);
s = r->son[0];
deletePoint(r->son, r->keyNum+1, 0);
r->keyNum--;
i--;
r = parent->son[i];
insertList(r->key, r->keyNum, k, &t);
r->keyNum++;
insertPoint(r->son, r->keyNum+1, s, r->keyNum);
}
if(haveSon){
parent->key[pos] = r->key[0];
deleteList(r->key, r->keyNum, 0);
s = r->son[0];
deletePoint(r->son, r->keyNum+1, 0);
r->keyNum--;
Node<T>* q = parent->son[pos]->son[parent->son[pos]->keyNum];
merge2Node(q, s);
}else{
parent->key[pos] = r->key[0];
deleteList(r->key, r->keyNum, 0);
r->keyNum--;
}
}else{
while(i != pos){
k = parent->key[i];
parent->key[i] = r->key[r->keyNum-1];
deleteList(r->key, r->keyNum, r->keyNum-1);
s = r->son[r->keyNum];
deletePoint(r->son, r->keyNum+1, r->keyNum);
r->keyNum--;
i++;
r = parent->son[i];
insertList(r->key, r->keyNum, k, &t);
r->keyNum++;
insertPoint(r->son, r->keyNum+1, s, 0);
}
if(haveSon){
parent->key[pos] = r->key[r->keyNum-1];
deleteList(r->key, r->keyNum, r->keyNum-1);
s = r->son[r->keyNum];
deletePoint(r->son, r->keyNum+1, r->keyNum);
r->keyNum--;
Node<T>* m = parent->son[pos+1]->son[0];
merge2Node(s , m);
parent->son[pos+1]->son[0] = s;
modifyParent(parent->son[pos+1]->son[0]);
}else{
parent->key[pos] = r->key[r->keyNum-1];
deleteList(r->key, r->keyNum, r->keyNum-1);
r->keyNum--;
}
}
}
return flag;
}
/**
*将q合并到p之后
*/
template<class T>
void BTree<T>::merge2Node(Node<T>* &p, Node<T>* q){
if(!p || !q) return;
int t, i=0;
for(i=0; i<q->keyNum; i++){
insertList(p->key, p->keyNum, q->key[i], &t);
p->keyNum++;
insertPoint(p->son, p->keyNum+1, q->son[i], p->keyNum);
}
insertPoint(p->son, p->keyNum+1, q->son[i], p->keyNum+1);
delete q;
}
/**
* 合并parent所在pos位置的左右孩子，并将key[pos]下降到合并结点中(下降-合并)
* 注：下降之后，并且删除了父结点中的key,它在合并结点中
* parent : 待合并孩子的双亲结点
* pos ：在parent中孩子指针位置，pos位置的孩子和其左或右孩子是待合并的
* ***如果key[pos]是待删除的则设置flag=true
*/
template<class T>
void BTree<T>::mergeSib(Node<T>* &parent, int pos, bool flag){
if(!parent || pos<0 || pos>parent->keyNum) return;
if(!parent->son[0]) throw "参数有误！";
//将r和其兄弟合并
int t=0;
int pos1,pos2;
if(pos == parent->keyNum){
pos1 = pos-1;
pos2 = pos;
}else{
pos1 = pos;
pos2 = pos+1;
}
Node<T>* r = parent->son[pos1];
Node<T> *x = parent->son[pos2];
if(x){
//将父结点放入左儿子（下降）
insertList(r->key, r->keyNum, parent->key[pos1], &t);
r->keyNum++;
//将右兄弟中的关键字和指针都放到左儿子中(合并)
int i=0;
while(x->keyNum != 0){
insertPoint(r->son, r->keyNum+1, x->son[i++], r->keyNum);
insertList(r->key, r->keyNum, x->key[0], &t);
r->keyNum++;
deleteList(x->key, x->keyNum, 0);
x->keyNum--;
}
insertPoint(r->son, r->keyNum+1, x->son[i], r->keyNum);
delete x;
//如果flag是true，则要删除下降的key
if(flag){
int pp = position(r, NULL, parent->key[pos1]);
if(!r->son[0]){
deleteList(r->key, r->keyNum, pp);
r->keyNum--;
}else{
mergeSib(r, pp, true);
}
}
//删除父节点的关键字和指针
deleteList(parent->key, parent->keyNum, pos1);
deletePoint(parent->son, parent->keyNum+1, pos2);
parent->keyNum--;
if(parent->keyNum == 0){
if(parent == root) root = r;
parent = r;
parent->parent = NULL;
}
modifyParent(r);
}
}
//递归合并，如果p不够就要向上合并
template<class T>
void BTree<T>::recursionMerge(Node<T>* &p){
int low = m%2==0 ? m/2-1 : m/2;
if(p && p->keyNum<low){
//看是否可以从兄弟借，若可借，则借，否则下降-合并
if(!borrowFromSib(p->parent, p, -1)){
cout<<"不可借"<<endl;
//下降-合并
int i = position(p->parent, p, 0);
mergeSib(p->parent, i, false);
recursionMerge(p->parent);
}
}
}
/**
* 递归插入
* *p : 暂存插入位置的节点
* *pos：暂存插入的位置
template<class T>
void BTree<T>::insertBT(Node<T>* &r, T x, int pos){
if(!r){
r = new Node<T>;
r->keyNum = 1;
r->parent = NULL;
(r->key)[0] = x;
return;
}else{
pos = 0;
//在r上搜索插入位置
if(x<r->key[0]){
pos = 0;
}else{//后面位置
while(pos<r->keyNum && x>r->key[pos]) pos++;
if(x == r->key[pos]) return;
}
//是否递归插入,如果在叶子结点，就找到了插入位置，否则递归插入
if(!r->son[pos]){//找到了插入的节点
cout<<"插入结点"<<endl;
insertList(r->key, r->keyNum, x, &pos);
r->keyNum++;
if(r->keyNum >= m){
cout<<"分裂-提升"<<endl;
//divideTree(root, r);
Node<T>* parent = divideTree(root, r);
while(parent && parent->keyNum >= m){
cout<<"继续提升！"<<endl;
parent = divideTree(root, parent);
}
}
return;
}else{//没有找到插入结点，递归插入
insertBT(r->son[pos], x, pos);
}
}
}
*/
c.main.cpp
#include <iostream>
#include "btree.cpp"
using namespace std;
//注意35是‘#’，故而输入的时候注意
int main(){
//int a[] = {23, 40, 12, 50, 80, 42, 6, 7};//, 47, 90, 95
//int a[] = {23,50,80,100,60,55,70,85,87,57,20,89,90,110,52,59,53, 111,114,24,25,26};//, 111,114,115
int a[] = {23,50,80,100,60,55,70,85,87,57,20,89,90,110,52,59,53,21};//
BTree<int> bt(5, a, 18);
//BTree<int> bt(3);
cout<<"非递归打印"<<endl;
bt.printBT();
cout<<"\n递归打印"<<endl;
Node<int>* root = bt.getRoot();
bt.printBT(root);
cout<<"\n高度:"<<bt.height()<<endl;
cout<<"\n搜索"<<endl;
Node<int>* p;
int pos = 0;
p = bt.search(100, &pos, p);
if(p){
for(int i=0; i<p->keyNum; i++) cout<<p->key[i]<<" ";
cout<<"\n位置"<<pos<<" "<<p->keyNum<<endl;
}
/*
cout<<"\n删除叶子，并且充足"<<endl;
bt.deleteBT(54);
bt.printBT();
cout<<"\n删除叶子，叶子不足，兄弟可借（借在左或右）"<<endl;
bt.deleteBT(23);
bt.printBT();
cout<<"\n删除叶子，叶子不足，兄弟不可借"<<endl;
root = bt.deleteBT(70);
bt.printBT();
cout<<endl;
bt.printBT(root);
cout<<endl;
cout<<root->keyNum<<endl;
for(int i=0; i<root->keyNum; i++){
cout<<root->key[i]<<" ";
}
cout<<endl;
for(int i=0; i<=root->keyNum; i++){
cout<<root->son[i]->keyNum<<endl;
for(int j=0; j<root->son[i]->keyNum; j++){
cout<<root->son[i]->key[j]<<" ";
}
cout<<endl;
}
cout<<endl;
*/
/*
cout<<"\n删除非叶子，儿子可借（借在左或右）"<<endl;
root = bt.deleteBT(55);
cout<<root->key[0]<<endl;
for(int i=0; i<root->keyNum+1; i++){
for(int j=0; j<root->son[i]->keyNum; j++){
cout<<root->son[i]->key[j]<<" ";
}
cout<<endl;
}
bt.printBT(root);
cout<<endl;
bt.printBT();
p = bt.search(53, &pos, p);
//p = p->son[p->keyNum];
cout<<p->keyNum<<endl;
for(int i=0; i<p->keyNum+1; i++){
for(int j=0; j<p->son[i]->keyNum; j++){
cout<<p->son[i]->key[j]<<" ";
}
cout<<endl;
}
cout<<"\n删除非叶子，儿子不可借，兄弟不可借"<<endl;
root = bt.deleteBT(85);
bt.printBT(root);
cout<<"\nroot:"<<root->keyNum<<endl;
bt.printBT();
cout<<"\n删除非叶子，儿子不可借，兄弟可借（借在左或右）"<<endl;
bt.deleteBT(85);
bt.printBT();
*/
return 0;
}
分享到：
发表评论
-
排序方法总结
2012-08-12 11:34 1133这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14181.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2774一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 11741.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 12761.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 9071.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
平衡二叉树
2012-08-10 10:39 27941.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14171.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56131.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 11881.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12371.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 25551.二叉树的基本操作 这里我有一个疑问： 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 14931.算法描述 a.数据结构与算法（Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 10751.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 17511.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 12891.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 9541.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1788参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10001.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2231算法描述:生成前N个整 ...
相关推荐
图书管理系统 B-树实现目录索引.rar
这个图书管理只是测试B-树，主要是B-树的实现算法。
B-树 C++实现 基本功能已实现， 代码经过严格测试，应该没有什么问题了
本文章完全是为了实现B-树的功能，代码很全，欢迎下载讨论
B-树作为查找作为查找存储结构，中文单词进行哈希，本中文词典规模在十万级别以上，最长逆向匹配算法实现中文分词。
定义B-树存储结构（要求m3；为方便操作，结点中增加双亲结点指针域，最底层的Fail结点用NULL指针表示并且所有结点均存储于内存）。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
实验内容及要求：定义B-树存储结构（要求m3；为方便操作，结点中增加双亲结点指针域，最底层的Fail结点用NULL指针表示并且所有结点均存储于内存）。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按...
该设计要实现B-数的算法，要求输入一个序列，建立B-树，能够查找指定节点，并且能够遍历整个B-树，输出遍历序列结果。
数据结构课程设计B- B-树算法实现 使用C语言描述，内含VC6.0工程包
旅游管理系统-和B-树的实现
本人学习数据结构时写的B-树的代码，用C++编写的，在Linux上用Gcc 4.5.1编译通过，实现了B-树的构造与删除，以及节点的查找，插入和删除。
数据结构程序设计之B-树的程序与实现。
相关理论知识参见 《数据结构基础》 张力译版 ，我是先实现的B—树， 有B-树的基础上实现的B+树 可以先看B-树 ，再看B+树 。二者实现我已经尽量的使他们相互独立了。
关于b-树的插入，删除等操作的实现，花费了我不少的时间，希望对大家有所帮助
修改严蔚敏《数据结构》B树的实现部分（因为那上面的代码有点bug不能运行）
B-树及图书管理中包括了B-树的建立、数据插入、数据删除、数据查询，以 及 B-树的用途等内容。
定义B-树存储结构（要求m3；为方便操作，结点中增加双亲结点指针域，最底层的Fail结点用NULL指针表示并且所有结点均存储于内存）。定义B-树插入关键字函数、删除关键字函数、查找关键字函数以及按层次遍历输出B-树...
B-树和B+树的C语言实现（数据结构）。
数据结构课程设计是做了玩儿的。 C风格的B-树，支持宏定义N阶
动态打印数据结构中的B-树，可实现其插入、创建、删除和查找。