09 이진 탐색 트리

9.1 이진 탐색 트리

자료구조의 관점에서 탐색search은 자료구조의 중요한 응용 분야 중 하나로 탐색을 위해 특화된 이진트리인 이진 탐색 트리에 대해 알아보자.

탐색

탐색은 레코드record의 집합에서 특정 레코드를 찾아내는 것으로, 레코드들의 집합을 테이블table이라고 한다. 즉 테이블에서 특정한 레코드를 찾는 것이 탐색이다. 레코드는 1개 이상의 필드field로 구성된다. 예를 들어, '학생'에 관한 레코드는 이름, 학번, 학과 등의 필드로 구성된다. 레코드들은 보통 키key라고 불리는 하나의 필드에 의해 구별된다. 키는 서로 중복되지 않는 고유한 값을 가지며 이 키를 사용해 레코드들을 구별할 수 있다. 이 키를 주요키primary key라고 부르며 탐색은 입력된 어떤 키를 사용해 레코드를 찾는다.

 

이진 탐색 트리BST

이진 탐색 트리Binary Search Tree는 이진트리 기반의 탐색을 위한 자료구조이다. 효율적인 탐색 작업을 위한 자료구조로 다음과 같은 성질을 가지며, 순환적으로 정의된다.

 

모든 노드는 유일한 키를 갖는다.

왼쪽 서브트리의 키들은 루트의 키보다 작다.

오른쪽 서브트리의 키들은 루트의 키보다 크다.

왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

 

따라서 어떤 탐색키가 주어지면, 이 값을 루트 노드의 키와 먼저 비교해서, 작으면 원하는 노드는 왼쪽 서브트리에, 크면 오른쪽 서브트리에 있다는 뜻이다. 

 

그림 9.1

그림 9.1을 보자. 왼쪽 서브트리에 있는 노드의 값들은 루트 노드인 50보다 작고, 오른쪽 서브트리의 값들은 크다. 따라서 이는 이진 탐색 트리이다. 이 트리를 중위 순회 방법으로 순회해보자.

 

9 - 12 - 14 - 17 - 19 - 23 - 50 - 54 - 67 - 72 - 76

 

오름차순으로 노드를 방문하는 것을 볼 수 있다. 즉 이진 탐색트리는 어느 정도 정렬된 상태를 유지한다.

 

이진 탐색 트리의 추상 자료형

이진 탐색 트리도 이진트리의 일종이므로 "상속"의 개념을 사용하자. 또한 이진트리의 공백 검사나 순회 등의 연산도 모두 포함될 것이다. 추가적으로는 삽입, 삭제, 검색의 함수가 필요할 것이다. 이진트리에서는 삽입, 삭제의 연산이 복잡하였지만 BST에서는 데이터들이 어느 정도 정렬되어 있으므로 이들을 구체화 하자.

 

객체: BST의 특성을 만족하는 이진트리: 어떤 노드x의 왼쪽 서브트리의 키들은 x의 키보다 작고, 오른쪽 서브트리 키들은 x의 키보다 크다. 이때 왼쪽, 오른쪽 서브트리 모두 BST이다.

 

연산:

insert(n): BST의 특성을 유지하며 새로운 노드 n을 BST에 삽입한다.

remove(n): BST의 특성을 유지하며 노드 n을 트리에서 삭제한다.

search(key): 키 값이 key인 노드를 찾고 반환한다.

 

 

9.2 이진 탐색 트리의 연산

탐색 연산

BST에서 어떤 탐색키를 가진 노드를 찾기 위해서는, 주어진 탐색키와 현재 루트 노드의 키 값의 비교가 선행되어야 한다.

비교한 결과가 같다면, 탐색이 성공적으로 끝난 것이다. 비교한 결과, 탐색키가 루트 노드의 키 값보다 작으면 탐색은 루트 노드의 왼쪽 자식 노드를 기준으로 다시 진행된다. 반대로 탐색키가 루트 노드의 키 값보다 크면 루트 노드의 오른쪽 자식 노드를 기준으로 탐색을 다시 진행한다. 물론 이와 같은 탐색이 가능하기 위해선, 이 트리가 주어진 키 값에 대해 BST의 조건에 맞게 구성되어 있어야 한다.

 

탐색 연산을 구현하는 방법을 생각해보면, 루트 노드부터 시작하여 그 자식 노드로 탐색을 순환하여 진행하므로, 리커젼 방법을 쓸 수도 있고, 같은 연산을 크기만 다르게 진행하므로 반복을 이용해 구현할 수도 있을 것이다.