[펌_java를 이용한 자료구조] 트리(Tree)

LONG

Binary Search Tree 란?

Tree는 하나의 root와 여러개의 자식 Node들로 구성이 되어 있죠. 보통 알고리즘에서 쓰이는 Tree는 자식노드의 갯수에 제한을 두는 경우가 많습니다. 하지만, [그림2]에서 보셨듯이 탐색기를 만들때 쓰는 Tree나, 전화번호부 같은데서 쓰이는 Tree구조들은 자식노드의 갯수에 재한이 없죠. "전화번호부에는 한 성씨가 10명이상 저장이 되지 않습니다." 이런 메시지가 뜨면 이용하는데 상당히 짜증이 나겠죠. 성을 갈아야 하는 상황이 나올지도 모르겠습니다. 어쨌든 이렇게 자식노드의 수에는 제한이 없는 경우가 보통입니다.

이번에 구현할 Binary Search Tree는 일정한 규칙을 가지고 Tree를 구성하게 됩니다. Node를 추가할때 root의 데이터보다 작은 경우라면(숫자에 해당합니다.) root의 왼쪽 자식으로 달리게 되는 것이죠. 밑에서 그림으로 설명하겠습니다.


[그림5]Binary Search Tree
[그림5]를 보시면 그림으로 간단하게 Binary Search Tree의 규칙을 나타내어 보았습니다. 규칙은 두가지 입니다. 왼쪽 Node는 오른쪽에 있는 Node보다 작아야 합니다. 새로운 Node들을 추가할때 마다(root 제외) 그 규칙에 따라서 추가만 해주시면 됩니다. 이런식으로 어떤 숫자 자료들을 구성을 하면 자료를 찾는데 걸리는 시간이 매우 빨라지게 됩니다.

또 하나! Binary Search Tree는 한 노드의 자식이 아무리 많아도 두개 까지만 허용됩니다. 이걸로 두가지 규칙이 모두 나왔네요. ^^ 쉽지 않습니까?

만약 34를 찾으려고 한다면 50(root)의 오른쪽 SubTree는 검색할 필요도 없겠죠? 50보다 큰 숫자들로 이루어진 SubTree일테니 말이죠. 하지만 이렇게 일정한 규칙으로 이루어진 Tree구조가 아니라면 모든 Node들을 검색해야 찾을수 있으므로, 정말 운이 나쁘다면 모든 Node들을 검사해본 후에야 찾는 결과가 나올 수 있겠죠. 이런 규칙에 따라서 Binary Search Tree를 작성해 보겠습니다.

Binary Search Tree 작성하기

우선 필요한 클래스가 두개가 필요합니다. Tree객체 클래스, Node 객체 클래스 이 두가지 이죠. Tree클래스는 root와 Tree에 있는 Node들의 갯수만을 가지게 되구요. Node클래스는 숫자 값과 left, right 값 만을 가지고 있습니다. left, right는 이미 앞에서 배우신 Linked List에서의 next 변수와 같은 역할로써 다른 Node를 가리키는 역할을 하게 됩니다. 하나의 Tree를 관장하는 Binary_search_tree 클래스부터 살펴보도록 하겠습니다.

