[자료구조론] 8 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)

자료구조 설계에서 가장 핵심적인 과제 중 하나는 데이터 레코드 집합과 각각의 고유한 키 값이 주어졌을 때, 특정 검색 키를 가진 레코드를 가장 효율적으로 찾아내는 것이다.

1차원 선형 배열에서의 검색 한계 일반적인 선형 배열을 사용할 경우 검색과 삽입/삭제 성능 사이에 트레이드오프가 발생한다

• 순차 검색
  • 키 값을 선형 배열에 순서 없이 단순히 저장하고 처음부터 끝까지 차례대로 찾는다
  • 검색 성능: O(n): 데이터가 많아질수록 정비례하여 느려진다
  • 삽입 성능: O(1): 배열의 맨 끝에 그냥 집어넣으면 되므로 매우 빠르다
• 이진 검색
  • 검색 속도를 높이기 위해 배열의 키 값들을 크기순으로 정렵하여 저장한다
  • 검색 성능: O(log n): 업다운 게임처럼 범위를 절반씩 좁혀가므로 매우 빠르다
  • 삽입/삭제 성능: 자료구조의 형태에 따라 정렬 상태를 유지하기 위해 기존 데이터들을 뒤로 밀거나 앞으로 당겨야 하므로 상당한 연산 오버헤드가 발생한다
• 검색도 빠르고, 삽입과 삭제도 효율적으로 처리할 수 있는 구조가 필요하게 되었고, 이를 위해 고안된 특별한 자료구조가 바로 이진 탐색 트리(BST)이다

이진 탐색 트리(BST)

이진 탐색 트리는 이진 트리의 일종으로, 모든 노드 $X$에 대해 다음과 같은 명확한 크기 규칙을 만족한다

• 왼쪽 서브트리의 규칙: 노드 $X$의 왼쪽 서브트리에 있는 모든 키 값들은 $X$의 키 값보다 작아야 한다
• 오른쪽 서브트리의 규칙: 노드 $X$의 오르쪽 서브트리에 있는 키 값들은 $X$의 키 값보다 커야 한다

두 트리를 비교해 보면 더 알기 쉽다. 왼쪽 트리는 루트 노드 6을 기준으로 왼쪽 서브트리는 모두 6보다 작고, 오른쪽은 6보다 커, 규칙을 완벽히 만족한다. 반면 오른쪽 그림은 4의 오른쪽 자식으로 7이 붙어 있어, 규칙에 만족하지 못해 BST가 아니다

이진 탐색 트리 추상 데이터 타입(BST ADT)

이진 탐색 트리 추상 데이터 타입은 다음과 같은 핵심 연산들을 처리할 수 있다

• find(x, T) (검색): 트리 $T$에서 키 값 $x$를 탐색한다. 검색 성공 여부(True/False)나 해당 레코드를 가리키는 포인터를 반환한다
• insert(x, T) (삽입): 트리 $T$에 새로운 키 값 $x$를 알맞은 위치에 삽입한다. 만약 $x$가 이미 트리에 존재한다면 아무것도 하지 않거나, 에러 메시지를 보내거나, 참조 횟수(Reference count)를 증가시키는 등 적절한 예외 처리를 수행한다
• delete(x, T) (삭제): 트리 $T$에서 키 값 $x$를 찾아 삭제한다. 만약 존재하지 않는 값을 삭제하려 하면 에러 메시지를 출력한다

구조체 구현

메모리상에서 이진 탐색 트리의 노드는 일반적인 이진 트리 노드 구조와 형태가 동일하다. 단지 데이터를 저장하고 가리키는 논리적인 규칙만 다를 뿐이다

typedef struct TreeNode* SearchTree;
typedef struct TreeNode* Node;
 
struct TreeNode
{
    ElementType Element;    // 노드에 저장될 키 값 데이터
    SearchTree  Left;       // 나보다 작은 값들이 모인 왼쪽 자식을 가리키는 포인터
    SearchTree  Right;      // 나보다 큰 값들이 모인 오른쪽 자식을 가리키는 포인터
};

이진 탐색 트리: Find

찾고자 하는 키 값 $X$를 루트 노드부터 비교해가며 탐색한다. 규칙에 따라 매 단계마다 탐색 범위가 절반 서브트리로 줄어든다

알고리즘 메커니즘(재귀적 구현)

• 현재 노드가 Null이면 트리가 비어있거나 찾는 값이 없는 것이므로 Null을 반환한다
• 찾으려는 값 $X$가 현재 노드의 값보다 작으면, 왼쪽 서브트리로 이동하여 다시 찾는다
• 찾으려는 값 $X$가 현재 노드의 값보다 크며, 오른쪽 서브트리로 이동하여 다시 찾는다
• 둘 다 아니라면 값을 찾은 것이므로 현재 노드의 주소를 반환한다

코드 구현

