Java 로 구현한 BSTree

이원 탐색트리 : 

: 모든 원소는 상이한 키를 갖는다.

: 왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다

: 오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다

: 왼쪽 서브트리와 오른쪽 서브트리도 모두 이원 탐색 트리이다.

노드의 구조 : | left | key | right| 

탐색 : 찾으려는 키값을 x 라고 하자 

키값보다 작으면 왼쪽을 탐색, 키값보다 크면 오른쪽을 탐색 

삽입 : x 키값으로 가진 원소가 이미 있는 지 확인 , 키값이 있어야 하는 위치에 없으면 탐색을 종료하고 원소  

    삽입.

package com.java.algo.woriworld;

class TreeNode{

String key;

TreeNode left;

TreeNode right;

}

class BinarySearchTree{

private TreeNode rootNode;

private TreeNode InsertKey(TreeNode T, String x){

// insert() 메소드에 의해 사용되는 보조 순환 메소드

if(T == null){

TreeNode newNode = new TreeNode();

newNode.key = x;

return newNode;

}else if(x.compareTo(T.key)<0){// x < T.key이면 x 를 T의 왼쪽

T.left = InsertKey(T.left, x);//서브트리에 삽

return T;

}else if(x.compareTo(T.key)>0){//x>T.key이면 x를 T의 오른쪽 

T.right = InsertKey(T.right, x);//서브트리에 삽입 

return T;

}else{

return T;// key값 x 가 이미 T에 있는 경우 

}

} // end insertkey()

void Insert(String x){

rootNode = InsertKey(rootNode, x);

}//end insert()

TreeNode find(String x){

// 키값 x 를 가지고 있는 TreeNode의 포인터를 반환

TreeNode T = rootNode;

int result;

while (T!=null) {

if((result = x.compareTo(T.key))<0){

T = T.left;

}else if(result == 0){

return T;

}else {

T = T.right;

}// end if

}

return T;

}//end find()

private void printNode(TreeNode N){

// printBST() 메소드에 의해 사용되는 순환 메소드 

if(N !=null){

printNode(N.left);

System.out.println(N.key);

printNode(N.right);

}

}//end printNode

void printBST(){

// 서브트리 구조를 표현하는 괄호 형태로 트리를 프린트 

printNode(rootNode);

System.out.println();

}//end printBST

}// end BinarySearchTree class

public class TreeEx {

public static void main(String[] args) {

BinarySearchTree T = new BinarySearchTree();

T.Insert("S");

T.Insert("J");

T.Insert("B");

T.Insert("D");

T.Insert("U");

T.Insert("M");

T.Insert("R");

T.Insert("Q");

T.Insert("A");

T.Insert("G");

T.Insert("E");

//구축된 bst 를 프린트 

System.out.println("The Tree is :");

T.printBST();

System.out.println();

// 스트링 "R"을 탐색하고 프린트 

System.out.println("Search For \'R\'");

TreeNode N = T.find("R");

System.out.println("Key of node found ="+N.key);

System.out.println();

// 스트링 "C"를 탐색하고 프린

System.out.println("Search For \'C\'");

TreeNode P = T.find("C");

if(P !=null){

System.out.println("Key of node found ="+P.key);

}else {

System.out.println("Node that was found =null");

}

System.out.println();

}//end main

}//end binarysearch tree test class 

삭제: 

이원 탐색 트리에서 키 값을 가진 원소를 찾은후 그 원소가 가진 자식의 수 (0,1,2)에 따라 다르다

1. 자식이 없는 리프노드의 삭제

삭제해야 될 노드가 자식이 없는 리프 노드의 경우 부모노드의 해당 링크 필드를 null로 만들고 삭제한 노드를 반환함

2. 자식이 하나인 노드의 삭제

삭제될 노드가 하나의 자식만을 가진 노드인 경우 삭제되는 노드의 자리에 하나밖에 없는 그 자식 노드를 위치시키면 된다.

3. 자식이 둘인 노드의 삭제

삭제해야 될 노드가 두 자식을 가진 경우에는 먼저 삭제되는 그 노드 자리에 그의 왼쪽 서브 트리에서 제일 큰 원소로 대체 할 것인지 또는 그의 오른쪽 서브트리에서 제일 작은 원소로 대체할 것인지 선택하여야 한다. 