class Binary_search_tree {     // root노드를 가리키고 있습니다.     private Integer_node root;     // Tree의 전체 Node의 갯수를 가지고 있습니다.     private int tree_size;     // 생성자     Binary_search_tree()     {         root = null;         tree_size = 0;     } }

실제로 Tree 클래스는 매우 복잡하기 때문에 하나의 Node의 속성을 나타내는 클래스부터 살펴보도록 하겠습니다.

class Integer_node {     private int value;     private Integer_node left;     private Integer_node right;     Integer_node(int _value)     {         // node에 값 배정         value = _value;         left = null;         right = null;     } }

위 두개의 코드는 간단히 클래스의 멤버 변수와 생성자만을 보여드렸습니다.

Tree클래스에는 추가, 삭제, 출력, 초기화 기능을 하는 함수들이 존재합니다.

Node클래스에는 Access 함수 말고는 없습니다. 멤버 변수의 값을 바꾸고,

얻어오고 하는 그런 함수들을 Access함수라고 합니다.

=============================================================================================

 

Tree클래스의 추가 함수부터 살펴보도록 하겠습니다. 추가하는데는 일정한 규칙이 있습니다. 추가할 Node와 현재 가리키고 있는 Node와 비교하여 그것보다 작으면 왼쪽 자식으로 달리게 되고, 아니면 오른쪽으로 달리게 됩니다. [그림5]를 통해서 설명해 드리겠습니다.

[그림6]Binary Search Tree의 추가과정

Add 함수의 Code 입니다.

public void Add(int value) {     Integer_node temp = new Integer_node(value);     if( tree_size == 0 )     {         root = temp;         tree_size += 1;     }     else     {         // temp node 가 적당한 위치를 찾으면 true로 값 변경         boolean search = false;         Integer_node point = root;         while( search == false )         {             // value가 현재 point가 가리키고 있는 node의 값보다 작거나 같다면             if( value <= point.get_value() )             {                 if( point.get_left() == null )                 {                     point.set_left(temp);                     search = true;                     tree_size += 1;                 }                 else                     point = point.get_left();             }             // 위의 반대 경우라면?             else if( value > point.get_value() )             {                 if( point.get_right() == null )                 {                     point.set_right(temp);                     search = true;                     tree_size += 1;                 }                 else                     point = point.get_right();             }         }     }     return; }

적당한 위치를 찾을때까지 반복문이 돌고, 적당한 위치를 찾아서 search 함수가 true로 세팅이 되면 Add 함수를 빠져나오는 구조입니다. while문 안의 if문의 조건을 보시면 Binary Search Tree의 조건에 따라서 Node를 추가한다는 것을 보실 수 있습니다.

이번에는 Remove 함수를 작성을 하도록 하겠습니다. 삭제함수는 추가과정보다는 복잡합니다. 5가지 상황에 따라서 삭제작업에 따르는 행동이 매우 다르게 됩니다.

CASE:
1. 삭제할 Node가 없을때[그림7]
2. 삭제할 Node가 왼쪽, 오른쪽 자식이 없을때[그림8]
3. 삭제할 Node가 Tree의 root이고, 왼쪽 자식이 없을때[그림9]
4. 삭제할 Node가 왼쪽 자식이 없고, 오른쪽 자식이 있을때[그림10]
5. 삭제할 Node가 왼쪽 자식이 있을때[그림11]

[그림8]2. 삭제할 Node가 왼쪽, 오른쪽 자식이 없을때

위의 Tree에서 17을 지우라고 하면 그냥 지워주면 됩니다. 하지만 JAVA에서는 C언어에서처럼 자체적으로 메모리를 해제할수는 없죠. 17의 부모 Node인 9 의 right 를 null로 바꿔줌으로써 17을 Tree에서 삭제할 수 있습니다.

[그림9]3. 삭제할 Node가 Tree의 root이고, 왼쪽 자식이 없을때

45를 삭제해야 합니다. 45는 현재 Tree의 root이죠. 그렇다면 지울 Node의 오른쪽 자식을 새로운 root로 지정해주면 45를 가리키는 방법이 없어지게 되므로 Tree에서 삭제가 되게 되는 것입니다.

[그림10]4. 삭제할 Node가 왼쪽 자식이 없고, 오른쪽 자식이 있을때

30을 삭제해야 합니다. 그렇다면 30의 부모노드인 45를 가리키는 Parent of target Node의 Left child 를 target의 right child로 세팅해주면 됩니다.

[그림11]5. 삭제할 Node가 왼쪽 자식이 있을때

public int Remove(int value) {     boolean search = false;     Integer_node parent_of_point = null;     Integer_node point = null;     // 지워야할 node를 찾는다     point = Search_node(root, value);     // 값을 찾지 못했는데 부모노드를 찾을 필요가 없지     if( point != null )         parent_of_point = Search_parent_of_node(root, point);     else if( point == root ) // 찾은 node가 루트라면 부모는 null 로 세팅         parent_of_point = null;     // 이제 이미 찾아놓은 노드와 그 노드의 부모를 이용하여 경우에 따른 삭제작업.     // 1. 찾는 값이 없는 경우     if( point == null )     {         Remove_case_one(value);         return -1;     }     // 2. 찾는 값이 트리의 루트이고 왼쪽 자식트리가 없을때     if( point == root && point.get_left() == null )         Remove_case_two(point, parent_of_point, value);     // 3. 찾는 값이 왼쪽 자식트리는 없고 오른쪽에만 자식이 있을 경우     else if( point.get_left() == null && point.get_right() != null )         Remove_case_three(point, parent_of_point, value);     // 4. 찾는 값이 왼쪽 자식트리가 있을때     else if( point.get_left() != null )         Remove_case_four(point, parent_of_point, value);     // 5. 찾는 값이 자식트리가 하나도 없을때     else if( point.get_left() == null && point.get_right() == null )         Remove_case_five(point, parent_of_point, value);     else         return -1;     return 1; }

위에서 말씀드린 1, 2, 3, 4, 5 번 경우에 따라서 Remove_case_NUMBER 함수를 각각 만들어서 호출을 하였습니다. 이 함수들은 강좌에는 따로 적지 않겠습니다. 필요하시면 이 강좌의 끝에 링크로 전체 코드를 받으실수 있도록 해드릴게요. 독자분들께서 직접 한번 짜보세요 ^^

=============================================================================================

 

이제 출력하는 함수와 초기화 함수가 남았죠? 초기화 해주는 함수는 root를 null로 세팅하고, tree_size 변수를 0으로 세팅해주는 작업으로 끝나게 됩니다.

// 트리 초기화. public void Init_all_tree() {     root = null;     tree_size = 0;     return; }

그리고 이제 출력함수만이 남았습니다. 보통 Binary Tree를 출력하는 방법에는 세가지 방법이 있습니다. Preorder, Inorder, Postorder 가 그 세가지 방법인데요. 어떻게 Tree를 돌아다니면서 Node의 값을 찍어주는지에 따라서 나뉘게 됩니다.

[그림12]Full Binary Search Tree

 

Preorder	1. root의 값을 찍는다 2. Left SubTree에서 Recursive하게 같은 과정을 거친다. 3. Right SubTree에서 Recursive하게 같은 과정을 거친다.
Inorder	1. Left SubTree에서 Recursive하게 같은 과정을 거친다. 2. root의 값을 찍는다. 3. Right SubTree에서 Recursive하게 같은 과정을 거친다.
Postorder	1. Left SubTree에서 Recursive하게 같은 과정을 거친다. 2. Right SubTree에서 Recursive하게 같은 과정을 거친다. 3. root의 값을 찍는다.

Preorder Print : 45, 30, 21, 35, 53, 53, 54
Inorder Print : 21, 30, 35, 45, 53, 53, 54
Postorder Print : 21, 35, 30, 53, 54, 53, 45

위의 Print 함수 역시 독자 여러분들이 직접 해보시구요. 정 안되시는 경우에만 코드를 직접 참고해 주세요.

강좌를 끝마치며...

8회 Tree 강좌가 드디어 끝이 났습니다. 지난회 강좌까지는 제가 모든 코드를 전부 다 강좌에 집어넣었습니다. 하지만 이번 Tree부터는 코드보다는 개념이 잡혀있어야만 코딩에 무리가 없겠다고 판단해서, 코드보다는 많은 그림으로 쉬운 이해에 도움이 되도록 강좌를 작성하였습니다. 문제는 재귀의 개념이 들어갔다는 것이네요. Tree에서는 while이나 for를 이용한 반복문보다는 재귀를 이용하여 여러 함수를 구현하는 경우가 많습니다. 이해가 잘 안되시는 독자분들께서는 일단 그림을 통해서 개념만 쌓아 두시구요, 다음 강좌에서 다룰 재귀에 대한 강좌를 하고 나서 보시는 것도 좋은 방법이 되실거라 생각합니다.

아! 전체 코드를 받고 싶으신 분은 ptyjj@naver.com 으로 메일을 보내시면 답장에 첨부하여

보내드리겠습니다. 왠만하면 직접 해보세요~ :)

날씨가 매우 쌀쌀합니다. 감기안걸리게 독자분들도 조심하시구요~. 다음강좌때 뵙겠습니다 _ _)

ARTICLE 참고서적 : Data Structures & Other Objects Using JAVA

강좌를 시작하며...

안녕하세요. 이번 강좌에서는 Tree를 배워보게 됩니다. 윈도우 탐색기를 한번 실행시켜 보시겠어요? 왼쪽에 보시면 바탕화면, 내문서, 내 컴퓨터 등의 아이콘이 보이실겁니다. 그 옆에는 +, - 기호들도 보이시죠? 그 기호 옆에는 폴더가 보이게 되죠. 이것이 바로 Tree입니다. 이 이름은 실제로 Tree구조의 형태가 나무를 뒤집어 놓은듯한 모양이라고 해서 그렇게 지었다고 합니다.

실제로 자료구조에서도 많이 개념을 사용하구 있구요, Algorithm 에서도 많이 Tree의 개념을 사용하고 있습니다. 유명한 0-1 Knapsack알고리즘이나, n-queens 알고리즘에서도 트리구조를 이용하여 Solution 을 구해내는 것을 경험해 보신 독자분들도 있으리라 생각됩니다. 그럼 이제부터 Tree의 세계로 여행을 떠나볼까요?

Tree란?

Tree란 말 그대로 나무입니다. 이 나무를 거꾸로 매달아놓은 형태가 바로 Tree 구조의 기본이죠.


[그림1] Tree구조

위에 보시는 형태가 바로 트리입니다. [그림1]의 오른쪽 그림은 나무 그림을 뒤집어 넣은 그림입니다. 나무에는 가지가 있죠? 이 가지를 Tree구조에서는 Node라고 하며, [그림1]의 왼쪽 그림에서의 네모를 Node라고 부릅니다. 나무는 가지가 하늘을 향해서 뻗치죠? Tree는 나무를 뒤집어 놓은 형태기 때문에 Node들이 아래를 향해서 뻗쳐지게 됩니다.

독자여러분. 나무에서 가장 중요한게 뭘까요? 잎? 꽃? 열매? 물론 생각하신것들도 다 중요하지만, 나무는 뿌리가 없으면 안되죠? 뿌리가 있어야 어린나무가 자라서 큰 나무가 되죠. Tree구조에서도 역시 뿌리가 가장 중요합니다. 이를 Root 라고 부릅니다. [그림1]에서 맨 위에 있는 Node가 Root Node가 됩니다. 앞서의 Linked list 에서는 Head Node로 어떤 Node라도 찾아갈 수 있었듯이, Tree에서도 Root만 잃지 않고 있다면 어느 Node라도 방문하여, 삽입, 삭제, 수정등의 작업을 하실 수 있습니다.

이정도라면 Tree에 대한 간단한 소개가 되었겠죠? 이제 이런 Tree를 이용하여, 구체적으로 어떻게 Tree의 개념을 사용하는지에 대하여 알아보도록 하겠습니다.

Tree의 중요 용어


[그림2]Tree에 쓰이는 용어

독자분들께서 이해하시 쉬우시도록 번호가 붙은 Node들을 가지고 있는 Tree그림을 예로 용어를 설명하겠습니다.

Level	Node 2,3의 Level은 2입니다. root에서부터 자신까지 오는데 거치는 Node의 갯수라고 할 수 있습니다.
Parent	Node 2는 Node 4,5의 Parent 입니다. 자신과 위로 연결되어 있는 Node를 Parent라고 합니다.
Children	Node 4,5는 Node 2의 Children 입니다. 자신과 아래로 연결되어 있는 Node를 Children이라고 합니다.
Leaf	자식이 없는 Node들을 가리킵니다.
Sibling	같은 부모를 가진 Node들을 Sibling이라고 합니다.
SubTree	Node 2를 root로 하는 Tree는 Node 1을 root로 하는 Tree의 SubTree라고 합니다. Node 3을 root로 하는 Tree도 SubTree라고 할 수 있겠죠.

=============================================================================================

 

Tree개념의 사용 용도

앞에서 Tree가 뭔지 그 개념에 대해서 살펴 보았습니다. 그렇다면 이 Tree라는 구조를 이용하여 실제로는 어떤곳에 어떻게 사용이 될까요?

[그림3] 윈도우 탐색기에서 사용된 Tree

독자분들도 위와 같은 그림을 자주 보셨으리라 생각됩니다.

[그림3]을 보시면 내 컴퓨터 밑에 '3.5 플로피 (A:)', '로컬 디스크 (C:)' 등이 보이구요, '로컬 디스크 (C:)' 밑에는 실제로 C: 밑에 있는 하위 디렉토리 들이 표시가 됩니다. 여기서 내 컴퓨터가 root라 할수 있구요, A:, C: 등이 내컴퓨터의 자식 Node가 됩니다. C:는 또 하나의 자식트리가 되어서 여러 자식디렉토리 Node들을 가지고 있는 셈이 됩니다. 앞서 설명드린 Tree의 구조를 그대로 따르고 있죠.

[그림4] 0-1 Knapsack Problem 알고리즘에 사용된 Tree

[그림4]는 0-1 Knapsack Problem 을 푸는데 사용되는 State Space Tree의 그림을 보여줍니다. 복잡한 알고리즘의 해답을 구하는데도 Tree구조가 이용되고 있습니다.

물론 위의 알고리즘 문제를 해결하는데 State Space Tree를 이용하는 방법만이 있는것은 아닙니다. 여러가지 다른 방법도 얼마든지 있죠.

[그림4]를 보시면 자식 노드가 2개씩만 뻗쳐 나가는걸 보실수 있습니다. Tree의 기초에 속하는 Binary Tree인데요, 이번에는 이렇게 생긴 Tree를 Java 언어로 직접 구현을 해보도록 하겠습니다.