Node Find(ElementType X, SearchTree T) {
    if (T == NULL)
        return NULL;
    if (X < T->Element)
        return Find(X, T->Left);  // 왼쪽으로 파고들기
    else if (X > T->Element)
        return Find(X, T->Right); // 오른쪽으로 파고들기
    else
        return T;                 // X == T->Element (찾음!)
}

이진 탐색 트리: FindMax

BST의 구조상 가장 큰 값은 항상 트리의 가장 오른쪽 끝에 존재한다

알고리즘 메코니즘(반복적 구현)

• 오른쪽 자식 노드가 없을 때(T->Right == NULL)까지 계속해서 Right 포인터를 타고 오른쪽으로만 직진한다
• 재귀 호출을 쓰지 않는 반복문 형태로 구현하면 함수 호출 오버헤드가 없어 효율적이다

코드 구현

Node FindMax(SearchTree T) {
    if (T == NULL)
        return NULL;
    else
        while (T->Right != NULL)
            T = T->Right; // 오른쪽 끝까지 직진
    return T;
}

이진 탐색 트리: FindMin

BST의 구조상 가장 작은 값은 항상 트리의 가장 왼쪽 끝에 존재한다

알고리즘 메커니즘(재귀적 구현)

• 왼쪽 자식 노드가 없을 때(T->Left == NULL)까지 계속해서 Left 포인터를 호출하며 왼쪽으로만 내려간다

코드 구현

Node FindMin(SearchTree T) {
    if (T == NULL)
        return NULL;
    else if (T->Left == NULL)
        return T;                 // 가장 왼쪽 끝에 도달함
    else
        return FindMin(T->Left);  // 왼쪽으로 계속 파고들기
}

이진 탐색 트리: Insert

BST에 새로운 키 값을 삽입할 때는 트리의 크기 규칙을 깨뜨리지 않는 알맞은 위치를 찾아내어 동적으로 노드를 추가해야 한다

알고리즘 메커니즘(재귀적 구현) 새로운 데이터 $X$를 삽입할 때, Find 연산과 마찬가지로 루트 노드부터 대소 관계를 비교하며 트리 아래로 타고 내려간다

• 트리가 비어있는 위치(T == NULL)에 도달한 경우:
  • 삽입할 올바른 자리를 찾은 것이다. malloc을 통해 새로운 노드를 동적으로 생성하고, 데이터 ㅎ필드에 $X$를 넣은 뒤, 왼쪽/오른쪽 자식을 Null로 초기화하여 반환한다
• 삽입하려는 값 $X$가 현재 노드의 값보다 작은 경우:
  • 왼쪽 서브트리로 이동하여 삽입 함수를 재귀적으로 호출한다(T->Left = Insert(X, T->Left);)
• 삽입하려는 값 $X$가 현재 노드의 값보다 큰 경우:
  • 오른쪽 서브트리로 이동하여 삽입 함수를 재귀적으로 호출한다(T->Right = Insert(X, T->Right);)
• 삽입하려는 값 $X$가 현재 노드의 값과 이미 같은 경우:
  • 중복된 키 값이 트리에 이미 존재하는 상황이다. 아무 작업도 하지 않고 기존 트리(T)를 그대로 반환한다

코드 구현

SearchTree Insert(ElementType X, SearchTree T) {
    if (T == NULL) {
        /* 트리가 비어있거나 올바른 삽입 위치(리프 노드 하단)를 찾은 경우 */
        T = malloc(sizeof(struct TreeNode));
        if (T == NULL)
            FatalError("Out of space!!!"); // 메모리 부족 예외 처리
        else {
            T->Element = X;
            T->Left = T->Right = NULL; // 새 리프 노드로 초기화
        }
    }
    else if (X < T->Element)
        T->Left = Insert(X, T->Left);   // 나보다 작은 값이므로 왼쪽 자식 자리에 삽입 유도
    else if (X > T->Element)
        T->Right = Insert(X, T->Right); // 나보다 큰 값이므로 오른쪽 자식 자리에 삽입 유도
        
    /* X가 이미 트리에 존재한다면(X == T->Element), 아무것도 하지 않음 */
    
    return T; /* 수정되거나 생성된 노드의 포인터를 반환 */
}

이진 탐색 트리: Delete

이진 탐색 트리(BST)에서 노드를 삭제할 때는 삭제 후에도 트리의 규칙이 그대로 유지되도록 재구성해야 한다. 삭제할 노드가 가진 자식 노드의 개수에 따라 3가지 독립된 케이스로 나뉜다

자식의 개수에 따른 3가지 삭제 규칙

삭제할 노드가 리트 노드인 경우(자식이 0개)

• 그냥 삭제하면 끝난다. 부모 노드가 이 노드를 가리키던 포인터를 Null로 바꾸어 연결을 끊어준다

삭제할 노드가 자식을 1개만 가진 경우

• 삭제할 노드의 자식 노드를 부모 노드에 직졉 연결해준다

