[자료구조] #16 Binary Search Tree(1)

• 탐색(Search)

 

특정 자료구조 내에 저장된 정보를 찾아내는 일이다.

방대하게 저장된 데이터에서 원하는 정보를 효율적으로 찾아내는 것은 중요하다.

 

n개의 아이템을 가지는 1차원 배열에서 원하는 값을 찾기 위해 가장 간단한 방법은 순차 탐색이다.

그러나 순차 탐색은 최악의 경우 O(n)의 시간 복잡도를 요구한다.

(마지막에 있거나 아예 없거나)

 

그렇다면 Insert/remove/search 등을 O(n) 보다 더 빠르게 할 수 있는 방법은 없을까?

 

탐색을 위해 특화된 이진 트리인 이진 탐색 트리에 대해 알아보도록 하자.

 

• Key & Value

 

트리에서 노드는 key와 value를 가진다.

Key : 해당 노드를 다른 노드와 구분 짓게 하는 식별자(ID)를 의미한다.

Value : key에 대응되는 데이터 값을 의미한다.

 

트리에서 search를 할때 key를 기준으로 찾는다.

 

• 이진 탐색 트리(Binary Search Tree)

 

BST에는 몇가지 특징이 있다.

• 모든 노드는 유일한 key를 가진다.
  따라서 key들끼리는 비교가 가능하고 순서가 존재한다.
• 왼쪽 서브트리의 key들은 루트의 key보다 작다.
• 오른쪽 서브트리의 key들은 루트의 key보다 크다.
• 왼쪽 및 오른쪽 서브트리는 재귀적으로 이진 탐색 트리여야 한다.

주요 연산

- search(key) : key를 가지는 노드(or value)를 찾아 반환한다.

- insert(key, value) : 이진 탐색 트리의 특성을 유지하면서 주어진 key와 value를 가지는 노드를 삽입한다.

  이때 이미 트리에 해당 key를 가지는 노드가 있다면 주어진 value로 업데이트한다.

- remove(key) : 이진 탐색 트리의 특성을 유지하면서 key를 가지는 노드를 트리에서 삭제한다.

 

따라서 우리는 이 두가지 문제를 항상 고민해봐야 한다!

1. insert/remove를 하면서 특성을 유지할 수 있을까?
2. O(n)보다 빠르게 수행할 수 있을까?

• Search

 

Case 1) 탐색 키와 현재 노드의 key가 같은 경우

→ 원하는 값을 찾은 것으로 현재 노드(or value)를 반환한다.

 

Case 2) 탐색 키가 현재 노드의 key보다 작은 경우

→ 왼쪽 서브트리를 기준으로 다시 search를 수행한다.

 

Case 3) 탐색 키가 현재 노드의 key보다 큰 경우

→ 오른쪽 서브트리를 기준으로 다시 search를 수행한다.

 

12를 탐색키라고 하면 아래 그림과 같이 탐색이 진행될 것이다.

 

재귀를 사용한 Search의 슈도 코드를 살펴보자.

def search(node, key):  # key는 사용자가 찾는 값
    if node == NULL or key == node’s key:  # 노드가 NULL이거나 키가 일치하면
        return node  # 현재 노드 반환 (case 1)
    elif key < node’s key:  # 찾는 키가 현재 노드의 키보다 작으면
        return search(node->left, key)  # 왼쪽 자식에서 탐색
    else:  # 찾는 키가 현재 노드의 키보다 크면 (case 2)
        return search(node->right, key)  # 오른쪽 자식에서 탐색 (case 3)

 

반복문을 사용한 search의 슈도 코드를 살펴보자.

def search_iter(node, key): 
    cur_node = node  # 탐색을 시작할 현재 노드를 초기화
    while cur_node != NULL:  # 현재 노드가 NULL이 아닐 때까지 반복 
        if key == cur_node’s key:  # 현재 노드의 키가 찾는 키와 같으면
            return cur_node  # 현재 노드 반환 (case 1)
        elif key < cur_node’s key:  # 찾는 키가 현재 노드의 키보다 작으면
            cur_node = cur_node->left  # 왼쪽 자식으로 이동 (case 2)
        else:  # 찾는 키가 현재 노드의 키보다 크면
            cur_node = cur_node->right  # 오른쪽 자식으로 이동 (case 3)
    return cur_node  # 키를 찾지 못한 경우 NULL 반환 (fail)

 

• Insert

 

BST에 원소를 삽입하기 위해서는 먼저 탐색을 수행해야 한다.

 

탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치이다.

동일한 key를 가지는 경우 주어진 value로 update 한다.

 

따라서 Insert는 탐색에 실패한 위치에 새로운 노드를 넣는다라고 요약할 수 있다.

