자료 구조 - 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree)는 고정된 데이터 집합에서만 가능하던 이진 탐색의 단점을 보완한 이진 탐색을 위한 이진트리입니다. 그렇다면, 이진트리와 이진 탐색 트리의 다른 점은 무엇일까요? 이진 탐색 트리는 다음과 같은 규칙을 따릅니다.

• 왼쪽 자식 노드는 루트 노드보다 작고, 오른쪽 노드는 루트 노드보다 크다.

 

이진 트리 탐색에서의 이진 탐색

---

이진트리 탐색서의 이진 탐색은 기본적인 이진 탐색과 다르지 않습니다.

다만, 고정된 배열의 이진 탐색에서 중앙 요소가 이진트리에서는 루트 노드가 그 역할을 하게 됩니다. 목푯 값이 루트 노드보다 크면 오른쪽 트리를 탐색하고 작으면 왼쪽 트리를 탐색합니다.

 

그럼 위의 이진트리에서 목푯 값 34를 찾아가는 과정을 살펴보겠습니다.

 

1. 목푯 값 34는 루트 노드 23 보다 큰 숫자 이므로 오른쪽 트리는 탐색합니다.
2. 다음 루트 노드인 56보다 목표 값 34가 더 작으므로 왼쪽 트리를 탐색합니다.
3. 왼쪽 트리 노드인 34와 목표 값 34 일치

 

아래는 코드 예시입니다.

BSTNode* BST_SearchNode(BSTNode* Tree, int Target) {
 
    if (Tree == NULL){ // 이진 탐색 트리가 널이면
        return NULL; // 널 반환
    }
    
    if (Tree->Data == Target) { // 트리의 루트 노드의 데이터와 타겟이 일치하면
        return Tree; // 노드 반환
    }
    else if (Tree->Data > Target) { // 루트 노드의 데이터가 목표 값 보다 크면
        return BST_SearchNode(Tree->Left, Target); // 왼쪽 자식 노드로 재귀
    }
    else if (Tree->Data < Target) { // 루트 노드의 데이터가 목표 값 보다 작으면
        return BST_SearchNode(Tree->Right, Target); // 오른쪽 자식 노드로 재귀
    }
}

 

이진 탐색 트리의 노드 삽입

---

이진 탐색 트리의 노드 삽입은 이진 탐색과 크게 다르지 않습니다.

위에서 알려드린 이진 탐색 트리의 규칙을 만족해야 하기 때문에 이진 탐색을 통해 노드가 놓일 적절한 위치를 찾아야 합니다.

 

아래는 코드의 예시입니다.

void BST_InsertNode(BSTNode** Tree, BSTNode* Child) {
    if ((*Tree)->Data < Child->Data) { // 삽입할 데이터가 루트 노드보다 크면 오른쪽 노드로
        if ((*Tree)->Right == NULL) { // 오른쪽 노드가 널이면
            (*Tree)->Right = Child; // 삽입
        }
        else { // 오른쪽 노드가 널이 아니면 
            BST_InsertNode((*Tree)->Right, Child); // 오른쪽 자식 노드로 재귀
        }
    }
    else if ((*Tree)->Data > Child->Data) { // 삽입할 데이터가 루트 노드보다 작으면 왼쪽 노드로
        if ((*Tree)->Left == NULL) { // 널이면
            (*Tree)->Left = Child; // 삽입
        }
        else { // 왼쪽 노드가 널이 아니면
            BST_InsertNode((*Tree)->Left, Child); // 왼쪽 자식 노드로 재귀
        }
    } 
    else { // 삽입할 데이터와 루트노드가 같으면
        printf("중복 노드 입니다.");
        return; // 리턴
    }
}

이진 탐색 트리는 중복이 필요하지 않은 자료 구조입니다. 왜냐하면 탐색을 위한 자료 구조이기 때문에 굳이 중복 값을 넣어서 효율을 떨어뜨릴 필요가 없기 때문에 죠. 필요하다면, 노드에 카운트를 넣어서 관리해주는 편이 좋다고 생각합니다.

 

이진 탐색 트리의 노드 삭제

---

