<ruby id="bdb3f"></ruby>

    <p id="bdb3f"><cite id="bdb3f"></cite></p>

      <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
        <p id="bdb3f"><cite id="bdb3f"></cite></p>

          <pre id="bdb3f"></pre>
          <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

          <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
          <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

          <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                <ruby id="bdb3f"></ruby>

                ThinkChat2.0新版上線,更智能更精彩,支持會話、畫圖、視頻、閱讀、搜索等,送10W Token,即刻開啟你的AI之旅 廣告
                # 一、定義 ### 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) ![](https://box.kancloud.cn/2016-02-02_56b02bd11a636.gif) ![](https://box.kancloud.cn/2016-02-02_56b02bd129ccc.gif) ![](https://box.kancloud.cn/2016-02-02_56b02bd138146.gif) ![](https://box.kancloud.cn/2016-02-02_56b02bd145ed7.gif) 18.1-4 2^(2t)-1 18.1-5 沒看懂題目 ### 18.2對B樹的基本操作 18.2-1 ![](https://box.kancloud.cn/2016-02-02_56b02bd151e4c.jpg) 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; } ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~ ~~~
                  <ruby id="bdb3f"></ruby>

                  <p id="bdb3f"><cite id="bdb3f"></cite></p>

                    <p id="bdb3f"><cite id="bdb3f"><th id="bdb3f"></th></cite></p><p id="bdb3f"></p>
                      <p id="bdb3f"><cite id="bdb3f"></cite></p>

                        <pre id="bdb3f"></pre>
                        <pre id="bdb3f"><del id="bdb3f"><thead id="bdb3f"></thead></del></pre>

                        <ruby id="bdb3f"><mark id="bdb3f"></mark></ruby><ruby id="bdb3f"></ruby>
                        <pre id="bdb3f"><pre id="bdb3f"><mark id="bdb3f"></mark></pre></pre><output id="bdb3f"></output><p id="bdb3f"></p><p id="bdb3f"></p>

                        <pre id="bdb3f"><del id="bdb3f"><progress id="bdb3f"></progress></del></pre>

                              <ruby id="bdb3f"></ruby>

                              哎呀哎呀视频在线观看