삭제할 노드가 자식을 3개 모두 가진 경우

• 삭제할 노드의 오른쪽 서브트리에서 가장 작은 노드를 찾아 그 값으로 삭제할 노드의 값을 덮어쓴다. 그리고 나서 아래쪽에 혼자 남겨진 그 가장 작은 노드를 규칙 1또는 규칙 2를 적용해 실제 삭제 처리한다

코드 구현

SearchTree Delete(ElementType X, SearchTree T) {
    Node TmpCell;
 
    if (T == NULL)
        Error("Element not found"); // 삭제할 값이 트리에 없는 경우 에러 처리
    else if (X < T->Element)
        T->Left = Delete(X, T->Left);   /* 왼쪽 서브트리로 탐색 진행 */
    else if (X > T->Element)
        T->Right = Delete(X, T->Right); /* 오른쪽 서브트리로 탐색 진행 */
        
    /* ──────────────── 드디어 삭제할 노드를 찾은 순간 (X == T->Element) ──────────────── */
    else if (T->Left && T->Right) { 
        /* [케이스 3] 자식이 2개인 노드를 삭제하는 경우 */
        TmpCell = FindMin(T->Right);        // 오른쪽 서브트리에서 가장 작은 값을 찾음
        T->Element = TmpCell->Element;      // 그 값으로 현재 노드를 덮어씀
        T->Right = Delete(T->Element, T->Right); // 아래쪽 서브트리에서 대체된 원본 노드를 최종 제거
    } 
    else { 
        /* [케이스 1 & 2] 자식이 0개 또는 1개인 노드를 삭제하는 경우 */
        TmpCell = T;
        if (T->Left == NULL)      // 왼쪽 자식이 없다면 (오른쪽 자식만 있거나 둘 다 없는 경우)
            T = T->Right;         // 오른쪽 자식을 위로 올려 부모와 연결시킴
        else if (T->Right == NULL) // 오른쪽 자식이 없다면 (왼쪽 자식만 있는 경우)
            T = T->Left;          // 왼쪽 자식을 위로 올려 부모와 연결시킴
            
        free(TmpCell); /* 메모리에서 노드를 완전히 해제 */
    }
 
    return T;
}

이진 탐색 트리의 복잡도 분석

트리의 높이와 실행 시간의 관계

이진 탐색 트리에서 주요 연산들의 실행 시간은 트리의 높이에 정비례한다. 따라서 데이터 삽입 순서에 따라 트리의 형태가 어떻게 결정되느냐가 성능을 좌우한다

최선의 케이스

• 트리 형태: 모든 레벨이 빈틈없이 채워진 Complete 이진 트리 형태를 띤다
• 시간 복잡도: $O(\log n)$
• 발생 조건: 데이터가 골고루 분산되어 들어올 때 발생한다(예: 4, 2, 6, 1, 3, 5, 7 순서로 삽입)

최악의 케이스

• 트리 형태: 노드들이 한 줄로 길게 늘어선 사향/선형 트리(Linear/Skewed Tree) 형태를 띱니다. 사실상 연결 리스트(Linked List)와 다를 바 없는 구조가 된다
• 시간 복잡도: $O(n)$
• 발생 조건: 이미 정렬된 데이터가 순서대로 들어올 때 발생한다 (예: 1, 2, 3, 4, ... 순서로 삽입)

평균 케이스 분석

평균적인 성능을 수학적으로 규명하기 위해 내부 경로 길이, $D(N)$의 개념을 도입한다. $D(N)$은 $N$개의 노드를 가진 이진 탐색 트리 $T$에 있는 모든 노드의 깊이(Depth)를 더한 값이다

$D(N)=\frac{2}{N}{\sum }_{j=0}^{N-1}D(i)+N-1$

이진 탐색 트리의 구조적 결함과 해결색

• 원인과 한계:
  • 무작위가 아닌 정렬된 데이터나 특정 패턴을 가진 데이터가 연속으로 들어오면 트리가 한쪽으로 심하게 치우치는 비대칭/불균형 트리가 형성된다. 이 경우 이진 탐색 트리의 최대 장점이었던 $O(\log n)$의 시간 복잡도가 무너지고 $O(n)$에 수렴하게 된다
• 궁극적인 해결책 (균형 트리의 필요성):
  • “데이터가 어떤 순서로 들어오든 상관없이, 트리가 스스로 형태를 재조정하여 항상 $O(\log n)$의 높이를 유지하도록 강제할 수는 없을까?”라는 고민이 시작된다. 이를 구현하기 위해서는 각 노드가 스스로의 균형 상태를 체크할 수 있는 균형 정보를 내부에 가지고 있어야 한다. 이러한 한계를 극복하고 스스로 항상 균형을 유지하도록 설계된 업그레이드형 자료구조가 바로 AVL 트리나 레드-블랙 트리(Red-Black Tree) 같은 균형 이진 탐색 트리이다