이진 검색 트리 (Binary Search Trees)

이진 검색 트리의 정의

이진 검색 트리에서 검색

이진 검색 트리에서 삽입

이진 검색 트리에서 삭제

이진 검색 트리의 높이

이진 검색 트리에서 중순위 운행

이진 검색 트리의 정의

이진 검색 트리는 검색(Search), 삽입(Insert), 삭제(Delete) 연산을 효율적으로 지원하는 자료 구조이다. 이러한 연산을 지원하는 자료 구조를 사전 구조(dictionary)라고 한다.

이진 검색 트리는 이진 트리이며 다음을 만족한다.

(a) 왼쪽 부트리에 있는 모든 노드 값은 루트의 값보다 작다.

(b) 오른쪽 부트리에 있는 노드 값은 루트의 값보다 크다.

(c) 왼쪽 부트리와 오른쪽 부트리는 역시 이진 검색 트리이다.

아래에 이진 검색 트리의 예가 주어져 있다.

이진 검색 트리에서 검색(Search)

이진 검색 트리 자체가 재귀적으로 정의되어 있으므로 검색 알고리즘도 순환(recursion)을 이용하여 설계할 수 있다. 주어진 키 값을 루트의 값과 비교하여 같으면 검색이 끝난 것이고, 작으면 왼쪽 부트리에서 검색하며, 루트의 값보다 크면 오른쪽 부트리에서 검색하면 된다.

순환을 이용한 알고리즘을 반복을 이용한 알고리즘으로 쉽게 변환할 수 있다.

이진 검색 트리의 높이를 [eqn: h]라고 했을 때, 검색은 [eqn: O(h)] 시간에 수행할 수 있다. 그리고 순환을 이용한 알고리즘에서는 시스템 스택을 위한 [eqn: O(h)] 공간을 필요로 한다.

이진 검색 트리에서 삽입(Insert)

이진 검색 트리에서 노드의 삽입은 간단히 해결할 수 있다. 삽입을 위하여 우선 이진 검색 트리를 검색한다. 검색이 실패로 끝난다면 바로 그 위치에 노드를 삽입하면 된다.

새로운 노드의 삽입은 항상 리프에서 일어나며, 이 삽입 연산에 대한 시간 복잡도는 [eqn: O(h)]이다.

이진 검색 트리에서 삭제(Delete)

이진 검색 트리에서 노드의 삭제는 삽입 연산보다는 복잡하다. 삽입은 항상 리프에서 일어나지만 삭제는 리프가 아닌 노드에서 발생할 수도 있기 때문이다.

삭제될 노드가 리프인 경우는 간단히 그 노드만 삭제하면 된다. 만약 하나의 자식 노드를 가지는 경우에는 자식 노드를 부모 노드의 자식 노드로 만들어 주면 된다.

삭제될 노드가 두 자식 노드를 가지고 있는 경우는 약간 복잡하다. 현재 노드를 삭제하고 난 후 왼쪽 부트리에서 가장 큰 노드나 오른쪽 부트리에서 가장 작은 노드를 삭제하여 현재 위치에 대치시키면 된다. 이 때 왼쪽 부트리에서 가장 큰 노드나 오른쪽 부트리에서 가장 작은 노드는 리프이거나 자식 노드가 하나밖에 없으므로 삭제하기가 수월하다.

삭제 연산의 시간 복잡도가 [eqn: O(h)]임을 설명하여 보시오.

이진 검색 트리의 높이

이진 검색 트리의 높이는 노드의 수를 [eqn: n]이라고 할 때 최대 [eqn: n-1]일 수 있다. 정렬된 순서로 혹은 그 역순으로 삽입이 일어나는 경우에 높이가 최대가 된다. 따라서 앞에서 제시한 연산을 [eqn: n]에 대한 함수로 표현하면 모두 [eqn: O(n)]이 된다.

이진 검색 트리의 높이가 [eqn: O(log n)]으로 제한되면, 앞에서 제시한 연산 모두 [eqn: O(log n)]이 될 것이다. 다음에 다루게 될 AVL 트리 등은 높이가 [eqn: O(log n)]이다. 일반적으로 삽입과 삭제가 임의로 발생하는 경우 평균적인 높이는 [eqn: O(log n)]임이 알려져 있다.

이진 검색 트리에서 중순위 운행

이진 검색 트리에서 중순위 운행을 하여 각 노드를 방문할 때 노드 값을 출력하면 어떤 결과를 얻을 수 있을까? 아래에 있는 이진 검색 트리에서 중순위 운행을 수행하여 보기로 한다.

이진 검색 트리를 중순위 운행하면 노드 값을 정렬하게 된다. 이 사실을 노드 개수에 대한 수학적 귀납법으로 어렵지 않게 증명할 수 있다. 증명을 완성하여 보시오.

참고. 앞에서 보았듯이 [eqn: n]개의 데이터로 힙을 [eqn: O(n)] 시간에 만들 수 있다. 그러면 이진 검색 트리도 [eqn: O(n)] 시간에 만들 수 있을까? 일반적으로 [eqn: n]개의 데이터를 정렬하기 위해서 [eqn: Omega(n log n)] 시간이 필요하다고 알려져 있다. 만약 이진 검색 트리를 [eqn: O(n)] 시간에 만들 수 있다면, 이진 검색 트리를 [eqn: O(n)] 시간에 중순위 운행하여 결국 [eqn: O(n)] 시간에 정렬할 수 있게 된다. 따라서 이진 검색 트리는 [eqn: O(n)] 시간에 만들 수 없다.