bptree.java

详细介绍了Btree的特性以及如何实现 适合初学者参考

		}
		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;
			}
		}
		
		//	从当前节点删除
		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]);
	}*/
	
}