[알고리즘] 트리4 - 이진 탐색 트리

이진 탐색 트리

이진트리는 트리를 효율적으로 구현하고 관리하기 위해서 일정한 조건으로 정의한 것이며, 이진트리를 탐색용 자료구조로 사용하기 위해 원소 크기에 따라 노드 위치를 정해둔 것이다. 이진트리에서는 내가 필요한 자료(정보)를 찾을 때 KEY 값을 이용하여 자료를 찾는데 이 KEY 값은 자료를 식별할 수 있는 유일한 값이다. (ex: 대학생의 학번 etc..)

이진 탐색 트리의 정의

• 모든 원소는 서로 다른 유일한 키를 갖는다. -> 데이터베이스에서의 기본 키(Primary Key)
• 왼쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 작다.
• 오른쪽 서브 트리에 있는 원소들의 키는 그 루트의 키보다 크다.
• 왼쪽 서브 트리와 오른쪽 서브 트리 둘 다 이진 탐색 트리이다.

왼쪽 서브 트리의 키값 < 루트의 키값 < 오른쪽 서브 트리의 키값

⭐모든 연산에는 탐색 연산이 이루어진 뒤에 삽입, 삭제 등 연산이 이루어져야 한다.⭐

이진 탐색 트리의 탐색 연산

이진 탐색 트리에서 키값이 어떤 값이든 탐색은 항상 루트 노드에서 시작하므로 항상 키값 x와 루트 노드의 키값을 비교한다.

• 키값 x == 루트 노드의 키값인 경우 : 원하는 원소를 찾았으므로 탐색 종료.
• 키값 x < 루트 노드의 키값인 경우 : 루트 노드의 왼쪽 서브 트리에서 탐색 연산을 수행.
• 키값 x > 루트 노드의 키값인 경우 : 루트 노드의 오른쪽 서브 트리에서 탐색 연산을 수행.

이렇게 3개의 경우를 확인하여 찾고자 하는 키값을 찾는데 위에 사진을 예로 들어 키값 5를 찾고자 하는 경우...

• 키값 5 < 루트 노드의 키값 8 : 원하는 원소 값이 8보다 작으므로 왼쪽 서브트리에서 탐색 연산을 수행.
• 키값 5 > 왼쪽 서브 트리에서의 노드 키값 3: 원하는 원소 값이 3보다 크므로 오른쪽 서브트리에서 탐색 연산을 수행.
• 키값 5 == 오른쪽 서브 트리에서의 노드 키값 5: 원하는 원소 값과 같으므로 탐색 종료.

찾고자 원소값 탐색에 실패하였다면 그 값은 트리에 없는 것이다.

이진 탐색 트리의 삽입 연산

이진 탐색 트리에 원소를 삽입하려면 이진 탐색 트리에 같은 원소가 있는지 먼저 확인해야 한다. 

탐색에 성공한다면 이미 같은 원소가 트리에 있으므로 삽입 연산을 수행하지 않고 실패하였다면 원소가 트리에 없다는 의미이므로 탐색에 실패한 곳 즉, 탐색 실패가 발생한 현재 위치에 원소를 삽입한다.

이진 트리에 9를 삽입하는 과정.

이진 탐색 트리의 삭제 연산

삭제 연산도 마찬가지로 삭제할 노드의 위치를 탐색하는 작업을 먼저 수행해야 한다.

삽입 연산과 다르게 삭제할 노드는 자식 노드 수에 따라 세 가지 경우 중 하나인데... 노드를 삭제한 후에도 이진 탐색 트리를 유지해야 하므로 각각 다른 후속 처리가 필요하다.

• 삭제할 노드가 단말 노드인 경우 = 차수는 0
  삭제할 노드가 단말 노드라면 해당 노드를 삭제하고 부모 노드의 링크 필드를 NULL로 설정하면 된다.

이진 탐색 트리에서 단말 노드 2를 삭제하는 예

• 삭제할 노드가 자식 노드를 한 개 가진 경우 = 차수는 1
  삭제할 노드가 자식 노드를 한 개 가진 부모 노드일 경우, 노드를 삭제한다면 자식 노드가 트리에서 분리가 되어버린다.
  이런 경우 자식 노드를 부모 노드의 자리로 올려주는 후처리 작업이 필요하다.