이진 탐색 트리의 노드 삭제는 아래와 같은 경우들이 있습니다.

1. 자식 노드가 있는 경우
• 양쪽 자식 노드를 모두 갖고 있는 경우
• 왼쪽/오른쪽 중 한쪽 자식 노드만 갖고 있는 경우
2. 자식 노드가 없는 경우

 

먼저 자식 노드가 없는 경우는 간단합니다.

삭제할 노드를 찾은 후 해당 노드의 루트 노드에서 해당 노드로 가는 포인터를 NULL로 해준다면 끝이 나게 됩니다.

 

다음으로 왼쪽/오른쪽 중 한쪽 자식 노드만 갖고 있는 경우입니다.

위와 마찬가지로 해당 노드를 찾은 후 루트 노드에서 해당 노드로 가는 포인터를 NULL로 해줍니다. 그 후 해당 노드의 자식 노드를 루트 노드와 연결시켜주면 끝이 나게 됩니다.

마지막으로 양쪽 자식 노드를 모두 갖고 있는 경우입니다.

아래의 그림에서 11 노드를 삭제한다고 예를 들어보겠습니다. 제거 후 자식 노드를 연결시켜줄 때 어떤 노드를 연결시켜야 '이진 탐색 트리의 특성'을 유지할 수 있을까요?

그 답은 삭제할 노드의 '오른쪽 트리 중에서 가장 작은 값'을 가진 노드입니다.

가장 작은 값을 가진 최솟값 노드가 오른쪽 자식 노드가 존재한다면 그 노드를 최소값 노드의 루트 노드로 연결시켜 주는 것으로 작업이 마무리됩니다.

아래는 이진 탐색 트리의 삭제에 대한 코드 예시입니다.

BSTNode* BST_SearchMinNode(BSTNode* Tree) {
    if (Tree == NULL) {
        return NULL;
    }
 
    if (Tree->Left == NULL) {
        return Tree;
    }
    else {
        return BST_SearchMinNode(Tree->Left);
    }
}
 
BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, int Target) {
    BSTNode* Removed = NULL;
 
    if (Tree == NULL) {
        return NULL;
    }
 
    if (Tree->Data > Target) { // 삭제할 데이터가 루트 노드보다 작으면
        Removed = BST_RemoveNode(Tree->Left, Tree, Target); // 왼쪽 트리로 이동
    }
    else if (Tree->Data < Target) { // 삭제할 데이터가 루트 노드보다 크면
        Removed = BST_RemoveNode(Tree->Right, Tree, Target); // 오른쪽 트리로 이동
    }
    else { // 삭제할 데이터가 루트 노드와 일치
        Removed = Tree; // 삭제할 데이터는 Tree
 
        if (Tree->Left == NULL && Tree->Right == NULL) { // 삭제할 노드의 자식 노드가 존재 하지 않는다면
            if (Parent->Left == Tree) { // 삭제할 데이터가 루트 노드의 왼쪽 트리면
                Parent->Left = NULL; // 왼쪽 삭제
            }
            else { // 오른쪽이면
                Parent->Right = NULL; // 오른쪽 삭제
            }
        }
        else { // 삭제할 노드의 자식 노드가 존재 한다면
            if (Tree->Left != NULL && Tree->Right != NULL) { // 양쪽다 존재 한다면
                BSTNode* MinNode = BST_SearchMinNode(Tree->Right); // 오른쪽 트리중에서 최소값 노드를 찾는다.
                Removed = BST_RemoveNode(Tree, NULL, MinNode->Data); // 찾은 최소값 노드도 옮겨질 때, 후처리를 해줘야 하기 때문에 똑같이 리무브함수를 호출해준다.
                Tree->Data = MinNode->Data; // 삭제할 노드를 최소값 노드의 데이터로 교체
            }
            else { // 자식 노드가 한쪽만 존재 할 경우
                BSTNode* Temp = NULL;
                if (Tree->Left != NULL) {
                    Temp = Tree->Left;
                }
                else {
                    Temp = Tree->Right;
                }
 
                if (Parent->Left == Tree) {
                    Parent->Left = Temp;
                }
                else {
                    Parent->Right = Temp;
                }
            }
        }
    }
}