freesora's computing Story

import java.io.*;
import java.util.*;

// 실제로 BTree를 구현할 class

public class BTree {
	
	
	public BTreeNode rootNode;
	
	public BTree()
	{
		rootNode = new BTreeNode();
	}
	
	public boolean insert(BTreeData data) throws Exception			// 생성부분 완료
	{
		Stack stack = new Stack();		// 삽입시 참조되는 순서를 저장하게 될 stack

		BTreeNode parentNode = null; 		
		BTreeNode currentNode = rootNode;
		BTreeNode newNode = null;
		
		currentNode = rootNode;
		int i=0;
		
		//int totalCount = 
		while(currentNode != null)
		{
			parentNode = currentNode;
			stack.push(parentNode);		// Stack에 부모노드들이 차근 차근 쌓아둔다.(나중에 split or merge시 사용)
			
			for(i=0;i data.key)	// 만약 bucket의 키 값이, data key보다 클 경우
				{											// 그 의미는 곧 삽입해야할 곳을 찾았다는 의미
					break;
					
				}
			}
			currentNode = currentNode.childNode[i];		// 실제 insert 될 곳의 node는 여기 들어간다.
		}
		if(parentNode == null)	// root에 아무것도 없는 경우
		{
			rootNode.data[0] = data;
			rootNode.elementCount = 1;
		}
		else		// root노드가 비어있지 않은 경우(일반정인 경우라면)(그리고 여기선 순서대로 저장되야 한다. sort함수를 사용하자)
		{
			insertDataBTree(parentNode,data, null);
			splitNode(stack);
		}
		return true;
	}
	
	
	//실제 Data를 입력하는 함수이다.
	public void insertDataBTree(BTreeNode currentNode, BTreeData data, BTreeNode RChildNode) throws Exception
	{
		@SuppressWarnings("null")
		int elementIndex = currentNode.elementCount;
		int i=0;			// 실제로 삽입될 index
		
		for( i = elementIndex-1 ; i>=0;i--)		// 자료를  이동하는 함수
		{
			int tempKey = currentNode.data[i].key;
			
			if(tempKey> data.key)			// 한칸씩 땡기게 된다.
			{
				currentNode.data[i+1] = currentNode.data[i];
				currentNode.childNode[i+2] = currentNode.childNode[i+1];
			}
			else
				break;
		}
		
		currentNode.data[i+1] = data;					// 실제 데이터 삽입부분, i--이므로
		currentNode.childNode[i+2] = RChildNode;		// 우 노드를 삽입한다(이는 merge와 split시 필요하다)
		currentNode.elementCount++;					// 
	}
	
	public void showBTree()					// 출력 함수
	{
		if(rootNode == null)
		{
			System.out.println("There is no data!!! BTree is empty!");
		}
		else
		{
			showBTreeByRecur(rootNode);
		}
	}
	
	public void showBTreeByRecur(BTreeNode Node)			// 출력 부분
	{
		// post-order traversals.
		if(Node != null)
		{
			for(int i=0;i stack) 		// 분할 함수 부분
	{
		BTreeNode parentTreeNode = null;
		BTreeNode currentTreeNode = null;
		BTreeNode newNode = null;
		BTreeData middleElement = null;
		BTreeNode tempNode;
		int middleIndex = 5/2;
		currentTreeNode = stack.pop();		// 가장 최상위 stack의 값을 가져온다.
		while(currentTreeNode != null)
		{
			//currentTreeNode = tempNode; 
			if(currentTreeNode.elementCount >= 5)	// 만약 5보다 element가 크다면(실제로 데이터는 M-1개 즉 4개밖에 저장하지 못한다)
			{
				newNode = new BTreeNode();		
				middleElement = new BTreeData();
				middleElement = currentTreeNode.data[middleIndex];		// 중간요소를 저장한다.
				currentTreeNode.data[middleIndex] = null;			// 이 부분을 없애준다.
				
				int j =0;
				int i;
				for(i= middleIndex + 1 ; i<5; i++)		// 중간 이후의 노드들은 분할되기 위해서 다 복사된다.
				{
					newNode.data[j] = currentTreeNode.data[i];
					newNode.childNode[j] = currentTreeNode.childNode[i];
					currentTreeNode.data[i] = null;
					currentTreeNode.childNode[i] = null;
					j++;
				}
				newNode.childNode[j] = currentTreeNode.childNode[i];		// m원 트리에서 node개수는 m-1개 subTree는 m개이기 떄문에
				currentTreeNode.childNode[i] = null;						// 이 작업을 반드시 해줘야한다.
				
				newNode.elementCount = 5/2;			// 분할되면 2개만 저장하게 된다.(5개 이므로)
				currentTreeNode.elementCount = 5/2;		// 현재 노드의 element 개수도 반이 된다고 명시해준다.
				
				// 여기서부터는 상위 부모 노드를 가져온다.
				try
				{
					parentTreeNode = stack.pop();		// 부모노드 가져오기
					insertDataBTree(parentTreeNode, middleElement, newNode);
				}
				catch(Exception e)			// 더 이상 pop하지 못하면 이 예외가 발생하게 된다.
				{
					rootNode = new BTreeNode();		// root노드를 하나 새로이 다시 만들고
					rootNode.data[0] = middleElement;		// 중간값을 새로 집어 넣고
					rootNode.elementCount++;		// 전체 개수를 증가 시킨 후
					rootNode.childNode[0] = currentTreeNode;		// 왼쪽 subtree는 현재껄로
					rootNode.childNode[1] = newNode;		// 다른쪽은 새로운 걸로 삽입한다.
				}
			}
			currentTreeNode = parentTreeNode;			// 계속해서 올라가야 한다.
			parentTreeNode = null;
		}
		
	}
	
	
	public boolean removeNode(int key) throws Exception
	{	
		int i = 0; 	// counter 변수
		//int index = 0;
		boolean isFind = false;		// 만약 검색해서 해당 노드를 찾지 못할경우 이 flag가 쓰인다.
		BTreeNode parentNode = null;
		BTreeNode currentNode = null;
		Stack stack = new Stack();		// stack을 하나 생성한다(노드 분할 및 balance를 위해서 쓰인다)
		
		currentNode = rootNode;
		
		while(currentNode != null && isFind == false)			// 이부분은 insert함수와 똑같지만, 찾을 때까지 수행하는 것만 다르다.
		{
			parentNode = currentNode;
			stack.push(parentNode);		// Stack에 부모노드들이 차근 차근 쌓아둔다.(나중에 split or merge시 사용)
			
			for(i=0;i key)	// 만약 bucket의 키 값이, data key보다 클 경우
				{											// 그 의미는 곧 삽입해야할 곳을 찾았다는 의미
					break;
				}
			}
			currentNode = currentNode.childNode[i];		// 실제 insert 될 곳의 node는 여기 들어간다.
		}
		
		if(isFind == true)		// 만약 원하는 키를 찾았다면
		{
								// 먼저 leaf node가 잇는지 검사한다.
			if(parentNode.childNode[0] == null)		// 현재노드가 아무것도 가리키지 않을 경우
			{
				deleteKeyBTree(parentNode, i);
				// deleteKeyBt 를 수행하는 부분
			}
			else			// leaf 노드가 잇다면
			{
				parentNode = replaceLeafNodeBTree(parentNode, i, stack);		// leaf 노드의 맨 끝 부분을 끌어 당기는 함수
				// replaceLeafNodebt를 수행한다.
			}			
			if(parentNode.elementCount < 5/2)		// 만약 최소 개수보다 작다면
			{
				balanceBTree(stack);
				//
			}
			return true;
			
		}
		else
		{
			System.out.println("The Key cannot be found! Try this again");
			return false;
		}
	}
	
	public void balanceBTree(Stack stack) throws Exception
	{
		BTreeNode parentNode = null;
		BTreeNode currentNode = null;
		BTreeNode newNode = null;
		BTreeNode leftNode = null;
		BTreeNode rightNode = null;
		
		BTreeData pivotData = new BTreeData();		// stack 가장 윗부분에 있는 node
		int index = 0;			// parentNode로부터 currentNode의 위치를 받을 변수
		int i= 0;
		
		currentNode = stack.pop();
		
		if(currentNode.elementCount >= 5/2)			// 만약 balance 유지할 필요가 없다면(1/2보다 크다)
			return;
		
		try
		{
			parentNode = stack.pop();					// 2번째 stack을 받는다(부모 노드)
		}
		catch(Exception e)			// 만약 부모노드에 아무것도 없다면 return한다.
		{
			return;
		}
		
		for(int j=0;i= ((5/2) + 1)))
		{
			borrowRightNodeBTree(parentNode,currentNode,index,parentNode.childNode[index+1]);
		}
		else if(index > 0 && (parentNode.childNode[index-1].elementCount >= ((5/2) + 1)))		// 왼쪼깅 다 많다면
		{
			// 여기는 왼쪽에서 빌린다.
			borrowLeftNodeBTree(parentNode,currentNode,index,parentNode.childNode[index+1]);
		}
		else		// 그렇지 않으면 merge한다.
		{
			mergeNodeBTree(stack,parentNode,currentNode,index);
		}
		
	}
	
	public void mergeNodeBTree(Stack stack, BTreeNode parentNode, BTreeNode currentNode, int index) throws Exception
	{
		BTreeNode leftNode = null;
		BTreeNode rightNode = null;
		BTreeData parentData = new BTreeData();
		BTreeNode parentParentNode = null;		//조상 노드.
		
		int i=0;
		int pivotIndex = 0;
		// 예외 처리 생략
		
		// 오른쪽으로 병합하는 경우
		if(index< parentNode.elementCount)
		{
			leftNode = currentNode;			// 현재노드가 left node가 되고
			rightNode = parentNode.childNode[index+1];	// 오른쪽 node는 parent의 오른쪽이 되고
			pivotIndex = index;				// pivot은 현재 index가 되고
			parentData = parentNode.data[pivotIndex];	// 그 데이터는 원래 index가 되고
		}
		else		// 왼쪽으로 합병하는 경우
		{
			leftNode = parentNode.childNode[index-1];
			rightNode  = currentNode;
			pivotIndex = index - 1;
			parentData = parentNode.data[pivotIndex];
		}
		insertDataBTree(leftNode, parentData, rightNode.childNode[0]);	// 0번째 요소에 왼쪽 data를 넣는다. 왼쪽에 parent 자료 추가
		
		for(i=0;i stack)
	{
		BTreeNode returnNode = null;
		BTreeData leafNodeData = new BTreeData();
		BTreeNode childNode = null;
		BTreeNode parentNode = deleteNode;
		int elementCount = index;
		do		// stack에 하나하나 다 쌓아둔다(나중에 balance를 유지할 때 필요하다)
		{
			childNode = parentNode.childNode[elementCount];		// parentNode의 삭제될 부분 뒤부터
			stack.push(childNode);		// 하나하나 씩 stack에 쌓아 논다.
			
			elementCount = childNode.elementCount;		// elementCount는 새로운 childNode의 elementCount가 되고 
			parentNode = childNode;		// 반복하여 수행한다.
			
		}while(childNode.childNode[elementCount] != null);
		
		leafNodeData = childNode.data[childNode.elementCount-1];		// 가장 오른쪽 끝에 있는걸 가져오고
		deleteNode.data[index] = leafNodeData;				// 삭제할 노드의 끝부분에다가 왼쪽끝의 요소를 대체한다.
		deleteKeyBTree(deleteNode, elementCount-1);			// 그리고 그 삭제될 바로 앞에 있는 요소를 삭제한다(원래 우리가 삭제하길 원했던 부분이다)
		returnNode = childNode;
		
		return returnNode;
	}
	
	
	public void deleteKeyBTree(BTreeNode parentNode, int index)		// 삭제 후 요소들을 한칸 씩 당기는 함수
	{
		int i=0;
		if(parentNode != null)
		{
			for(i = index + 1; i < parentNode.elementCount; i++)		// 앞으로 한칸 씩 떙긴다
			{
				parentNode.data[i-1] = parentNode.data[i];
				parentNode.childNode[i] = parentNode.childNode[i+1];
			}
			parentNode.data[parentNode.elementCount - 1] = null;		// 요소를 하나 삭제하고
			parentNode.childNode[parentNode.elementCount] = null;		// 역시 끝에 포인터도 null로 만든다.
			parentNode.elementCount--;									// 전체 요소의 개수를 줄이고
			
		}
		
	}
}