def insert(node, key, value):  # key와 value는 삽입하려는 값과 그 값에 대한 데이터
    if key == node’s key:  # 현재 노드의 키가 삽입하려는 키와 같으면
        node’s value = value  # 현재 노드의 값을 업데이트하고 반환
        return
    elif key < node’s key:  # 삽입하려는 키가 현재 노드의 키보다 작으면
        if node->left == NULL:  # 현재 노드의 왼쪽 자식이 NULL이면
            node->left = Node(key, value, NULL, NULL)  # 새 노드를 왼쪽 자식으로 삽입
        else:  # 왼쪽 자식이 NULL이 아니면
            insert(node->left, key, value)  # 왼쪽 자식 노드에서 재귀적으로 삽입
    else:  # 삽입하려는 키가 현재 노드의 키보다 크면
        if node->right == NULL:  # 현재 노드의 오른쪽 자식이 NULL이면
            node->right = Node(key, value, NULL, NULL)  # 새 노드를 오른쪽 자식으로 삽입
        else:  # 오른쪽 자식이 NULL이 아니면
            insert(node->right, key, value)  # 오른쪽 자식 노드에서 재귀적으로 삽입

 

• Remove

 

먼저 삭제하려는 노드를 search를 통해 찾는다.

 

Case 1) 삭제하려는 노드가 리프 노드인 경우

 

부모 노드에서 삭제할 노드로 가는 포인터에 대해 NULL 처리 후 해당 노드를 해제한다.

만일 삭제하려는 노드가 로트인 동시에 리프인 경우 부모가 없기 때문에 삭제만 하면 된다. 

 

Case 2) 삭제하려는 노드가 왼쪽 또는 오른쪽 서브트리 중 하나만 자식으로 가지고 있는 경우

 

서브트리의 루트를 부모 노드에 붙여주고 해당 노드는 해제한다.

 

삭제하려는 노드가 전체 트리의 루트인 경우 서브트리의 루트는 전체 트리의 루트로 대체된다.

 

Case 3) 삭제하려는 노드가 두개의 서브트리를 모두 가지고 있는 경우

 

삭제하려는 노드를 대체할 다른 노드를 찾아야 한다.

이를 후계자(successor)라고 한다.

 

후계자 1) 왼쪽 서브트리에서 제일 큰 key

후계자 2) 오른쪽 서브트리에서 제일 작은 key

 

후계자 1과 2 중 어느 것을 선택해도 구조가 유지된다.

우리는 후계자 2를 선택하도록 하자.

 

후계자 노드의 key & value를 삭제할 노드로 복사하고 후계자 노드를 삭제한다.

// 탐색
def remove(node, parent, key):  # key는 삭제할 값
    if node == NULL:  # 노드가 NULL이면
        return  # 종료
    if key < node’s key:  # 키가 현재 노드의 키보다 작으면
        remove(node->left, node, key)  # 왼쪽 자식에서 삭제
    elif key > node’s key:  # 키가 현재 노드의 키보다 크면
        remove(node->right, node, key)  # 오른쪽 자식에서 삭제
    else:  # 키가 현재 노드의 키와 같으면
// Case 3
        if node has both left & right children:  # 양쪽 자식이 모두 있으면
            successor = leftmost(node->right)  # 후계자 찾기
            replace node with successor & remove successor  # 후계자로 교체하고 후계자 삭제
// Case 2
        elif node has only a left child:  # 왼쪽 자식만 있으면
            replace node in its parent with node->left  # 왼쪽 자식으로 교체
        elif node has only a right child:  # 오른쪽 자식만 있으면
            replace node in its parent with node->right  # 오른쪽 자식으로 교체
// Case 1
        else:  # 자식이 없으면
            replace node in its parent with NULL  # NULL로 교체 (노드 삭제)

 

• Leftmost/Rightmost 노드

 

이진 탐색 트리에서 제일 작은 key 또는 제일 큰 key는 어떻게 찾을 수 있을까?

 

제일 작은 key를 가지는 노드는 트리의 제일 왼쪽에 위치하며 왼쪽에는 더 이상 자식 노드가 없다.

→ leftmost 노드

 

제일 큰 key를 가지는 노드는 트리의 제일 오른쪽에 위치하며 오른쪽에는 더 이상 자식 노드가 없다.

→ rightmost 노드

 

귀류법을 통해 이를 증명할 수도 있다.

 

가정 : Leftmost 노드가 minimum key를 가지지 않는다.

→ 트리의 leftmost를 제외한 어딘가에 minimum key를 가지는 node가 있다.

→ BST 정의에 어긋나게 되어 모순이 발생한다.

 

따라서 가정의 가정이 거짓이므로 Leftmost 노드가 Min이라는 것은 참이다.