hao3100590
- 浏览: 131805 次
- 性别:
- 来自: 成都
-
最新评论
-
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 1178这里面包含了所有常见的排序操作 1.性能等比较分析 2 ... -
常见字符串操作大全
2012-08-12 11:34 14631.常见的字符串操作 如计算长度，求子串等都是考验基本功的， ... -
KMP算法解析
2012-08-12 11:35 2841一.理论基础 1.什么 ... -
二叉堆的实现
2012-08-12 11:35 12121.堆的概念 这里只需要注意两点： a.堆的存储方式：就是 ... -
set和map的简单实现
2012-08-10 11:35 13211.Set的简单实现 set是利用二叉查找树来实现的,而且为 ... -
红黑树的插入总结
2012-08-10 11:25 14091.红黑树 这个在july的博客中有详尽的说明，我就不在赘述 ... -
平衡二叉树
2012-08-10 10:39 28601.问题描述 什么是平衡 ... -
二叉排序树
2012-08-10 10:25 14861.基本概念 二叉排 ... -
B-树
2012-07-04 22:48 56771.B-树的概念 是一种多 ... -
构造哈夫曼树
2012-07-04 10:40 12331.算法说明 就是建造哈夫曼树树，从而使得构造出的树带权路径 ... -
线索二叉树
2012-07-04 09:20 12761.算法描述 就是简单的线索二叉树的建立，遍历，查找等基本操 ... -
二叉树基本操作大全
2012-07-03 18:22 26081.二叉树的基本操作 这里我有一个疑问： 在使用构造 ... -
多种队列的实现
2012-06-29 10:09 15621.算法描述 a.数据结构与算法（Mark Allen We ... -
栈的各种实现
2012-06-28 16:34 11091.算法描述 a.实现二个栈，在一个数组里面，除非没有任何空 ... -
中缀表达式转换为后缀
2012-06-28 11:10 18371.算法描述 例如a+b*c这是常见的中缀表达式，但是 ... -
后缀表达式的值
2012-06-27 16:33 13361.算法描述 计算后缀表达式的值 2.事例 如：（ ... -
Josephus问题
2012-06-21 15:30 10021.算法描述 简单的游戏：有N个人坐成一圈，编号1-N、从编 ... -
关于最长递增子序列的实际应用--动态规划
2012-06-07 11:35 1837参考链接： a.http://www.programfan. ... -
线性查找二维数组
2012-06-05 17:23 10311.算法描述 有序（行有序，列有序，且每行从左至右递增 ... -
整数的随机置换
2012-06-05 15:10 2325算法描述:生成前N个整 ...
相关推荐
《基于B-树实现的图书管理系统》 在计算机科学领域，数据结构的选择对系统的性能有着至关重要的影响。在这个图书管理系统中，我们运用了B-树（B-tree）这一经典的数据结构，来高效地管理和检索图书信息。B-树是...
"BMT"可能是"B-Tree Main Test"的缩写，这可能是一个主测试程序，用来验证B-树实现的正确性和性能。 在具体实现时，需要注意的是，C++标准库并不直接支持B-树这样的数据结构，因此我们需要自己编写代码来实现。同时...
《B-树实现的中文词典》 在信息技术领域，数据结构是构建高效算法的基础，而B-树（B-tree）作为一种自平衡的查找树，因其高效的数据存储和检索特性，常被用于数据库和文件系统中。在这个项目中，B-树被用来实现一个...
《图书管理系统 B-树实现目录索引》 在IT领域，数据结构是计算机科学的基础，B-树（B-Tree）作为一种自平衡的查找树，常用于数据库和文件系统中，以实现高效的检索效率。本项目是针对图书管理系统的目录索引实现，...
### B-树的实现与分析 B-树是一种自平衡的树数据结构，常用于数据库和文件系统中，因其能够高效地支持查找、插入和删除操作，并且在磁盘读写方面具有很好的性能。本文将从给定的代码片段出发，深入解析B-树的关键...
在本项目中，我们将深入探讨B- B-树（通常指的是B-树或B+树）的实现，并以C语言为编程工具，结合VC6.0开发环境进行实践。 B-树的核心特性在于它的分层结构，每个节点可以有多个子节点，这使得它在处理大量数据时...
标题中的"B.rar_B-树索引_B树_b tree_b tree java_java B-Tree"表明这是一个关于B-树实现的压缩文件，其中包含了用Java语言编写的B-树索引代码，并且含有详细的注释。这为学习和理解B-树提供了实践示例。 首先，...
在“B-TreeProject”这个项目中，你将会看到一个完整的B-树实现，包括BTreeNode类、插入和删除的函数，以及可能的测试用例。通过阅读和运行代码，你可以更深入地理解B-树的工作原理，并学习如何在实际编程中应用数据...
**数据结构实验报告 - B-树基本操作的实现** 本次实验主要关注B-树这一重要的数据结构，它在数据库和文件系统中有着广泛的应用。B-树是一种自平衡的多路搜索树，能够保持数据排序并高效地进行查找、插入和删除操作...
3. **函数声明**: 提供的代码还包含了若干个函数的声明，这些函数用于实现B-树的各种操作： - `btreesearch`: 查找键值。 - `btreeinsert`: 插入键值。 - `btreedelete`: 删除键值。 - `height`: 计算树的高度。...
在这个“B-树的源代码”项目中，开发者使用C++语言实现了B-树的基本操作，包括构造、查找、插入和删除节点。C++是一种广泛应用的面向对象编程语言，具有高效和灵活的特点，适合编写这种底层数据结构的代码。 B-树的...
本项目提供的源代码是C++实现的B-树和B+树，有助于学习者深入理解这两种数据结构的内部机制。 首先，B-树（Balanced Tree）是一种自平衡的多路搜索树，它的每个节点可以有多个子节点，通常为2到32个。B-树的主要...
2. **树形结构**：如二叉树、平衡树和B-树。二叉树是最简单的树形结构，每个节点最多有两个子节点。平衡树，如AVL树和红黑树，是为了保持搜索效率而设计的，它们确保任何节点的左右子树高度差不超过1。B-树是一种自...
**数据结构实验报告 - B-树基本操作的实现** 本次实验是关于B-树的数据结构操作，主要涉及插入、删除、查找以及层次遍历等基本功能。B-树是一种自平衡的多路查找树，广泛应用于数据库和文件系统中，以高效地处理...
B-树是一种自平衡的树数据结构，主要用于数据库和文件系统中，以高效地存储和检索大量数据。在B-树中，每个节点可以拥有多个子节点，最多可...在实际应用中，Java等编程语言可以通过实现B-树的数据结构来提供这些功能。
本教程将详细阐述如何动态地打印B-树，以及如何实现其基本操作：插入、创建、删除和查找。 首先，B-树是一种多路搜索树，每个节点可以有多个子节点。它的特性在于所有叶子节点都在同一层，且每个节点存储的关键字...
本次课程设计的目标是理解和实现B-树数据结构，这是一种高效的数据存储和检索方法，尤其适用于大量数据的管理和操作。学生将在Windows环境下使用Devc++开发软件进行编程，最低硬件要求为奔腾处理器和32MB内存，但...
"完整的B-树实现源码，包括注释、详细讲解、相关的报告文档及ppt" 提供的资源可以帮助我们深入理解B-树的内部工作机制。源码提供了直观的实现细节，注释有助于理解代码逻辑，报告文档和PPT则可能包含理论介绍、算法...
通过以上分析可以看出，这段代码主要实现了B-树的基本功能，包括节点结构体的定义、查找操作以及插入操作。其中涉及到了关键的B-树维护操作，例如节点分裂和新建根节点，这些操作确保了B-树能够在保持平衡的同时支持...
根据给定的信息，本文将详细解析B-树的实现与分析。B-树是一种非常重要的数据结构，在数据库索引、文件系统以及其他需要高效查找、插入和删除操作的应用场景中广泛使用。 ### B-树的基本概念 B-树是一种自平衡的多...