[자료구조] 이진 검색 트리의 이론과 구현 :: 늦깎이 IT

이번 포스팅에서는 이진 검색 트리에 대해서 알아봅니다.

[전체 구현 소스코드 확인하기]

[전체 구현 이클립스 프로젝트 확인하기]

우선, 데이터를 저장, 검색, 삭제 등을 할 때 사용되는 자료구조는 대부분 배열과 연결 리스트를 사용합니다.

저장, 검색, 삭제 등의 연산(?)을 할 때 배열과 연결 리스트에서 걸리는 시간 복잡도를 우선적으로 확인해봅시다.

1. 데이터가 정렬되지 않은 상태일 때,

[배열을 사용할 경우]

1) 검색

 - 원하는 데이터를 찾기 위해서는 배열의 처음부터 끝까지 모두 확인해야 하므로 O(N)만큼의 시간이 걸립니다.

2) 저장

 - 데이터들이 정렬되지 않은 상태이므로, 배열의 맨 마지막에 데이터를 저장하면 되기 떄문에 O(1)만큼의 시간이 걸립니다.

3) 삭제

 - 삭제할 데이터를 검색하기 위한 시간 복잡도는 O(N)입니다.

 - 삭제할 데이터를 찾았다면, 정렬을 할 필요가 없는 상태이므로 맨 뒤에 있는 데이터를 현재 삭제할 데이터의

위치에 저장하면 되므로 O(1)만큼의 시간이 걸립니다.

[연결 리스트를 사용할 경우]

1) 검색

- 원하는 데이터를 찾기 위해서는 리스트의 처음부터 끝까지 모두 확인해야 하므로 O(N)만큼의 시간이 걸립니다.

2) 저장

 -  데이터들이 정렬되지 않은 상태이므로, 리스트의 Head 혹은 Tail에 데이터를 저장하면 되기 떄문에 O(1)만큼의 시간이 걸립니다.

3) 삭제

 - 삭제할 데이터를 검색하기 위한 시간 복잡도는 O(N)입니다.

 - 삭제할 데이터를 찾았다면, 리스트에서 데이터를 삭제할 때에는 O(1)만큼의 시간이 걸립니다.

2. 데이터가 정렬된 상태일 때,

[배열을 사용할 경우]

1) 검색

 - 배열에 저장된 데이터가 정렬된 경우에는, 이진 검색을 사용할 수 있으므로 O(logN)만큼의 시간이 걸립니다.

2) 저장

 - 데이터를 저장할 위치가 배열의 맨 앞이라면, 모든 데이터들을 뒤로 한 칸씩 미뤄야 하므로 O(N)만큼의 시간이 걸립니다.

3) 삭제

 - 맨 앞의 데이터를 삭제해야 한다면, 모든 데이터들을 앞으로 한 칸씩 당겨야 하므로 O(N)만큼의 시간이 걸립니다.

[연결 리스트를 사용할 경우]

1) 검색

 - 리스트에 저장된 데이터가 정렬된 경우라고 할지라도, 리스트는 인덱스로 접근할 수 없기 때문에 O(N)만큼의

시간이 걸립니다.

2) 저장

 - 데이터를 저장하는 시간은 O(1)이지만, 데이터를 저장할 위치를 찾는 시간은 O(N)입니다.

3) 삭제

 - 데이터를 삭제하는 시간은 O(1)이지만, 삭제할 데이터를 찾는 시간은 O(N)입니다.

위, 내용을 표로 정리하면 다음과 같습니다.

표를 보면, 정렬 여부에 관계없이, 검색, 삭제, 저장의 연산 중에 최소 한가지는 O(N)만큼의 시간이 걸리게 됩니다.

어떻게하면 O(N)보다 더 효과적인 방법이 바로 이진 검색 트리입니다.

---

[이진 검색 트리]

이진검색 트리는 연산의 시간복잡도가 트리의 높이에 비례하여 증가하게 됩니다.

1. 이진 탐색 트리의 조건

1) 트리에 저장된 원소들은 서로 다른 유일한 키를 갖는다.

