[EKOO의 JAVA를 이용한 자료구조:7회] Tree (4)

 [EKOO의 JAVA를 이용한 자료구조:7회] Tree (4)

저자:EKOO| 날짜: 2005년 05월 24일

 

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 함수를 각각 만들어서 호출을 하였습니다. 이 함수들은 강좌에는 따로 적지 않겠습니다. 필요하시면 이 강좌의 끝에 링크로 전체 코드를 받으실수 있도록 해드릴게요. 독자분들께서 직접 한번 짜보세요 ^^