import java.io.*;

public class BTreeData 		// 데이터 부분
{
	public int key;
	public Object value; 
	BTreeData(int _key, Object _value)		// 2개의 부분으로 overloading 되어 있다.
	{
		key = _key;
		value = _value;
	}
	BTreeData()
	{
		key=0;
		value = null;
	}
}

import java.io.*;



public class BTreeNode
{
	public BTreeNode childNode[];
	public BTreeData data[];
	public int elementCount;				// 총 Element Count가 있다.
	
	BTreeNode()
	{
		childNode = new BTreeNode[6];		// M-5 트리, 추가로 하나의 여유분을 둔다.. 우선 insert한후에 split하기 위해서
		data = new BTreeData[5];			
	}
	public void setData(int index, BTreeData TreeData)
	{
		data[index] = TreeData;
		
	}
}

import java.io.Console;
import java.util.Scanner;


public class mainFunction {

	public static void main(String args[]) throws Exception
	{
		BTree bt = new BTree();					// B-Tree 생성
		Scanner scan = new Scanner(System.in);	// Scanner 생성
		System.out.println("Welcome to B-Tree's world!!!!!");		
		int input=0;
		do
		{
			System.out.println("\n1. Input Data");				// Menu 출력
			System.out.println("2. Remove Data with Key value");
			System.out.println("3. Show B-Tree by post-order traversal method");
			System.out.println("Please Enter the menu number(Exit is 0)\n");	
			
			String temp = scan.nextLine();				// 입력받기
			try
			{
				input = Integer.valueOf((temp));		// switch 문을 위해서 변환을 해준다.
			}
			catch(Exception e)							// 예외 처리
			{
				System.out.println("Please enter the correct number please");
				continue;
			}
			
			switch(input)								
			{
			case 1:										// 1번은 insert function
				String temp1 = new String();
				String temp2 = new String();
				System.out.println("Please Enter the Key number");
				temp1 = scan.nextLine();
				System.out.println("Please Enter the Any String Data you want");
				temp2 = scan.nextLine();
				BTreeData tmpData = new BTreeData(Integer.valueOf(temp1),temp2);		// 입력받은 값을 가지고 data를 생성한다.
				if(bt.insert(tmpData))
					System.out.println("Successful!");
				else
					System.out.println("Failed");
				break;
			case 2:										// 2번은 remove function
				String tempRemoveKey = new String();
				System.out.println("Please Enter the key you want to remove from B-Tree");
				tempRemoveKey = scan.nextLine();
				if(bt.removeNode(Integer.valueOf(tempRemoveKey)))			// 삭제한다.
					System.out.println("Successful!");
				else
					System.out.println("Failed");
				break;
			case 3:						// 3번은 출력 
				System.out.println("\nThe B-Tree will be shown soon\n");
				bt.showBTree();				// 출력한다.
				break;
			case 0:						// 0은 프로그램 종료
				System.out.println("The program will be terminated");
				break;
			default:
				System.out.println("Please Enter correct number");
				break;
			}
		}while(input!=0);
		

	}
}