2) 루트 노드의 왼쪽 서브트리에 있는 원소들의 키는 루트노드의 키보다 작다.

3) 루트 노드의 오른쪽 서브트리에 있는 원소들의 키는 루트노드의 키보다 크다.

4) 왼쪽, 오른쪽 서브트리도 이진 탐색 트리이다.

[그림 출처]

[검색]

예를 들어, 7을 검색한다고 가정하면, 다음과 같은 경로를 따라 검색하게 된다.

8 → 3 → 6 → 7

1) 7은 8보다 작으므로 8의 왼쪽 서브트리를 검색한다.

2) 7은 3보다 크므로 3의 오른쪽 서브트리를 검색한다.

3) 7은 6보다 크므로 6의 오른쪽 서브트리를 검색한다.

4) 7을 찾았다.

[의사 코드]

TREE-SEARCH(x, k)  // x는 루트 노드, k는 찾는 값
    if x == NULL or key[x] == k
        return x
    if k < key[x]
        TREE-SEARCH(left[x], k)
    else
        TREE-SEARCH(right[x], k)

[최소 값]

이진트리에서 최소 값은 항상 가장 왼쪽 서브트리에 있습니다.

위의 그림에서 가장 최소 값은 1입니다. 그리고 그 위치는 가장 왼쪽 서브트리(노드)인 것을 확인할 수 있습니다.

즉, 왼쪽 자식노드가 NULL일 때 까지 반복적으로 왼쪽 노드를 찾아가면 됩니다.

[의사 코드] - 최소값

SEARCH-MINIMUM(x)
    while left[x] is not null
        x <- left[x]
    return x

[의사코드] - 최대값

TREE-MAXIMUM(x)
    while right[x] != NULL
        do x <- right[x]
    return x

[Successor]

Successor란 어느 노드 X의 key[x]보다 크면서 가장 작은 키를 가진 노드입니다.

아래 그림에서 8의 Successor는 10입니다. 8보다 큰 값들 중에서 가장 작은 값은 10이기 때문입니다.

3의 Successor는 4입니다. 3보다 큰 값들(4, 6, 7) 중에서 가장 큰 값은 4이기 때문입니다.

이처럼 Successor는 해당 노드의 오른쪽 서브트리중에서 최소 값을 의미합니다.

그럼, 7의 Successor는 누구일까요? 눈으로 확인하면 8이지만 어떻게 그 값을 찾아갈 수 있을까요?

[Successor를 구하는 경우]

1. 구하고자 하는 노드의 오른쪽 서브트리가 존재할 경우에는 오른쪽 서브트리의 최소값

2. 오른쪽 서브트리가 존재하지 않는 경우, 

 - 구하고자 하는 노드에서부터 부모 노드를 타고 올라가다가, 최초로 그 부모노드의 왼쪽 자식노드가 되는 경우에

그때의 부모노드가 Successor이다. 

 예를 들어, 7의 Successor를 찾기 위해 부모 노드를 타고 올라가보자.

 1) 7 → 6 으로 올라갈 때, 7은 6의 오른쪽 자식이다.

 2) 6 → 3 으로 올라갈 때, 6은 3의 오른쪽 자식이다.

 3) 3 → 8 으로 올라갈 때, 3은 8의 왼쪽 자식이다. 이때, 최초로 왼쪽자식이 된 경우이므로 3의 부모노드인 8이

    7의 Successor가 된다.

3. 구하고자 하는 노드가 최대값인 경우

 - 이때에는 루트노드까지 올라가더라도 단 한 번도 누군가의 왼쪽자식이 되지 않는 경우이다.

[의사 코드]

TREE-SUCCESSOR(x)
    if right[x] != NULL
        then return TREE-MINIMUM(right[x])
    y <- p[x] // p[x]는 x의 부모노드
    while y != NULL and x == right[y]
        do  x <- y
            y <- p[y]
    return y

[Predecessor]

노드 x의 Predecessor란, key[x]보다 작으면서 가장 큰 키를 가진 노드이다. Successor와 반대이다.