이진 탐색 트리에서 자식 노드가 하나인 노드 11을 삭제하는 예

• 삭제할 노드가 자식 노드를 두 개 가진 경우 = 차수는 2
  자식 노드를 두 개 가지고 있는 노드를 삭제하는 경우에도 삭제 노드 자리를 자식 노드에게 몰려주는 후처리 작업이 필요한데.
  두 개의 자식 중 후계자를 정하여 그 후계자에게 자리를 물려주는 것이다. 이 경우 이진 탐색 트리가 유지되어야 하기에 위에서 정의하였던 (왼쪽 서브 트리의 키값 < 루트의 키값 < 오른쪽 서브 트리의 키값)을 기억하면 된다
  1. 왼쪽 서브 트리에서 가장 큰 키값의 노드를 탐색하는 작업은 왼쪽 서브 트리의 오른쪽 링크를 따라 계속 이동하다가 오른쪽 링크 필드가 NULL인 노드, 즉 왼쪽 서브 트리에서 가장 오른쪽 노드를 찾는 것이다.
  2. 오른쪽 서브 트리에서 가장 작은 키값의 노드를 탐색하는 작업은 오른쪽 서브 트리에서 왼쪽 링크를 따라 계속 이동하다가 왼쪽 링크 필드가 NULL인 노드, 즉 오른쪽 서브 트리에서 가장 왼쪽 노드를 찾는 것이다.

삭제할 노드의 자리를 몰려줄 수 있는 자손 노드

이진 탐색 트리에서 자식 노드가 2 개인 노드 8 을 삭제하는 과정.

 

이진 탐색 트리의 구현

//
//  ex7_4.c
//  Algorithm
//
//  Created by 권xx on 2023/09/18.
//

#include <stdio.h>
#include <stdlib.h>

// 이진 트리 노드 구조체 정의
struct treeNode {
    char key;
    struct treeNode* left;  // 왼쪽 서브 트리 링크
    struct treeNode* right; // 오른쪽 서브트리 링크
};

// 이진 탐색 트리를 중위 순회하면서 출력하는 함수
void displayInorder(struct treeNode* root) {
    if (root) {
        displayInorder(root->left);
        printf("%c ", root->key); // 노드의 키를 출력합.
        displayInorder(root->right);
    }
}
// 이진 탐색 트리에서 키 값이 x인 노드의 위치를 탐색하는 함수
struct treeNode* searchBST(struct treeNode* root, char x) {
    struct treeNode* p = root;
    while (p != NULL) {
        if (x < p->key) p = p->left;
        else if (x == p->key) return p; // 키를 찾았을 때 해당 노드를 반환.
        else p = p->right;
    }
    puts("\n 찾는 키가 없습니다.");
    return p; // 키를 찾지 못한 경우 NULL을 반환.
}

// 포인터 p가 가리키는 노드와 비교하여 노드 x를 삽입하는 함수
struct treeNode* insertBSTNode(struct treeNode* p, char x) {
    struct treeNode* node;

    // 1. 노드 p가 NULL인 경우, 새로운 노드를 동적으로 할당하고 초기화.
    if (p == NULL) {
        // 2. 새로운 노드를 메모리에 할당.
        node = (struct treeNode*)malloc(sizeof(struct treeNode));
        // 3. 새로운 노드의 키 값을 설정.
        node->key = x;
        // 4. 새로운 노드의 왼쪽 서브트리와 오른쪽 서브트리를 초기화.
        node->left = NULL;
        node->right = NULL;
        // 5. 새로운 노드를 생성하고 반환.
        return node;
    }
    
    // 6. 노드 x와 p의 키 값을 비교하여 적절한 서브트리에 삽입.
    else if (x < p->key)
        p->left = insertBSTNode(p->left, x);
    else if (x > p->key)
        p->right = insertBSTNode(p->right, x);

    // 7. 노드를 삽입하고 현재 노드를 반환.
    return p;
}