/*
BTreeData b1 = new BTreeData(69, "b1");			BTreeData b2 = new BTreeData(7, "b2");
BTreeData b3 = new BTreeData(150, "b3");		BTreeData b4 = new BTreeData(19, "b4");
BTreeData b5 = new BTreeData(70, "b5");		BTreeData b6 = new BTreeData(20, "b6");
BTreeData b7 = new BTreeData(128, "b7");		BTreeData b8 = new BTreeData(18, "b8");
BTreeData b9 = new BTreeData(42, "b9");		BTreeData b10 = new BTreeData(120, "b10");
BTreeData b11 = new BTreeData(140, "b11");		BTreeData b12 = new BTreeData(16, "b12");
BTreeData b13 = new BTreeData(100, "b13");		BTreeData b14 = new BTreeData(26, "b14");
BTreeData b15 = new BTreeData(145, "b15");		BTreeData b16 = new BTreeData(15, "b16");
BTreeData b17 = new BTreeData(110, "b17");		BTreeData b18 = new BTreeData(30, "b18");
BTreeData b19 = new BTreeData(40, "b19");		BTreeData b20 = new BTreeData(132, "b20");
BTreeData b21 = new BTreeData(138, "b21");		BTreeData b22 = new BTreeData(50, "b22");
BTreeData b23 = new BTreeData(43, "b23");		BTreeData b24 = new BTreeData(130, "b24");
BTreeData b25 = new BTreeData(136, "b25");		BTreeData b26 = new BTreeData(41, "b26");
BTreeData b27 = new BTreeData(59, "b27");		BTreeData b28 = new BTreeData(54, "b28");
BTreeData b29 = new BTreeData(122, "b29");		BTreeData b30 = new BTreeData(124, "b3o");


bt.insert(b1);		bt.insert(b2);		bt.insert(b3);		bt.insert(b4);	
bt.insert(b5);		bt.insert(b6);		bt.insert(b7);		bt.insert(b8);		
bt.insert(b9);		bt.insert(b10);		bt.insert(b11);		bt.insert(b12);		
bt.insert(b13);		bt.insert(b14);		bt.insert(b15);		bt.insert(b16);		
bt.insert(b17);		bt.insert(b18);		bt.insert(b19);		bt.insert(b20);
bt.insert(b21);		bt.insert(b22);		bt.insert(b23);		bt.insert(b24);	
bt.insert(b25);		bt.insert(b26);		bt.insert(b27);		bt.insert(b28);		
bt.insert(b29);		bt.insert(b30);

System.out.println("All datas have been inserted, it will be shown by post-order traversal");

bt.showBTree();		

System.out.println("Removing data........");


bt.removeNode(138);		bt.removeNode(50);		bt.removeNode(43);
bt.removeNode(130);		bt.removeNode(136);		bt.removeNode(41);
bt.removeNode(59);		bt.removeNode(54);		bt.removeNode(122);
bt.removeNode(124);

System.out.println("Removing task has been completed, now printing B-Tree");

bt.showBTree();		
*/