# 一、定義
### 1、B樹
B樹是為磁盤或其它直接存取輔助存儲設備而設計的一種平衡查找樹,主要特點是降低磁盤I/O操作次數。
B樹以自然的方式推廣二叉查找樹。
B樹的分支因子由磁盤特性所決定。?
### 2、B數的數據結構
int n:當前存儲在結點x中的關鍵字數
key[N]:n個關鍵,以非降序存放
bool leaf;//TRUE:x是葉子;FALSE:x是內結點
node *child[N+1]:只有內結點才有。指向其n+1個孩子的指針。child[1].key <= key[1] <= child[2].key……
### 3.B樹的特征
(1)只有內結點才有指向子女的指針,且child[1].key <= key[1] <= child[2].key……
(2)每個葉結點具有相同的深度
(3)分支因子t>=2
(4)每個非根結點至少有t-1個關鍵字,如果是內結點,至少有t個子女
(5)每個結點至多有2t-1個關鍵字,如果是內結點,到多有2t個子女
### 4.B樹上的操作
B-Tree-Search(x, k)
B-Tree-Create(T)
B-Tree-Split-Child(x,i,y)
B-Tree-Insert(T,k)
B-Tree-Insert-Nonfull(x,k)
B-Tree-Delete(T,x)
# 二、代碼
### B_Tree.h
~~~
#include <iostream>
using namespace std;
#define N 10
int t = 2;
//B樹結點結構
struct node
{
int n;//當前存儲在結點x中的關鍵字數
char key[N];//n個關鍵字,以非降序存放
bool leaf;//TRUE:x是葉子;FALSE:x是內結點
node *child[N+1];//指向其n+1個孩子的指針
//構造函數
node(int num, bool IsLeaf):n(num),leaf(IsLeaf){}
//磁盤讀寫操作
void Disk_Read(){}
void Disk_Write(){}
};
//B樹結構
class B_Tree
{
public:
//指向根結點
node *root;
B_Tree():root(NULL){}
//從以x為根結點的樹中尋找關鍵字為k的結點,若找到,將結果存入y中,返回其是第幾個關鍵字
int B_Tree_Search(node *x, char k, node&y);
//構造一棵帶樹結點的空樹
void B_Tree_Create();
//分裂,把y分裂為兩個結點,選擇其中一個關鍵字插入到x中的第i個位置
void B_Tree_Split_Child(node *x, int i, node *y);
//將關鍵字k插入到一個未滿的結點x中
void B_Tree_Insert_Nonfull(node *x, char k);
//向T中插入關鍵字k
void B_Tree_Insert(char k);
//刪除T樹中關鍵字為k的結點,由于是遞歸方法,當前處理的是x結點
void B_Tree_Delete(node *x, char k);
//按關鍵字從小到大輸出結點
void Print(node *n);
};
//從以x為根結點的樹中尋找關鍵字為k的結點,若找到,將結果存入y中,返回其是第幾個關鍵字
int B_Tree::B_Tree_Search(node *x, char k, node&y)
{
int i = 1;
//找到第一個關鍵字不大于k的i
while(i < x->n && k > x->key[i])
i++;
//若key[i] = k,則找到了
if(i <= x->n && k == x->key[i])
{
//將結果存入y中
y = *x;
//返回其是第幾個關鍵字
return i;
}
//若沒找到,則返回空
if(x->leaf)
{
// &y = NULL;
return 0;
}
//若還有子樹可以找,則遞歸查找第i個子樹
x->child[i]->Disk_Read();
return B_Tree_Search(x->child[i], k, y);
}
//構造一棵帶樹結點的空樹
void B_Tree::B_Tree_Create()
{
//生成一個根結點
//初始時,根結點為葉子結點,根結點中沒有關鍵字
root = new node(0, true);
root->Disk_Write();
}
//分裂,把y分裂為兩個結點,選擇其中一個關鍵字插入到x中的第i個位置
void B_Tree::B_Tree_Split_Child(node *x, int i, node *y)
{
int j;
//生成一個新結點z
//要把y分裂為y和z,因此z的葉子屬性與y相同
//分裂前y有2t-1個關鍵字,分裂后前t-1個屬于y,后t-1個屬于z,中間第t個屬于x
node *z = new node(t-1, y->leaf);
y->n = t - 1;
//后t-1個關鍵字依次復制給z
for(j = 1; j < t; j++)
z->key[j] = y->key[j+t];
//如果有孩子,孩子也要復制過去,原來有2t個子樹,前t個屬于y,后t個屬于z
if(y->leaf == false)
{
for(j = 1; j <= t; j++)
z->child[j] = y->child[j+t];
}
//使z作為x的第i+1個孩子(y已經是x的第i個孩子)
for(j = x->n+1; j > i; j--)
x->child[j+1] = x->child[j];
x->child[i+1] = z;
//把y中第t個關鍵字插入到x的第i個位置
for(j = x->n; j >= i; j--)
x->key[j+1] = x->key[j];
x->key[i] = y->key[t];
//x的關鍵字+1
x->n++;
y->Disk_Write();
z->Disk_Write();
x->Disk_Write();
}
//將關鍵字k插入到一個未滿的結點x中
void B_Tree::B_Tree_Insert_Nonfull(node *x, char k)
{
int i = x->n;
//若x是葉子結點
if(x->leaf)
{
//找到該插入的位置
while(i >= 1 && k < x->key[i])
{
x->key[i+1] = x->key[i];
i--;
}
//插入關鍵字k
x->key[i+1] = k;
x->n++;
x->Disk_Write();
}
//若不是葉子結點
else
{
//找到該插入的位置
while(i >= 1 && k < x->key[i])
i--;
i++;
//讀取其孩子,將關鍵字插入到它的孩子中,分兩種情況
x->child[i]->Disk_Read();
//孩子已滿
if(x->child[i]->n == 2 * t - 1)
{
//對孩子執行分裂操作,分裂后,孩子不變為不滿
B_Tree_Split_Child(x, i, x->child[i]);
if(k > x->key[i])
i++;
}
//孩子不滿,直接對孩子進行插入操作
B_Tree_Insert_Nonfull(x->child[i], k);
}
}
//向T中插入關鍵字k
void B_Tree::B_Tree_Insert(char k)
{
node *r = root, *s;
//若根結點已滿
if(r->n == 2*t-1)
{
//申請一個新的結點,將新的結點作為根結點
root = new node(0, false);
root->child[1] = r;
//將原根結點分裂為兩個結點,分別作為s的第0個孩子和第1個孩子
B_Tree_Split_Child(root, 1, r);
//把關鍵字k插入到根結點中,此時根結點一定不滿
B_Tree_Insert_Nonfull(root, k);
}
//若根結點不滿
else
//直接把關鍵字插入到根結點中
B_Tree_Insert_Nonfull(r, k);
}
//刪除T樹中關鍵字為k的結點,由于是遞歸方法,當前處理的是x結點
void B_Tree::B_Tree_Delete(node *x, char k)
{
int i, j;
//找到x中第一個不小于k的關鍵字,即待處理的位置
for(i = 1; i <= x->n; i++)
if(x->key[i] >= k)
break;
//y是關鍵字k之前的結點,即小于k的最大孩子
//z是關鍵字k之后的結點,即大于k的最小孩子
node *y = x->child[i], *z = x->child[i+1], *d;
//若關鍵字k在結點x中的第i個位置
if(x->key[i] == k && i <= x->n)
{
//1)y是葉子結點,則直接從x中刪除k
if(x->leaf == true)
{
//關鍵字依次前移
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//關鍵字數-1
x->n--;
return;
}
//2)x是內結點
//2-a:x中前于k的子結點y包含至少t個關鍵字
if(y->n >= t)
{
//找出k在以y為根的子樹中的前驅d
d = y;
while(d->leaf == false)
d = d->child[d->n+1];
//用d取代k
x->key[i] = d->key[d->n];
//遞歸地刪除d
B_Tree_Delete(y, d->key[d->n]);
}
//2-b:x是位于k之后的子結點z包含至少t個關鍵字
else if(z->n >= t)
{
//找出k在以z為根的子樹中的后繼d
d = z;
while(d->leaf == false)
d = d->child[1];
//用d取代k
x->key[i] = d->key[1];
//遞歸地刪除d
B_Tree_Delete(z, d->key[1]);
}
//2-c:y和z都只有t-1個關鍵字,將k和z中所有關鍵字合并進y,使得x失去k和指向z的指針
else
{
//將k關鍵字合并進y
y->key[y->n+1] = k;
//將z中所有關鍵字合并進y
for(j = 1; j <= z->n; j++)
y->key[y->n+j+1] = z->key[j];
//如果有孩子,孩子也要合并
if(y->leaf == false)
{
//使得x指向z的指針
for(j = 1; j <= z->n+1; j++)
y->child[y->n+j+1] = z->child[j];
}
//y包含2t-1個關鍵字
y->n = y->n + 1 + z->n;
//使得x失去k
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//使x失去指向z的指針
for(j = i+1; j <= x->n; j++)
x->child[j] = x->child[j+1];
x->n--;
//如果x是根結點,x
if(x->n == 0 && root == x)
root = y;
//釋放z
delete z;
//將k從y中遞歸刪除
B_Tree_Delete(y, k);
}
}
//3)關鍵字不在結點x中,則必定包含k的正確的子樹的根x->child[i]
else
{
//x是葉子結點,找到根結點都沒有找到k,則k不在樹中
if(x->leaf == true)
{
cout<<"error:not exist"<<endl;
return;
}
//x是內結點
//3-a:child[i]中只有t-1個關鍵字
if(y->n == t-1)
{
//它的相鄰兄弟x->child[i+1](用z表示)包含至少t個關鍵字
if(i <= x->n && i <= x->n && z->n >= t)
{
//將x中的關鍵字下降至y
y->n++;
y->key[y->n] = x->key[i];
//將z的某一關鍵字上升至x
x->key[i] = z->key[1];
for(j = 1; j < z->n; j++)
z->key[j] = z->key[j+1];
//將z適合的子女指針移到y
if(y->leaf == false)
{
y->child[y->n+1] = z->child[1];
for(j = 1; j <= z->n; j++)
z->child[j] = z->child[j+1];
}
//z的關鍵字數-1
z->n--;
}
//它的相鄰兄弟x->child[i-1]包含至少t個關鍵字
else if(i > 1 && x->child[i-1]->n >= t )
{
//將x中的關鍵字下降至y
for(j = y->n; j >= 1; j--)
y->key[j+1] = y->key[j];
y->key[1] = x->key[i-1];
y->n++;
//將y的相鄰兄弟x->child[i-1]的某一關鍵字上升至x
x->key[i-1] = x->child[i-1]->key[x->child[i-1]->n];
//將該兄弟適合的子女指針移到y
if(y->leaf == false)
{
for(j = y->n; j >= 1; j--)
y->child[j+1] = y->child[j];
y->child[1] = x->child[i-1]->child[x->child[i-1]->n+1];
}
//x->child[i-1]的關鍵字數-1
x->child[i-1]->n--;
}
//y和其所有相鄰兄弟都只有t-1個關鍵字,則與其中一個兄弟合并
else
{
//與后面一個結點(用z表示)合并
if(i <= x->n)
{
//將x->key[i]并入y中
y->key[y->n+1] = x->key[i];
//將z中所有關鍵字并入y中
for(j = 1; j <= z->n; j++)
y->key[j+y->n+1] = z->key[j];
//如果有孩子,所有孩子也要并入
if(y->leaf == false)
{
for(j = 1; j <= z->n+1; j++)
y->child[j+y->n+1] = z->child[j];
}
//修改y的關鍵字數
y->n = y->n + 1 + z->n;
//將x->key[i]從x中移出
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//把指向z的指針從x->child中移出
for(j = i+1; j <= x->n; j++)
x->child[j] = x->child[j+1];
//x的關鍵字數-1
x->n--;
//若根結點被刪除,更新根結點
if(x->n==0 && root == x)
root = y;
}
//與前面一個結點合并
else
{
//令z=x->child[i-1],y=x->child[i],把z并入y中
z = y;i--;
y = x->child[i];
//將x->key[i]并入y中
y->key[y->n+1] = x->key[i];
//將z中所有關鍵字并入y中
for(j = 1; j <= z->n; j++)
y->key[j+y->n+1] = z->key[j];
//如果有孩子,所有孩子也要并入
if(y->leaf == false)
{
for(j = 1; j <= z->n+1; j++)
y->child[j+y->n+1] = z->child[j];
}
//修改y的關鍵字數
y->n = y->n + 1 + z->n;
//將x->key[i]從x中移出
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//把指向z的指針從x->child中移出
for(j = i+1; j <= x->n; j++)
x->child[j] = x->child[j+1];
//x的關鍵字數-1
x->n--;
//若根結點被刪除,更新根結點
if(x->n==0 && root == x)
root = y;
}
}
}
//遞歸執行刪除操作
B_Tree_Delete(y, k);
}
}
//按關鍵字從小到大輸出結點
void B_Tree::Print(node *n)
{
int i;
for(i = 1; i <= n->n; i++)
{
if(n->leaf == false)
Print(n->child[i]);
cout<<n->key[i]<<' ';
}
if(n->leaf == false)
Print(n->child[n->n+1]);
}
~~~
### main.cpp
~~~
#include <iostream>
using namespace std;
#include "B_Tree.h"
int main()
{
//測試數據
char ch[] = {'F','S','Q','K','C','L','H','T','V','W','M','R','N','P','A','B','X','Y','D','Z','E'};
//生成一棵B樹
B_Tree *T = new B_Tree;
T->B_Tree_Create();
//依次插入關鍵字
cout<<"插入測試"<<endl;
int i;
for(i = 0; i < 21; i++)
{
T->B_Tree_Insert(ch[i]);
T->Print(T->root);
cout<<endl;
}
//輸出這棵樹
T->Print(T->root);
cout<<endl;
//B樹刪除操作測試
cout<<"查找與刪除測試"<<endl;
char c;
for(i = 0; i < 100; i++)
{
cin>>c;
T->B_Tree_Delete(T->root, c);
T->Print(T->root);
cout<<endl;
}
return 0;
}
~~~
# 三、練習
### 18.1B樹的定義
18.1-1
若t=1,樹中的結點最少有0個關鍵字,就沒有意義了
18.1-2
t=2
18.1-3
[http://zh.clrs-ans.wikia.com/index.php?title=18.1_B%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89&variant=zh-cn](http://zh.clrs-ans.wikia.com/index.php?title=18.1_B%E6%A0%91%E7%9A%84%E5%AE%9A%E4%B9%89&variant=zh-cn)




18.1-4
2^(2t)-1
18.1-5
沒看懂題目
### 18.2對B樹的基本操作
18.2-1

18.2-2
待解決
[http://bbs.csdn.net/topics/390279127](http://bbs.csdn.net/topics/390279127)
18.2-3
類似于紅黑樹中的找前驅和后繼的操作
~~~
//若要找x->key[i]的前驅d
d = x->child[i];
while(d->leaf == false)
d = d->child[d->n+1];
~~~
~~~
//若要找x->key[i]的后繼d
d = x->child[i+1];
while(d->leaf == false)
d = d->child[1];
~~~
18.2-4
在網上找了份答案 說是 至少n - 2lg(N) - 2個節點 沒有解答! 總之漸進意義上說 是n個 沒必要太糾結與細節
沒想到怎么求,寫了個程序來計算,依次插入1-n,每分裂一次就cnt+1
~~~
#include <iostream>
using namespace std;
#define N 10
int t = 2, cnt;
//B樹結點結構
struct node
{
int n;//當前存儲在結點x中的關鍵字數
int key[N];//n個關鍵字,以非降序存放
bool leaf;//TRUE:如果x是葉子FALSE:內結點
node *child[N+1];//指向其n+1個孩子的指針
};
//B樹結構
struct B_Tree
{
//指向根結點
node *root;
};
//磁盤讀寫操作
void Disk_Read(node *x){}
void Disk_Write(node *x){}
//構造一棵帶樹結點的空樹
void B_Tree_Create(B_Tree *T)
{
//生成一個根結點
node *x = new node;
//初始時,根結點為葉子結點
x->leaf = true;
//初始時,根結點中沒有關鍵字
x->n = 0;
Disk_Write(x);
T->root = x;
cnt = 1;
}
//分裂,把y分裂為兩個結點,選擇其中一個關鍵字插入到x中的第i個位置
void B_Tree_Split_Child(node *x, int i, node *y)
{
cnt++;
int j;
//生成一個新結點z
node *z = new node;
//要把y分裂為y和z,因此z的葉子屬性與y相同
z->leaf = y->leaf;
//分裂前y有2t-1個關鍵字,分裂后前t-1個屬于y,后t-1個屬于z,中間第t個屬于x
z->n = t - 1;y->n = t - 1;
//后t-1個關鍵字依次復制給z
for(j = 1; j < t; j++)
z->key[j] = y->key[j+t];
//如果有孩子,孩子也要復制過去,原來有2t個子樹,前t個屬于y,后t個屬于z
if(y->leaf == false)
{
for(j = 1; j <= t; j++)
z->child[j] = y->child[j+t];
}
//使z作為x的第i+1個孩子(y已經是x的第i個孩子)
for(j = x->n+1; j > i; j--)
x->child[j+1] = x->child[j];
x->child[i+1] = z;
//把y中第t個關鍵字插入到x的第i個位置
for(j = x->n; j >= i; j--)
x->key[j+1] = x->key[j];
x->key[i] = y->key[t];
//x的關鍵字+1
x->n++;
Disk_Write(y);
Disk_Write(z);
Disk_Write(x);
}
//將關鍵字k插入到一個未滿的結點x中
void B_Tree_Insert_Nonfull(node *x, int k)
{
int i = x->n;
//若x是葉子結點
if(x->leaf)
{
//找到該插入的位置
while(i >= 1 && k < x->key[i])
{
x->key[i+1] = x->key[i];
i--;
}
//插入關鍵字k
x->key[i+1] = k;
x->n++;
Disk_Write(x);
}
//若不是葉子結點
else
{
//找到該插入的位置
while(i >= 1 && k < x->key[i])
i--;
i++;
//讀取其孩子,將關鍵字插入到它的孩子中,分兩種情況
Disk_Read(x->child[i]);
//孩子已滿
if(x->child[i]->n == 2 * t - 1)
{
//對孩子執行分裂操作,分裂后,孩子不變為不滿
B_Tree_Split_Child(x, i, x->child[i]);
if(k > x->key[i])
i++;
}
//孩子不滿,直接對孩子進行插入操作
B_Tree_Insert_Nonfull(x->child[i], k);
}
}
//向T中插入關鍵字k
void B_Tree_Insert(B_Tree *T, int k)
{
node *r = T->root;
//若根結點已滿
if(r->n == 2*t-1)
{
//申請一個新的結點
node *s = new node;
//將的結點作為根結點
T->root = s;
s->leaf = false;
s->n = 0;
s->child[1] = r;
//將原根結點分裂為兩個結點,分別作為s的第0個孩子和第1個孩子
B_Tree_Split_Child(s, 1, r);
//把關鍵字k插入到根結點中,此時根結點一定不滿
B_Tree_Insert_Nonfull(s, k);
}
//若根結點不滿
else
//直接把關鍵字插入到根結點中
B_Tree_Insert_Nonfull(r, k);
}
int main()
{
//生成一棵B樹
B_Tree *T = new B_Tree;
B_Tree_Create(T);
//依次插入關鍵字
int i;
for(i = 1; i <= 100; i++)
{
B_Tree_Insert(T, i);
cout<<i<<' '<<cnt<<' '<<endl;
}
return 0;
}
~~~
18.2-5
見[算法導論-18.2-5-B樹葉結點無指針](http://blog.csdn.net/mishifangxiangdefeng/article/details/7945167)
18.2-7
一棵具有n個結點且度為t的B樹,可計算其高度h(P266定理18.1)。對一棵B樹的操作時間T=讀取磁盤頁的時間*讀取磁盤頁的次數。根據代碼可知,讀取磁盤頁的次數=B樹的高度。
T = (a+bt)*h,代入a,b,h,求T的最大值
### 18.3從B樹中刪除關鍵字
18.3-2
木有偽代碼,直接上代碼
# 四、思考題
### 18-1輔存上的棧
a)2n次,O(mn)
假設一直是PUSH,且頁面字數接近于m
b)2(n/m)次,O((n/m)*m)
每連續個字m個字處理一次,共處理n/m次。每次處理包括存一次(m個字),取一次(0個字)
c)2n次,O(mn)
最壞情況下,當頁面滿時PUSH,當頁面只有一個字是POP,其中:
PUSH操作:存一次(m個字),取一次(0個字)
POP操作:存一次(0個字),取一次(m個字)
d)待解決
### 18-2連接與分裂2-3-4樹
見[算法導論-18-2-連接與分裂2-3-4樹](http://blog.csdn.net/mishifangxiangdefeng/article/details/7957517)
關于2樓問題的解答:
~~~
//刪除T樹中關鍵字為k的結點,由于是遞歸方法,當前處理的是x結點
void B_Tree::B_Tree_Delete2(node *x, char k)
{
int i, j;
//找到x中第一個不小于k的關鍵字,即待處理的位置
for(i = 1; i <= x->n; i++)
if(x->key[i] >= k)
break;
//y是關鍵字k之前的結點,即小于k的最大孩子
//z是關鍵字k之后的結點,即大于k的最小孩子
node *y = x->child[i], *z = x->child[i+1], *d;
//若關鍵字k在結點x中的第i個位置
if(x->key[i] == k && i <= x->n)
{
//1)y是葉子結點,則直接從x中刪除k
if(x->leaf == true)
{
//關鍵字依次前移
for(j = i; j < x->n; j++)
x->key[j] = x->key[j+1];
//關鍵字數-1
x->n--;
return;
}
//2)x是內結點
//2-a:x中前于k的子結點y包含至少t個關鍵字
if(y->n >= t)
{
//找出k在以y為根的子樹中的前驅d
d = y;
while(d->leaf == false)
d = d->child[d->n+1];
//用d取代k
x->key[i] = d->key[d->n];
//遞歸地刪除d
B_Tree_Delete2(y, d->key[d->n]);
}
//2-b:x是位于k之后的子結點z包含至少t個關鍵字
else if(z->n >= t)
{
//找出k在以z為根的子樹中的后繼d
d = z;
while(d->leaf == false)
d = d->child[1];
//用d取代k
x->key[i] = d->key[1];
//遞歸地刪除d
B_Tree_Delete2(z, d->key[1]);
}
//2-c:y和z都只有t-1個關鍵字,將k和z中所有關鍵字合并進y,使得x失去k和指向z的指針
else
{
//將z并入y中,y是x的第i個孩子
B_Tree_Merge(x, y, z, i);
//將k從y中遞歸刪除
B_Tree_Delete2(y, k);
}
}
//3)關鍵字不在結點x中,則必定包含k的正確的子樹的根x->child[i]
else
{
//x是葉子結點,找到根結點都沒有找到k,則k不在樹中
if(x->leaf == true)
{
cout<<"error:not exist"<<endl;
return;
}
//x是內結點
//3-a:child[i]中只有t-1個關鍵字
if(y->n == t-1)
{
//它的相鄰兄弟x->child[i+1](用z表示)包含至少t個關鍵字
if(i <= x->n && i <= x->n && z->n >= t)
{
//將x中的關鍵字下降至y
y->n++;
y->key[y->n] = x->key[i];
//將z的某一關鍵字上升至x
x->key[i] = z->key[1];
for(j = 1; j < z->n; j++)
z->key[j] = z->key[j+1];
//將z適合的子女指針移到y
if(y->leaf == false)
{
y->child[y->n+1] = z->child[1];
for(j = 1; j <= z->n; j++)
z->child[j] = z->child[j+1];
}
//z的關鍵字數-1
z->n--;
}
//它的相鄰兄弟x->child[i-1]包含至少t個關鍵字
else if(i > 1 && x->child[i-1]->n >= t )
{
//將x中的關鍵字下降至y
for(j = y->n; j >= 1; j--)
y->key[j+1] = y->key[j];
y->key[1] = x->key[i-1];
y->n++;
//將y的相鄰兄弟x->child[i-1]的某一關鍵字上升至x
x->key[i-1] = x->child[i-1]->key[x->child[i-1]->n];
//將該兄弟適合的子女指針移到y
if(y->leaf == false)
{
for(j = y->n; j >= 1; j--)
y->child[j+1] = y->child[j];
y->child[1] = x->child[i-1]->child[x->child[i-1]->n+1];
}
//x->child[i-1]的關鍵字數-1
x->child[i-1]->n--;
}
//y和其所有相鄰兄弟都只有t-1個關鍵字,則與其中一個兄弟合并
else
{
//與后面一個結點(用z表示)合并
if(i <= x->n)
{
//將z并入y中,y是x的第i個孩子
B_Tree_Merge(x, y, z, i);
//將k從y中遞歸刪除
B_Tree_Delete2(y, k);
}
//與前面一個結點合并
else
{
//將y并入z中,z是x的第i-1個孩子
B_Tree_Merge(x, z, y, i-1);
//將k從z中遞歸刪除
B_Tree_Delete2(z, k);
}
}
}
//遞歸執行刪除操作
B_Tree_Delete2(y, k);
}
}
//left是parent的第pos個孩子,right是parent的第pos+1個孩子,把parent->key[pos]和right都合并到left中
void B_Tree::B_Tree_Merge(node *parent, node *left, node *right, int pos)
{
int j;
//將k關鍵字合并進left
left->key[left->n+1] = parent->key[pos];
//將right中所有關鍵字合并進left
for(j = 1; j <= right->n; j++)
left->key[left->n+j+1] = right->key[j];
//如果有孩子,孩子也要合并
if(left->leaf == false)
{
//使得parent指向z的指針
for(j = 1; j <= right->n+1; j++)
left->child[left->n+j+1] = right->child[j];
}
//left包含2t-1個關鍵字
left->n = left->n + 1 + right->n;
//使得parent失去k
for(j = pos; j < parent->n; j++)
parent->key[j] = parent->key[j+1];
//使parent失去指向right的指針
for(j = pos+1; j <= parent->n; j++)
parent->child[j] = parent->child[j+1];
parent->n--;
//如果x是根結點,x
if(parent->n == 0 && root == parent)
root = left;
//釋放z
delete right;
}
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
~~~
- 前言
- 第6章 堆排序
- 6-3 Young氏矩陣
- 第7章 快速排序
- 第8章 線性時間排序
- 第9章 排序和順序統計學算法導論
- 算法導論 9.1-1 求第二小元素
- 第10章 10.1 棧和隊列
- 第10章 10.2 鏈表
- 第10章 10.3 指針和對象實現
- 第10章 10.4 有根樹的表示
- 第11章-散列表
- 第12章 二叉查找樹
- 第13章 紅黑樹
- 第14章 14.1 動態順序統計
- 算法導論-14-1-最大重疊點
- 算法導論-14-2-Josephus排列
- 第14章 14.3 區間樹
- 第15章 動態規劃
- 第16章 貪心算法
- 第18章 B樹
- 第19章-二項堆
- 第20章 斐波那契堆
- 第21章 用于不相交集合的數據結構
- 第22章 圖的基本算法 22.1 圖的表示
- 第22章 圖算法 22.2 廣度優先搜索
- 第22章 圖算法 22.3 深度優先搜索
- 第22章 圖的基本算法 22.4 拓撲排序
- 第22章 圖的基本算法 22.5 強聯通分支