그후 해당 서브트리에서 이 대체 원소를 삭제하면 된다.

대체하게 되는 노드의 차수는 항상 1 이하가 된다.

이원 탐색 트리의 결합과 분할

1. 이원 탐색 트리의 3원 결합

ThreeJoin(aBST, x , bBST,cBST) 

이원 탐색 트리 aBST와 bBST에 있는 모든 원소들과 키 값 x 를 가진 노드를 루트 노드로 하는 이원 탐색트리 cBST를 생성한다. 여기서 aBST 에 있는 모든 원소는 x 보다 작고 bBST 에 있는 모든 원소는 x보다 크다고 가정.

이 결합 연산 이후에 aBST 와  bBST는 더 이상 사용하지 않는다고 가정 

새로운 트리 노드 cBST를 생성하여 key 값으로 x 를 지정하고 left 링크 필드에는 aBST,right 링크 필드에는 bBST를 설정하면 원하는 이원 탐색 트리가 된다. 

새로운 이원 탐색 트리의 높이는 max{height(aBST),height(bBST)}+1 이 된다.

2. 이원 탐색 트리의 2원 결합

TwoJoin(aBST,bBST,cBST)

두 이원 탐색 트리 aBST,bBST 를 결합하여 aBST,bBST에 있는 모든 원소들을 포함하는 하나의 이원 탐색 트리 cBST 를 생성

aBST의 모든 키 값들은 bBST의 어떤 키 값보다 작고 이 결합 연산이후 aBST,bBST는 더 이상 사용하지않는다고 가정 

만일 aBST,bBST 트리가 공백이면 원하는 이원 탐색 트리 cBST 는 곧바로 공백이 아닌 aBST,bBST가 된다.

aBST,bBST가 공백이 아닌 경우, 이 두 이원 탐색 트리를 결합하는 방법: 

1. 먼저 aBST에서 키 값이 가장 큰 원소를 삭제,

이 원소가 삭제된 이원 탐색트리를 aBST 이라고 하고, 삭제된 가장 큰 키 값을 max 라고 하자 , 

그런 다음 3원 결합 연산을 실행 시키면 된다. 

2원 결합 연산결과 : cBST 의 높이는 max{height(aBST),height(bBST)}+1

2. bBST 에서 가장 작은 키 값을 가진 원소를 삭제 

     이 원소가 삭제된 이원 탐색 트리를 bBST 라 하고 삭제된 가장 작은 키 값을 min 이라 하자 .

그다음 3원 결합 연산을 실행.

이원 탐색 트리의 분할

Split(aBST , x, bBST,cBST) 

이원 탐색 트리 aBST 를 주어진 키 값 x 를 기준으로 2개의 이원 탐색 트리 bBST,cBST로 분할.

bBST 는 x 보다 작은 키 값을 가진  aBST 의 모든 원소를 포함하고  cBST 는 x 보다 큰 키 값을 가진 aBST의 모든 원소를 포함한다. 

분할로 생성된 bBST,cBST 는 모두 이원 탐색 트리의 성질을 만족 시켜야 한다.

주어진 키 값 x 가 aBST에 있으면 true, 없으면 false 를 반환.

aBST 의 루트 노드가 키 값 x 를 가질 때는 곧바로 연산을 마친다.

이 경우  aBST 의 루트 노드를 중심으로 왼쪽 서브트리는  bBST 로 만들고 aBST 의 오른쪽 서브트리는 cBST 로 만들고 true 반환.

만일 x 가 루트 노드의 키 값보다 작으면 루트와 그 오른쪽 서브트리는 cBST에 속하게 된다. 

만일 x 가 루트 노드의 키 값보다 크면 루트와 그 왼쪽 서브트리는  bBST에 속하게 된다.

키 값 x 를 가진 원소를 탐색하면서 이원 탐색 트리 aBST를 아래로 이동한다. 

aBST 를 아래로 이동해 나갈때 2개의 이원 탐색트리 bBST,cBST가 구성되면서 분할 작업이 진행된다.