[C언어 알고리즘] 3.4.2 이진 탐색 트리(Binary Search Tree)

[C언어 알고리즘] 3.4.2 이진 탐색 트리(Binary Search Tree)

---

이번에는 재귀 알고리즘으로 구현하는 이진 탐색 트리(Binary Search Tree)를 알아봅시다. 이진 탐색 트리는 검색 효율을 높이기 위해 만들어진 이진 트리입니다.

 

이진 탐색 트리에서는 자료를 보관할 때 부모보다 작은 값을 갖는 자료는 부모의 왼쪽 서브 트리에 매달고 큰 값을 갖는 자료는 부모의 오른쪽 서브 트리에 매다는 이진 트리입니다. 그리고 이진 탐색 트리에서는 같은 값을 갖는 자료는 보관하지 않습니다. 이처럼 매달면 서브 트리도 이진 탐색 트리인 특징을 갖습니다.

 

binary search tree = { root, sub trees}

sub tree is binary search tree, left son’ s data <parent’s data > right son’s data, MAX[N(sub tree)]=2

[그림 3.9] 이진 탐색 트리

이진 탐색 트리에서는 자료를 추가할 때 재귀적인 방법으로 부모 노드를 찾을 수 있습니다. 그리고 검색할 때나 삭제할 때도 원하는 자료를 보관한 노드를 재귀적인 방법으로 찾을 수 있습니다.

 

다음은 자료를 추가할 때 부모 노드를 찾거나 검색 및 삭제할 때 원하는 자료를 보관한 노드를 찾는 알고리즘입니다. 물론 검색과 삭제에서는 반환한 노드의 값이 원하는 자료인지 확인은 해야겠죠.

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

    조건(sroot가 존재하지 않으면)

        0 반환

    rkey:= sroot.key

    gap: = rkey - key

    조건(gap IsEqual 0)

        sroot 반환

    조건(gap < 0)

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

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

        sroot 반환

    조건(gap>0)

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

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

        sroot 반환

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

 

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

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

 

따라서 검색 비용은 노드의 개수가 n일 때 h 번이므로 h = logn이며 Θ(logn)이라 말할 수 있습니다. 하지만 편향 트리에서는 O(n)일 수 있습니다.

[그림 3.10] 이진 탐색 트리에서 탐색 과정

 

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

 

위의 이진 탐색 트리에서 전위 순회하면 방문 순서는 50, 25, 15, 12, 40, 30, 43, 75, 60, 80, 77와 같습니다. 언제나 부모는 자식들보다 먼저 방문하고 있음을 알 수 있습니다.

 

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

    조건(sr IsEqual null)

        종료

    doit(sr)

    PreOrderTravel (sr의 왼쪽 자식 노드, doit)

    PreOrderTravel (sr의 오른쪽 자식 노드, doit)

 

왼쪽 서브 트리를 방문한 후에 오른쪽 서브 트리를 방문한 후에 마지막으로 루트를 방문하는 것을 후위 순회(Post Order Travel)혹은 후위 운행이라고 말합니다.

 

위의 이진 탐색 트리에서 후위 순회하면 방문 순서는 12, 15, 30, 43, 40, 25, 60, 77, 80, 75, 50와 같습니다. 언제나 부모는 자식들보다 나중에 방문하고 있음을 알 수 있습니다.

 

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

    조건(sr IsEqual null)

        종료

    PostOrderTravel (sr의 왼쪽 자식 노드, doit)

    PostOrderTravel(sr의 오른쪽 자식 노드, doit)

    doit(sr)

 

왼쪽 서브 트리를 방문한 후에 루트를 방문하고 오른쪽 서브 트리를 방문하는 것을 중위 순회(In Order Travel) 혹은 중위 운행이라고 말합니다.

 

위의 이진 탐색 트리에서 중위 순회하면 방문 순서는 12, 15, 25, 30, 40, 43, 50, 60, 75, 77, 80와 같습니다. 언제나 부모는 왼쪽 자식들보다 나중에 방문하고 오른쪽 자식들보다 먼저 방문함을 알 수 있습니다.

 

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

    조건(sr IsEqual null)

        종료

     InOrderTravel (sr의 왼쪽 자식 노드, doit)

    doit(sr)

     InOrderTravel (sr의 오른쪽 자식 노드, doit)

[그림 3.11] 이진 탐색 트리의 운행