이진 탐색 트리

Dayon·2023년 3월 5일

자료구조

목록 보기

2/10

📡 이진 탐색 트리

정의

이진 탐색 트리 (binary search tree)는 이진 트리 기반의 탐색을 위한 자료구조 이다.

탐색이란 컴퓨터 프로그램에서 레코드의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다. 레코드의 집합을 일반적으로 table이라 하고, 레코드를 key라 부른다. 탐색 작업을 할때는 primary key가 입력되어 특정한 키를 가진 레코드를 찾는다. 이진 탐색 트리는 이러한 탐색 작업을 효율적으로 하기위한 자료 구조이다.

이진탐색트리란 이진 탐색 트리의 성질을 만족하는 이진 트리를 말한다.

이진탐색(binary search) + 연결리스트(linked list) 를 결합한 자료구조

정의
- 모든 원소의 키는 유일한 키를 가진다
- 왼쪽 서브 트리 키들은 루트 키보다 작다
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다
- 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.
  
  이진탐색의 효율적인 탐색 능력을 유지하면서도 빈번한 자료입력과 삭제를 가능하다.

예시

다음은 이진 탐색 트리의 예시이다. 루트 노드 8을 기준으로 왼쪽 서브 트리에 있는 값들은 (3, 1, 6, 4, 7)은 루트노드인 8보다 작다.
또, 오른쪽 서브트리에 있는 (10, 14, 13)은 루트 노드인 8보다 크다. 이성질은 모든 노드에서 만족된다.
이진 탐색 트리를 중위 순회 방법으로 순회하면 1, 3, 4, 6, 7, 8, 10, 13, 14 로 숫자들의 크기 순이 된다.

알고리즘

순환적인 탐색 연산

이진 탐색 트리에서 특정한 키값을 가진 노드를 찾기 위해서는 먼저 주어진 탐색키 값과 루트 노드의 키값을 비교한다. 비교한 결과가,

같으면 탐색 성공
주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 자식을 기준으로 다시 시작한다.
주어진 키 값이 루트 노드의 키값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.

위에 예시 이진 탐색 트리에서 6을 찾는 과정을 살펴보면, 6 탐색 → 루트 8보다 작으므로 왼쪽 자식부터 다시 탐색 → 왼쪽 자식의 루트인 3보다 크므로 오른쪽 자식부터 다시 탐색 → 탐색 키와 동일한 6 탐색 성공 !

// 순환적인 탐색 함수
TreeNode * search (TreeNode * node, int key)
{
    if (node == NULL) return NULL;
    if (key == node->key) return node ;
    else if (key < node-> key)
        return search(node -> left, key);
    else 
        return search(node -> right, key);
}

삽입연산

먼저 탐색을 수행해야 한다. 이진 탐색 트리에서는 같은 키 값을 갖는 노드가 없어야 하고, 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문이다.

아래 코드는 루트노드가 root인 이진탐색트리에 새로운 노드 n을 삽입하는 알고리즘이다

새로운 노드는 항상 단말노드에 추가되고, 단말 노드를 발견할 때 까지 루트에서 키를 검색한다.

TreeNode * insert_node (TreeNode * node, int key)
{
    // 트리가 공백이면 새로운 노드 반환
		// new_node 함수는 동적으로 메모리 할당해서 새로운 노드를 생성해 반환하는 유틸리티 함수 
    if (node == NULL) return new_node(key); 

    // 그렇지 않으면 순환적으로 트리를 내려간다
    if (key < node->key)
        node->left = insert_node(node->left, key);
    else if (key > node->key)
        node -> right = insert_node(node->right, key);
    
    // 변경된 루트 포인터 반환
    return node; 
}

삭제 연산

먼저 노드를 삭제하기 위해서는 삽입과 마찬가지로 먼저 노드를 탐색하고, 아래 3가지 사항을 고려해야 한다.

삭제하려는 노드가 단말 노드일 경우

삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우

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

1번의 경우 : 삭제하려는 노드가 단말노드일 경우

단말 노드 아래에 더이상 노드가 없으므로 단말노드만 지우면 된다. 단말 노드의 부모노드를 찾아서 부모노드 안의 링크 필드를 null로 만들어 연결을 끊으면 된다.

