?? bptree.java
字號:
}
else
{
currec = removeHelp((BpNode)node.recArray[currec].pointer, k, currec);
if(currec == -1)
return -1;
else if(((BpNode)node.recArray[currec].pointer).count >1)
{
/*
node.recArray[currec].key =
((BpNode)node.recArray[currec].pointer).recArray[1].key;
*/
BpNode current = (BpNode)node.recArray[currec].pointer;
while(!current.isLeaf())
{
current = (BpNode)current.recArray[0].pointer;
}
node.recArray[currec].key =
current.recArray[1].key;
return -1;
}
}
// 從當(dāng)前節(jié)點刪除
Comparable key = node.recArray[1].key;
node.deleteAt(currec);
if(node.isBigEnough())
return -1;
else
{
if(isFirstChild(node,key))
{
if(node.canMerge(node.rightSibling))
{
node.merge(node.rightSibling);
return thispos +1;
}
else
{
node.shuffle(node.rightSibling);
return thispos+1;
}
}
else if(node.canMerge(node.leftSibling))
{
node.leftSibling.merge(node);
return thispos;
}
else
{
node.leftSibling.shuffle(node);
return thispos;
}
}
}
private Pair insertHelp(BpNode node, Elem rec)
{
Pair tmp; // 存放一個 key/pointer 對
int currec = node.maxLE(rec.key);
if(node.isLeaf())
{
tmp = new Pair(rec.key, rec);
}
else
{
tmp = insertHelp((BpNode)node.recArray[currec].pointer, rec);
if(tmp == null)
return null;
}
if(!node.isFull())
{
node.addAfter(currec, tmp);
}
else
{
BpNode tp = node.split(currec, tmp);
if(tp.isLeaf())
{
return new Pair(tp.recArray[1].key, tp);
}
else
{
Pair maxP = node.recArray[--node.count]; // 刪除了此Pair
node.recArray[node.count] = null;
tp.recArray[0].pointer = maxP.pointer;
return new Pair(maxP.key, tp);
}
}
return null;
}
public Elem find(Comparable k)
{
int currec = root.maxLE(k);
BpNode current = root;
while(!current.isLeaf())
{
current = (BpNode)current.recArray[currec].pointer;
currec = current.maxLE(k);
}
if(!current.recArray[currec].key.equals(k))
return null;
return (Elem)current.recArray[currec].pointer;
}
BpNode firstLeaf()
{
BpNode curr = root;
while(!curr.isLeaf())
curr = (BpNode)curr.recArray[0].pointer;
return curr;
}
public boolean isFirstChild(BpNode node,Comparable k)
{
BpNode curr = root;
int currec = curr.maxLE(k);
while(curr.recArray[currec].pointer != node)
{
curr = (BpNode)curr.recArray[currec].pointer;
currec = curr.maxLE(k);
}
return (currec == 0);
}
void print()
{
if(root == null)
{
System.out.println("Empty tree");
return;
}
BpNode curr = firstLeaf();
while(curr != null)
{
System.out.println(curr);
curr = curr.rightSibling;
}
System.out.println("========================");
}
void printRev()
{
BpNode curr = firstLeaf();
while(curr.rightSibling != null)
curr = curr.rightSibling;
while(curr != null)
{
System.out.println(curr);
curr = curr.leftSibling;
}
System.out.println("===========");
}
public String toString()
{
if(root==null)
return "Empty Tree!";
String res ="";
BpNode first = root;
Object tmp = first;
while(tmp instanceof BpNode)
{
first = (BpNode)tmp;
res += first +"\t";
BpNode curr = first.rightSibling;
while(curr!= null)
{
res += curr +"\t";
curr = curr.rightSibling;
}
res += "\n";
tmp = first.recArray[0].pointer;
}
return res;
}
static void f1()
{
int[] arr = {
1,2,15,7,6,3,8,10,9,11,14,16,17,
};
BpTree tree = new BpTree();
for(int i=0; i<arr.length; i++)
tree.insert(arr[i]);
System.out.println(tree);
for(int i=0; i<20; i++)
System.out.println(tree.find(i));
}
static void f2()
{
BpTree tree = new BpTree();
int[] arr = RandomArray.randomArr(20);
for(int i=0; i<arr.length; i++)
{
tree.insert(arr[i]);
// tree.print();
}
tree.print();
System.out.println("================");
tree.printRev();
}
static void f3()
{
BpTree tree = new BpTree(7);
int test = 1000;
int[] arr1 = RandomArray.randomArr(test);
int[] arr2 = RandomArray.randomArr(test);
for(int i=0; i<arr1.length; i++)
System.out.print(arr1[i]+",");
System.out.println();
for(int i=0; i<arr2.length; i++)
System.out.print(arr2[i]+",");
System.out.println();
for(int i=0; i<arr1.length; i++)
tree.insert(arr1[i]);
System.out.println(tree);
for(int i=0; i<arr2.length; i++)
{
tree.remove(arr2[i]);
}
System.out.println(tree);
}
static void f4()
{
BpTree tree = new BpTree();
int[] arr1 = {34,9,43,26,12,14,31,27,37,35,23,47,19,39,22,44,16,7,18,24,40,6,11,41,21,49,32,5,28,1,17,3,45,10,42,33,25,30,15,50,36,8,38,13,4,29,46,20,48,2};
int[] arr2 = {31,17,35,42,7,16,33,13,19,12,4,41,50,2,21,24,23,47,14,28,25,49,38,9,18,27,22,48,8,36,44,37,30,40,39,32,46,10,45,6,11,20,15,43,1,34,3,29,26,5};
for(int i=0; i<arr1.length; i++)
System.out.print(arr1[i]+",");
System.out.println();
for(int i=0; i<arr2.length; i++)
System.out.print(arr2[i]+",");
System.out.println();
for(int i=0; i<arr1.length; i++)
{
tree.insert(arr1[i]);
// tree.print();
}
System.out.println(tree);
for(int i=0; i<arr2.length; i++)
{
tree.remove(arr2[i]);
// if(i%10 == 0)
System.out.println(tree);
}
System.out.println(tree);
}
static void f5()
{
BpTree tree = new BpTree();
int[] arr = RandomArray.randomArr(100);
for(int i=0; i<arr.length; i++)
{
tree.insert(arr[i]);
// tree.print();
}
tree.print();
System.out.println(tree);
}
static void f6()
{
BpTree tree = new BpTree(8);
String[] arr1 = RandomArray.randomStrArr();
String[] arr2 = RandomArray.randomStrArr();
for(int i=0; i<arr1.length; i++)
System.out.print(arr1[i] + "\t");
for(int i=0; i<arr1.length; i++)
{
tree.insert(arr1[i]);
System.out.println(tree);
}
for(int i=0; i<arr2.length; i++)
{
Elem tmp =tree.find(arr2[i]);
System.out.println("" + i +": "+tmp);
}
}
public static void main(String[] args)
{
f6();
}
}
class RandomArray
{
static String[] initArr1 =
{
"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t",
"u","v","w","x","y","z"
};
static String[] initArr2 =
{
"0","1","2","3","4","5","6","7","8","9"
};
static String[] initArr;
static
{
initArr = new String[initArr1.length * initArr2.length];
int k=0;
for(int i=0; i<initArr1.length; i++)
{
for(int j=0; j<initArr2.length; j++)
initArr[k++] = initArr1[i]+ initArr2[j];
}
}
static int[] randomArr(int size)
{
int[] arr = new int[size];
for(int i=0;i<arr.length; i++)
{
arr[i] = i+1;
}
for(int i=0; i< size*10; i++)
{
int r1 = (int)(Math.random()*size);
int r2 = (int)(Math.random()*size);
int tmp = arr[r1];
arr[r1] = arr[r2];
arr[r2] = tmp;
}
return arr;
}
static String[] randomStrArr()
{
String[] arr = initArr;
for(int i=0; i< arr.length*10; i++)
{
int r1 = (int)(Math.random()*arr.length);
int r2 = (int)(Math.random()*arr.length);
String tmp = arr[r1];
arr[r1] = arr[r2];
arr[r2] = tmp;
}
return arr;
}
/*
public static void main(String[] args)
{
String[] arr = randomStrArr();
for(int i=0; i<arr.length; i++)
System.out.println(arr[i]);
}*/
}
?? 快捷鍵說明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -