btree.java

数据结构中的B-TREE的实现

	// B树的结点
	class BTNode
	{
		static int nodes = 1; // 计输出的节点数
		int m; // B树的阶
		int keynum; // 结点中关键字个数
		BTNode parent; // 指向双亲结点的指针
	    int[] key; // 关键字，0号单元不用
		BTNode[] ptr; // 指向子树的指针
			
		public BTNode(int j)
		{
			m = j;
			keynum = 0;
			parent = null;
			key = new int[m+1];
			ptr = new BTNode[m+1];
		}

		public BTNode(int m, int keynum, BTNode parent, int[] key, BTNode[] ptr)
		{
			this.m = m;
			this.keynum = keynum;
			this.parent = parent;
			this.key = key;
			this.ptr = ptr;
		}

		// 将p分裂为两个节点，返回新节点和需提升的关键字
		public SplitResult split()
		{	
			int k = 0;
			//System.out.println("This is the split");
			BTNode child1 = new BTNode(this.m);
			BTNode child2 = new BTNode(this.m);
			BTNode parent1;

			if (this.parent == null)
			{
				parent1 = new BTNode(this.m);
			}
			else
			{
				parent1 = this.parent;	
			}

			child1.keynum = this.keynum/2;
			child2.keynum = this.keynum/2;
			
			if (this.parent == null)
			{//System.out.println("This.parent is null");
				parent1.keynum = 1;
			}
			else
				parent1.keynum = this.parent.keynum + 1;
			
				
			child1.parent = parent1;
			child2.parent = parent1;

			if ( this.parent == null || this.parent.parent == null)
			{
				parent1.parent = null;
			}
			else
				parent1.parent = this.parent.parent;
			
			for (int i=1; i <= this.keynum ;i++ )
			{
				System.out.println("This is the value3: "+this.key[i]+" :"+i);
			}
			System.out.println("This is the keynum: "+this.keynum);

			for (int i = 1; i <= this.keynum/2 ; i++ )
			{
				child1.key[i] = this.key[i];
				System.out.println("This is the child1 value: "+child1.key[i]);
			}

			for (int i = 1; i <= this.keynum/2 ; i++ )
			{
				child2.key[i] = this.key[i + (this.keynum+1)/2];
				System.out.println("This is the child2 value: "+child2.key[i]+": "+i+" "+(this.keynum+1)/2);
			}

			if (this.parent == null)
			{	
				System.out.println("This.keynum: "+this.keynum);
				parent1.key[1] = this.key[(this.keynum+1)/2];//this.key.length/2
			}

			else
			{
				for (int i = 1; i <= this.parent.keynum; i++ )
				{
					int b = this.key[this.key.length/2];
					int a = this.parent.key[i];
					int c = this.parent.key[i+1];
					if (a <= b && b < c)
					{
						k = i;
						parent1.key[i] = b;
					}
					else if (a <= b && c <= b)
					{
						parent1.key[i] = this.parent.key[i];
					}
					else if (a >= b && c > b)
					{
						parent1.key[i + 1] = this.parent.key[i];
					}
				}
			}
			
				
			if (this.parent == null)
			{
				parent1.ptr[0] = child1;
				parent1.ptr[1] = child2;
			}

			else
			{
				parent1.ptr[k] = child1;
				parent1.ptr[k + 1] = child2;
				for (int i = 0; i <= this.parent.ptr.length; i++ )
				{
					if (i < k)
					{
						parent1.ptr[i] = this.parent.ptr[i];
					}
					else if (i > k+1)
					{
						parent1.ptr[i] = this.parent.ptr[i - 1]; 
					}

				}
			}

			if (this.ptr != null)
			{
				//System.out.println("This is the ptr.length: " + this.ptr.length);
				for (int i = 0; i < this.ptr.length/2 ; i++ )
				{
					child1.ptr[i] = this.ptr[i];
				}
				for (int i = 0; i < this.ptr.length/2 ; i++ )
				{
					child2.ptr[i] = this.ptr[i + this.ptr.length/2];
				}
			}
			else
			{
				child1.ptr = null;
				child2.ptr = null;
			}


			//if (parent1.key.length > m)
			//{
				//return parent1.split();
			//}
			//else
			System.out.println("This is the parent1: "+parent1.key[1]+": "+parent1.keynum);
				return new SplitResult(parent1, this.key[this.key.length/2]);
		}

		// 遍历该节点及其子节点
		public void visit()
		{
			System.out.print("Node" + BTNode.nodes + ": ");
			BTNode.nodes++;
			for(int i = 1; i <= keynum; i++)
			{
				System.out.print(key[i] + " ");
			}
			System.out.println("");
			for(int i = 0; i <= keynum; i++)
			{
				if(ptr[i] != null)
					ptr[i].visit();
			}
		}
	}
	
	// 查找结果的包装类
	class SearchResult
	{
		BTNode pos; // 指向找到的结点
		int i; // 在结点中的关键字序号
		boolean status; // 查找成功与否

		public SearchResult(BTNode pos, int i, boolean status)
		{
			this.pos = pos;
			this.i = i;
			this.status= status;
		}
	}

	// 分裂结果的包装类
	class SplitResult
	{
		BTNode newNode; // 指向新节点
		int promote; // 需提升的关键字

		public SplitResult(BTNode newNode, int promote)
		{
			this.newNode = newNode;
			this.promote = promote;
			System.out.println("This is the SplitResult: "+newNode.key[1]);
		}
	}

	// B树的实现
	class BTree
	{
		BTNode root; // B树的根节点

		public BTree(BTNode t)
		{
			root = t;
		}

		// 在node.key[1...keynum]中查找val，
		// node.key[i] <= val < node.key[i+1]
		private int searchVal(BTNode node, int val)
		{
			boolean found = false;
			int k = 1;
			//System.out.println("This is the keynum: " + node.keynum);
			if (node != null && !found)
			{
				for (int i = 0; i <= node.keynum; i++)
				{
					if (node.key[i] == val)
					{
						k = i;
						found = true;
					}
					//System.out.println("this is the node length: " + node.key.length);
					if (found == false && node.key[i] <= val)
					{
						k = i;
					}
				}
			}
			//System.out.println("This is the position0: " + k);
			return k;// your implementation
		}

		// 从根节点开始查找关键字val，结果被包装成
		// 一个SearchResult对象
		public SearchResult search(int val)
		{	
			BTNode p = root;
			BTNode q = null;
			int k = 0;
			boolean found = false;
			
			while (p != null && !found)
			{	//System.out.println("Wang!");
				k = this.searchVal(p, val);
				q = p;
				if ( p.key[k] == val)
					found = true;
				else 
				   p = p.ptr[k]; 
			}
			//System.out.println("This is the position: " + k);
			return new SearchResult(q, k, found);
		}

		// 将val和child分别插入到node.key[pos+1]和node.ptr[pos+1]
		private void insertVal(BTNode node, int pos, int val, BTNode child)
		{
			int p;
			System.out.println("This is the keynum: "+node.keynum);
			System.out.println("This is the pos: "+pos);
			System.out.println("This is the value: "+val);
			for (int i = node.keynum; i > pos; i--)
			{
				node.key[i + 1] = node.key[i];
			}
			node.key[pos + 1] = val;

			for (int i = node.keynum; i > pos; i--)
			{
				node.ptr[i+1] = node.ptr[i];
			}
			node.ptr[pos + 1] = child;
			node.keynum = node.keynum + 1;
		}

		// 在B树的结点q的key[i]与key[i+1]之间插入
		// 关键字val。若引起结点过大，则沿双亲链进行
		// 必要的结点分裂调整，使原B树仍符合定义。
		public void insert(int val, BTNode q, int i) 
		{
			BTNode child = null;
			//System.out.println("This is the q: "+q.keynum);
			if ( (q.keynum + 1) < q.m)
			{   System.out.println("wang");
				this.insertVal(q, i, val, child);	
			}
			
			else if ((q.keynum + 1) == q.m)
			{
				this.insertVal(q, i, val, child);
				SplitResult f = q.split();
				q = f.newNode;
				System.out.println("This is the Jona: "+q.key[i]);
			}
		}

		// 在B树中插入关键字val
		public void insert(int val)
		{
			SearchResult sr = search(val);
			insert(val, sr.pos, sr.i);
		}

		// 深度遍历
		public void visit()
		{
			if(root != null)
				root.visit();
		}
		
		/** 深度遍历
		    本例中，你的程序应该输出
			=====B-Tree Implementation=====
			Step1:
			Node1: 18 33 

			Step2:
			Node1: 18 
			Node2: 12 
			Node3: 23 33 

			Step3:
			Node1: 18 30 
			Node2: 12 
			Node3: 23 
			Node4: 33 48 

			Step4:
			Node1: 18 
			Node2: 12 
			Node3: 10 
			Node4: 15 
			Node5: 30 
			Node6: 20 23 
			Node7: 33 48 

			Step5:
			Node1: 18 30 
			Node2: 12 
			Node3: 10 
			Node4: 15 
			Node5: 21 
			Node6: 20 
			Node7: 23 24 
			Node8: 33 
			Node9: 31 
			Node10: 48 

			Step6:
			Node1: 18 30 
			Node2: 12 
			Node3: 10 
			Node4: 15 
			Node5: 21 
			Node6: 20 
			Node7: 23 24 
			Node8: 33 47 
			Node9: 31 
			Node10: 45 
			Node11: 48 

			Step7:
			Node1: 30 
			Node2: 18 
			Node3: 12 
			Node4: 10 
			Node5: 15 
			Node6: 21 
			Node7: 20 
			Node8: 23 24 
			Node9: 47 
			Node10: 33 
			Node11: 31 
			Node12: 45 
			Node13: 50 
			Node14: 48 
			Node15: 52 
		*/
		public static void main(String[] args)
		{
			System.out.println("===B-Tree Implementation===");
			BTNode node = new BTNode(3);
			BTree tree = new BTree(node);
			
			tree.insert(18);
			tree.insert(33);
			System.out.println("step1: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;

			tree.insert(12);
			tree.insert(23);
			System.out.println("step2: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;

			tree.insert(30);
			tree.insert(48);
			System.out.println("step3: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;

			tree.insert(10);
			tree.insert(15);
			tree.insert(20);
			System.out.println("step4: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;

			tree.insert(21);
			tree.insert(24);
			tree.insert(31);
			System.out.println("step5: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;

			tree.insert(45);
			tree.insert(47);
			System.out.println("step6: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;

			tree.insert(50);
			tree.insert(52);
			System.out.println("step7: ");
			tree.visit();
			System.out.println("");
			BTNode.nodes = 1;
		}
	}