import?java.util.*;


//////?DisposeRoot?///////中的key參數(shù)有些問題

public?class?BTree?{
??//用于記錄每個(gè)節(jié)點(diǎn)中的鍵值數(shù)量
??public?int?keyAmount;
??//樹的根節(jié)點(diǎn)
??public?Node?root;

??public?BTree（int?keyAmount）?{
????this.keyAmount?=?keyAmount;
????this.root?=?new?Node（keyAmount）;
??}



??//在B樹中插入葉節(jié)點(diǎn)/////////////////////////////////////////////////////////////
??public?void?insert（long?keyobject?pointer）
??{
????//找到應(yīng)該插入的節(jié)點(diǎn)，即找到葉子節(jié)點(diǎn)
????Node?theNode?=?search（keyroot）;

????//在葉節(jié)點(diǎn)中找到空閑空間，有的話就把鍵放在那里
????if（?!isFull（theNode）?）
????{
??????putKeyToNode（keypointertheNode）;
????}else{
??????//如果在適當(dāng)?shù)娜~節(jié)點(diǎn)沒有空間，就把該葉節(jié)點(diǎn)分裂成兩個(gè)，并正確分配鍵值
??????Node?newNode?=?separateLeaf（keypointertheNode）;
??????//如果分裂的是根節(jié)點(diǎn)，就新建一個(gè)新的根節(jié)點(diǎn)將新建的節(jié)點(diǎn)作為他的根節(jié)點(diǎn)
	??//原來的根節(jié)點(diǎn)，和分裂的節(jié)點(diǎn)分別作為新根節(jié)點(diǎn)的左右孩子，此時(shí)新根只有一個(gè)元素
??????if（?isRoot（theNode）?）
??????{
????????DisposeRoot（theNodenewNodenewNode.keys[0]）;
??????}else{
????????//將新建立的節(jié)點(diǎn)的指針插入到上層節(jié)點(diǎn)
????????insertToInnerNode（theNode.parentnewNodenewNode.keys[0]）;
??????}
????}
??}




??//用于尋找鍵值key所在的或key應(yīng)該插入的節(jié)點(diǎn)
??//key為鍵值curNode為當(dāng)前節(jié)點(diǎn)--一般從root節(jié)點(diǎn)開始
??public?Node?search（long?keyNode?curNode）
??{
????if?（isLeaf（curNode））
??????return?curNode;

????for?（int?i?=?0;?i?????{
????????if?（key???????????return?search（key?（Node）?curNode.pointer[i]）;
????????else?if?（key?>=?curNode.keys[i]）?{
??????????if?（i?==?curNode.keyAmount?-?1）?//如果后面沒有值
??????????{
????????????//如果key比最后一個(gè)鍵值大則給出最后一個(gè)指針進(jìn)行遞歸查詢
????????????return?search（key（Node）?curNode.pointer[curNode.keyAmount]）;
??????????}
??????????else?{
????????????if?（key???????????????return?search（key?（Node）?curNode.pointer[i?+?1]）;
??????????}
????????}
????}
????//永遠(yuǎn)也不會到達(dá)這里
????return?null;
??}




	//把鍵值放到葉節(jié)點(diǎn)中--這個(gè)函數(shù)不進(jìn)行越界檢查////////////////////////////////////////
??private?void?putKeyToNode（long?keyobject?pointerNode?theNode）
??{
????int?position?=?getInsertPosition（keytheNode）;
????//進(jìn)行搬遷動(dòng)作--------葉節(jié)點(diǎn)的搬遷
????if（?isLeaf（theNode）?）
????{
????????if（theNode.keyAmount?<=?position）
????????{
???????????theNode.add（keypointer）;
???????????return;
????????}
????????else{
????????????for?（int?j?=?theNode.keyAmount?-?1;?j?>=?position;?j--）?{
??????????????theNode.keys[j?+?1]?=?theNode.keys[j];
??????????????theNode.pointer[j?+?1]?=?theNode.pointer[j];
????????????}
????????????theNode.keys[position]?=?key;
????????????theNode.pointer[position]?=?pointer;
????????}
?????}else{
??????????//內(nèi)部節(jié)點(diǎn)的搬遷----有一定的插入策略：
??????????//指針的插入比數(shù)據(jù)的插入多出一位
??????????for?（int?j?=?theNode.keyAmount?-?1;?j?>=?position;?j--）?{
????????????theNode.keys[j?+?1]?=?theNode.keys[j];
????????????theNode.pointer[j?+?2]?=?theNode.pointer[j+1];
??????????}
??????????theNode.keys[position]?=?key;
??????????theNode.pointer[position+1]?=?pointer;
????????}
????//鍵值數(shù)量加1
????theNode.keyAmount++;
??}



?//將對應(yīng)的葉節(jié)點(diǎn)進(jìn)行分裂并正確分配鍵值，返回新建的節(jié)點(diǎn)///////////////////////////////
??private?Node?separateLeaf

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----

?????文件???????9016??2011-11-07?20:53??BTree.java

?????文件????????972??2011-11-07?20:41??Node.java

?????文件???????1424??2011-11-07?20:21??Test.java

?????文件???????1623??2011-11-07?11:07??TreePrinter.java

-----------?---------??----------?-----??----

????????????????13035????????????????????4