File Structure assignment, it works perfectly well
BTree.java
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--; // 전체 요소의 개수를 줄이고
}
}
}
BTreeData.java
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;
}
}
BTreeNode.java
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;
}
}
mainFunction.java
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();
*/