// 루트 노드부터 탐색하여 키 값과 같은 노드를 찾아 삭제하는 함수
void deleteBSTNode(struct treeNode* root, char key) {
    struct treeNode* parent, *p, *succ, *succ_parent;
    struct treeNode* child;
    parent = NULL;
    p = root;

    while ((p != NULL) && (p->key != key)) {
        parent = p;
        if (key < p->key) p = p->left;
        else p = p->right;
    }

    // 삭제할 노드가 없는 경우
    if (p == NULL) {
        printf("\n 찾는 키가 이진 트리에 없습니다.");
        return;
    }

    // 삭제할 노드가 단말 노드인 경우
    if ((p->left == NULL) && (p->right == NULL)) {
        if (parent != NULL) {
            if (parent->left == p) parent->left = NULL;
            else parent->right = NULL;
        } else {
            root = NULL;
        }
    } else if ((p->left == NULL) || (p->right == NULL)) {
        // 삭제할 노드가 자식 노드를 한 개 가진 경우
        if (p->left != NULL) child = p->left;
        else child = p->right;

        if (parent != NULL) {
            if (parent->left == p) parent->left = child;
            else parent->right = child;
        } else {
            root = child;
        }
    } else { // 삭제할 노드가 자식 노드를 두 개 가진 경우
        succ_parent = p;
        succ = p->left;
        while (succ->right != NULL) {
            // 왼쪽 서브 트리에서 후계자 찾기
            succ_parent = succ;
            succ = succ->right;
        }
        if (succ_parent->left == succ) succ_parent->left = succ->left;
        else succ_parent->right = succ->left;
        p->key = succ->key;
        p = succ;
    }
    free(p); // 노드 메모리 해제
}

// 메뉴를 출력하는 함수
void menu(void) {
    printf("\n----------------------");
    printf("\t1 : 트리 출력");
    printf("\t2 : 트리 삽입");
    printf("\t3 : 트리 삭제");
    printf("\t4 : 트리 검색");
    printf("\t5 : 종료");
    printf("----------------------");
    printf("\n 메뉴 입력-> ");
}

int main(void) {
    struct treeNode* root = NULL;
    struct treeNode* foundedNode = NULL;
    char choice, key;

    // [그림 7-38]과 같은 초기 이진 탐색 트리를 구성하고 노드 G를 노드 포인터 root로 지정
    root = insertBSTNode(root, 'G');  // 'G'의 아스키 코드는 71.
    insertBSTNode(root, 'I');         // 'I'의 아스키 코드는 73.
    insertBSTNode(root, 'H');         // 'H'의 아스키 코드는 72.
    insertBSTNode(root, 'D');         // 'D'의 아스키 코드는 68.
    insertBSTNode(root, 'B');         // 'B'의 아스키 코드는 66.
    insertBSTNode(root, 'M');         // 'M'의 아스키 코드는 77.
    insertBSTNode(root, 'N');         // 'N'의 아스키 코드는 78.
    insertBSTNode(root, 'A');         // 'A'의 아스키 코드는 65.
    insertBSTNode(root, 'J');         // 'J'의 아스키 코드는 74.
    insertBSTNode(root, 'E');         // 'E'의 아스키 코드는 69.
    insertBSTNode(root, 'Q');         // 'Q'의 아스키 코드는 81.


    while (1) {
        menu();
        scanf(" %c", &choice);

        switch (choice - '0') {
            case 1:
                printf("\t[이진 트리 출력]  ");
                displayInorder(root);
                puts("");
                break;
            case 2:
                printf(("삽입할 문자를 입력 : "));
                scanf(" %c", &key);
                root = insertBSTNode(root, key);
                break;
            case 3:
                printf(("삭제할 문자를 입력 : "));
                scanf(" %c", &key);
                deleteBSTNode(root, key);
                break;
            case 4:
                printf(("찾을 문자를 입력 : "));
                scanf(" %c", &key);
                foundedNode = searchBST(root, key);
                if (foundedNode != NULL) printf("\n %c를 찾았습니다. \n", foundedNode->key);
                else printf("\n 문자를 찾지 못하였다. \n");
                break;
            case 5:
                return 0;
            default:
                puts("다시 입력하시오");
                break;
        }
    }
}

2023.11.13 - [알고리즘] - [알고리즘] 트리3 - 스레드 이진 트리

[알고리즘] 트리3 - 스레드 이진 트리