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

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

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

 

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함수라고 합니다.