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

이진 탐색 트리(Binary Search Tree)

• 한 노드를 기준으로 왼쪽 자식에 있는 트리는 해당 노드보다 작다
• 한 노드를 기준으로 오른쪽 자식에 있는 트리는 해당 노드보다 크다

 

위 그림처럼, 모든 각 노드들에 대하여 왼쪽은 더 작은 값이, 오른쪽은 더 큰 값이 위치해야한다.

 

 

위와 같은 이진탐색트리를 코드로 구현해보겠다.

구현할 기능은 아래와 같다.

• 이진탐색트리에서 가장 작은 값
• 이진탐색트리에서 가장 큰 값
• 이진탐색트리에서 주어진 키 값 찾기
• 이진탐색트리에서 새로운 키 삽입
• 이진탐색트리에서 주어진 키 값 삭제

 

 

이진탐색트리에서 가장 작은 값

해당 노드에서 왼쪽 트리가 더 작아야 하므로 왼쪽으로 쭉 내려가면 가장 작은 값이 나온다.

int min_BST(Node *root) {
    Node *temp = root;
    while(temp->left != NULL) {
        temp = temp->left;
    }
    return temp->data;
}

 

 

이진탐색트리에서 가장 큰 값

해당 노드에서 오른쪽 트리가 더 커야하므로 오른쪽으로 쭉 내려가면 가장 큰 값이 나온다.

int max_BST(Node *root) {
    Node *temp = root;
    while(temp->right != NULL) { 
        temp = temp->right;
    }
    return temp->data;
}

 

 

 

주어진 키 찾기

재귀함수를 사용하여 탐색하도록 한다.

Node* search_BST(Node *root, int key) {
    if(root == NULL)
        return NULL;
    if(key == root->data)
        return root;
    if(key < root->data)
        return search_BST(root->left, key);
    else
        return search_BST(root->right, key);
}

 

 

 

키 값 삽입

가장 위에서부터 새로운 노드와 기존 노드를 비교하여 작으면 왼쪽, 크면 오른쪽으로 이동하여 위치를 찾는다

Node* insert_BST(Node* root, int key) {
    Node *parent = NULL;
    Node *node = root;
    Node *newnode = (Node *)malloc(sizeof(Node));
    newnode->data = key;
    newnode->left = newnode->right = NULL;

    if(node == NULL) {
        root = newnode;
        return root;
    }
    
    while(node != NULL) {
        parent = node;
        if(key < node->data) {
            node = node->left; 
        } else {
            node = node->right;
        }
    }
    
    if(key < parent->data)
        parent->left = newnode;
    else
        parent->right = newnode;
    
    return root;
}

 

 

 

키 값 삭제

아마 가장 까다로운 부분이 아닐까 싶다.

우선 키 값을 삭제하려고 하는 노드의 종류가 세 가지로 나눠질 것이다.

• 자식이 없는 노드(말단 노드)
• 자식이 하나만 있는 노드
• 자식이 둘 다 있는 노드

 

자식이 없는 노드(말단 노드) : 자식이 없는 노드는 해당 노드를 그냥 삭제처리한다.

자식이 하나만 있는 노드 : 삭제할 노드의 부모 노드와 자식 노드를 연결시키는 방식으로 처리

자식이 둘 다 있는 노드 : 삭제할 노드와 가장 비슷한 노드를 찾는다. (여기서는 오른쪽 자식의 가장 왼쪽 노드, 삭제하려던 노드보다 아주 조금 더 큰 노드를 찾는것임) , 그리고 비슷한 노드를 삭제할 노드의 위치로 바꾼다. 

 

Node* BST_delete(Node* root, int key) {
    Node *curr = root;
    Node *parent = NULL;

    // 키 값을 찾을 때까지 반복
    while (curr != NULL && curr->data != key) {
        parent = curr;
        if (key < curr->data)
            curr = curr->left;
        else
            curr = curr->right;
    }

    // 키 값이 발견되지 않음
    if (curr == NULL) {
        printf("Error: 키 값이 트리에 존재하지 않습니다.\n");
        return root;
    }

    // 경우 1: 삭제할 노드가 단말 노드인 경우
    if (curr->left == NULL && curr->right == NULL) {
        if (curr != root) {
            if (parent->left == curr)
                parent->left = NULL;
            else
                parent->right = NULL;
        } else
            root = NULL;

        free(curr);
    }
    // 경우 2: 삭제할 노드가 하나의 자식 노드를 가진 경우
    else if (curr->left == NULL || curr->right == NULL) {
        Node *child;
        if (curr->left == NULL)
            child = curr->right;
        else
            child = curr->left;

        if (curr != root) {
            if (curr == parent->left)
                parent->left = child;
            else
                parent->right = child;
        } else
            root = child;

        free(curr);
    }
    // 경우 3: 삭제할 노드가 두 개의 자식 노드를 가진 경우
    else {
        Node *successor = curr->right;
        Node *successorParent = curr;

        // 오른쪽 서브트리에서 가장 작은 값을 찾음
        while (successor->left != NULL) {
            successorParent = successor;
            successor = successor->left;
        }

        int k_value = successor->data;

        // 후속 노드를 삭제
        root = BST_delete(root, successor->data);

        // 현재 노드의 값을 후속 노드의 값으로 대체
        curr->data = k_value;
    }

    return root;
}

 

 

아마 키 값을 삭제하는 과정이 생각보다 더 어려워 당황할 수 있다. 하지만 이러한 개념을 익혀둔다면 자료구조, 더 나아가 알고리즘 공부를 하는데 많은 도움이 될거라 믿는다.