Predecessor를 구하는 방법은, Successor에서 왼쪽, 오른쪽을 바꿔주기만 하면 된다.

[의사코드]

TREE-PREDECESSOR(x)
    if left[x] != NULL    
        then return TREE-MAXIMUM(left[x])
    
    y <- p[x]
    while y != NULL and x == left[y]
        do x <- y
           y <- p[y]
    return y

[삽입]

1) 삽입하려는 데이터와 루트 노드를 비교한다. 루트 노드의 값이 더 크다면 삽입할 데이터는 루트 노드의 왼쪽

서브트리에, 더 작다면 루트 노드의 오른쪽 서브트리에 저장한다.

2) 이 과정에서 현재 노드를 가리키는 포인터, 부모 노드를 가리키는 포인터가 필요하다. 그 이유는 대소비교를

통해 왼쪽 혹은 오른쪽 서브트리로 내려가면서 결국에는 null을 만나게 되는데, 이 자리가 바로 새로운 데이터가

삽입될 위치이다. 그런데 삽입될 위치의 부모 노드의 주소값을 알지 못한다면 삽입이 불가능하기 때문이다.

[의사 코드]

TREE-INSERT(T,z) //T는 이진탐색트리, z는 삽입할 노드
    y <- NULL
    x <- root[T]
    while x is not NULL
        do y <- x
        if key[x] > key[z]
            then x <- left[x]
            else x <- right[x]
    end
 
    p[z] <- y
    if y is NULL
        then root[T] <- z
        else if key[z] < key[y]
            then left[y] <- z
            else right[y] <- z
 

[삭제]

삭제 과정은 크게 세 가지로 나뉜다.

1. 삭제하려는 노드(A)가 단말 노드인 경우

 - A 노드와 그 A노드의 부모간의 연결관계를 끊는다.

2. 삭제하려는 노드(A)가 왼쪽 혹은 오른쪽 서브트리 하나를 갖는 경우

 - A 노드가 부모의 왼쪽 자식인 경우, A노드의 자식을 A노드 부모의 왼쪽자식으로 연결시킨다.

 - A 노드가 부모의 오른쪽 자식인 경우, A노드의 자식을 A노드 부모의 오른쪽자식으로 연결시킨다.

3. 삭제하려는 노드(A)가 왼쪽, 오른쪽 서브트리를 모두 갖는 경우

 - A노드의 Successor 또는 Predecessor를 A노드의 위치에 대입한다. (Successor를 기준으로 설명한다.)

 - Successor는 자식이 0개 혹은 1개이다. Successor란 더 이상 왼쪽으로 갈 수 없는 노드이기때문이다.

 - 그렇기 때문에, Successor가 자식이 있다면 반드시 오른쪽 자식노드만을 가져야 한다.

 - Successor의 값을 A노드에 대입했다면, 기존에 Successor를 삭제해줘야한다.

 - Successor는 자식이 0개 혹은 1개이므로 위의 1번, 2번 과정을 수행하면 된다.

[의사 코드]

TREE-DELETE(T, z) // T는 BST, z는 삭제할 노드
 
    //자식노드가 0개 혹은 1개인 경우 y ← z
    //자식노드가 2개인 경우 y ← successor[y]
    //즉, y가 실제로 삭제될 노드를 가리킴
    if left[z] == NULL or right[z] == NULL
        then y ← z        
        else y ← TREE-SUCCESSOR(z) 
    
    //y의 자식은 0개 혹은 1개인 상태
    //x는 null, left[y], right[y]이다.
    if left[y] != NULL
        then x ← left[y]
        else x ← right[y]
 
    // x의 부모가 y의 부모가 되게한다.
    if x != NULL
        then p[x] ← p[y]
 
    //y가 루트노드인 경우와 아닌 경우
    if p[y] == NULL
        then root[T] ← x
        else if y == left[p[y]]
                then left[p[y]] ← x
                else right[p[y]] ← x
    
    // y가 z의 successor인 경우
    // 즉, z가 자식노드가 2개인 경우
    if y != z
        then key[z] ← key[y]