2번의 경우 : 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브트리 중 하나만 가지고 있는 경우

삭제되는 노드가 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우 자기 노드는 삭제하고 서브트리는 자기 노드의 부모 노드에 붙여주면 된다.

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

왼쪽 서브 트리에서 가장 큰값은 오른쪽 서브트리에서 가장 작은 값과 가장 가까이 위치하고 있다. 따라서 삭제 노드가 18이라고 했을때 후계자가 될 수 있는 대상노드는 12와 22가 된다. (왼쪽 서브 트리에서 제일 큰값 과 오른쪽 서브트리에서 제일 작은 값)

이들 후계자 대상 노드 중에서 어느 것을 선택해도 상관이 없다. 예를 들어서 오른쪽 서브 트리에서 제일 작은 값 (22)을 후계자로 선택해보자. 이때 후계자 노드는 오른쪽 서브트리에서 가장 작은 값을 갖는 노드는 오른쪽 서브트리에서 왼쪽 자식 링크를 타고 NULL을 만날때 까지 계속 진행하면 된다.

최종적으로 22가 18자리로 이동하게 된다.

전체 삭제 함수 코드

// 이진 탐색 트리와 키가 주어지면 키가 저장된 노드를 삭제하고 새로운 루트 노드를 반환한다. 
TreeNode * delete_node (TreeNode * root, int key)
{
    if (root == NULL) return root; 

    // 키가 루트 보다 작으면, 왼쪽 서브트리에 있는 것
    if (key < root->key)
        root->left = delete_node(root->left, key);
    // 키가 루트 보다 크면, 오른쪽 서브트리에 있는 것
    else if (key > root->key)
        root -> right = delete_node(root->right, key);
    
    // 키가 루트와 같으면 이 노드를 삭제하면 된다
    else {
    // 첫 번째나 두 번째 경우
    if (root->left == NULL) {
        TreeNode * temp = root-> right;
        free(root);
        return temp;
    }

    else if (root->right == NULL) {
        TreeNode * temp = root -> left ;
        free(root);
        return temp;
    }
    // 세 번째 경우
    TreeNode * temp = min_value_node(root->right);

    // 중위 순회시 후계 노드를 복사
    root -> key = temp -> key ;
    // 중위 순회시 후계 노드 삭제 
    root -> right = delete_node(root->right, temp->key);
    }
    return root; 
}

🕵🏻 탐색

분석

이진 탐색 트리에서 탐색, 삽입, 삭제 연산의 시간복잡도는 트리의 높이를 h라고 했을때 $O(h)$ 가 된다.

따라서 $n$ 개의 노드를 가지는 이진 탐색 트리의 경우, 일반적인 이진트리의 높이는 $log_2 n$ 이므로 이진 탐색 트리 연산의 평균적인 경우의 시간복잡도는 $O(log_2h)$ 이다.

이진 탐색과 이진 탐색 트리의 차이점

이진 탐색, 이진 탐색 트리는 근본적으로 같은 원리에 의한 탐색 구조

이진 탐색은 자료들이 배열에 저장되어 있으므로 삽입과 삭제가 상당히 힘들다.

자료를 삽입하고 삭제할 때마다 앞뒤의 원소들을 이동시켜야 한다.

반면에 이진 탐색 트리는 비교적 빠른 시간 안에 삽입과 삭제를 끝마칠 수 있는 구조로 되어 있다.

따라서 삽입과 삭제가 심하지 않은 정적인 자료를 대상으로 탐색이 이루어지는 경우에는 이진 탐색도 무난한 방법이나 삽입, 삭제가 빈번히 이뤄진다면 반드시 이진 탐색 트리를 사용해야 한다.

알고리즘	최악의 경우 (탐색)	최악의 경우 (삽입)	평균적인 경우 (탐색)	평균적인 경우 (삽입)
순차탐색 (정렬되지 않은 연결리스트 사용)	$N$	$N$	$N/2$	$N/2$
이진 탐색 (정렬된 배열)	$logN$	$N$	$logN$	$N/2$
이진 탐색 트리	$N$	$N$	$logN$	$logN$