[디딤돌 자료구조와 알고리즘 with C] 3.4 이진 탐색 트리

3. 4 이진 탐색 트리

 이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 트리입니다. 이진 탐색 트리는 노드와 서브 트리의 집합으로 서브 트리도 이진 탐색 트리입니다. 그리고 부모 노드는 두 개의 자식 노드를 가질 수 있고 왼쪽 서브 트리에는 부모보다 작은 값들이 오른쪽 서브 트리에는 부모보다 큰 값들이 있습니다.

 

[그림 3.7] 이진 탐색 트리

 

 

 이진 탐색 트리에서 데이터를 추가하거나 검색할 때 재귀적인 방법으로 찾을 수 있습니다.

 

검색 (key:키, sroot: 서브 트리의 루트노드)

    rkey:= sroot.key

    gap: = rkey - key

    조건(gap IsEqual 0)

        sroot 반환

    조건(gap < 0)

        조건(sroot의 오른쪽 노드가 있다면)

            검색(key, sroot의 오른쪽 노드)

        sroot 반환

    조건(gap>0)

        조건(sroot의 왼쪽 노드가 있다면)

            검색(key, sroot의 왼쪽 노드)

        sroot 반환

 

 이처럼 검색하면 높이가 h인 트리에서 각 계층마다 하나의 노드와 비교를 수행합니다. 따라서 이진 탐색 트리에서 검색 비용은 높이와 비례합니다.

 

 만약 이진 탐색 트리의 각 계층의 노드가 꽉 차면 노드의 개수의 합은 2의 h승 -1개 입니다.

S(h) = 2^0 + 2^1 + 2^2 + ... + 2^(h-1) =2^h - 1

 

 따라서 검색 비용은 노드의 개수가 n일 때 h 번이므로 h = logn이며 O(logn)이라 말할 수 있습니다.

 

 그리고 이진 탐색 트리의 모든 노드를 방문할 때도 재귀적인 방법으로 문제를 해결할 수 있습니다. 만약 루트를 먼저 방문한 후에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 방문하면 전위 운행이라고 말합니다.

 

전위 운행(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

    조건(sr IsEqual null)

        종료

    doit(sr)

    전위 운행(sr의 왼쪽 자식 노드, doit)

    전위 운행(sr의 오른쪽 자식 노드, doit)

 

 

 

 

  그리고 왼쪽 서브 트리를 방문한 후에 오른쪽 서브 트리를 방문한 후에 마지막으로 루트를 방문하는 것을 후위 운행이라고 말합니다.

 

후위 운행(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

    조건(sr IsEqual null)

        종료

    후위 운행(sr의 왼쪽 자식 노드, doit)

    후위 운행(sr의 오른쪽 자식 노드, doit)

    doit(sr)

 

 마지막으로 왼쪽 서브 트리를 방문한 후에 루트를 방문하고 오른쪽 서브 트리를 방문하는 것을 중위 운행이라고 말합니다.

 

중위 운행(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

    조건(sr IsEqual null)

        종료

    중위 운행(sr의 왼쪽 자식 노드, doit)

    doit(sr)

    중위 운행(sr의 오른쪽 자식 노드, doit)

 

[그림 3.8] 운행 방법에 따라 방문 순서