[자료구조 & 알고리즘] 이진 검색 트리 (feat. 트리)

 

자료구조 관련 내용은 하단 포스트를 참고해주세요.

2024.12.14 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

[자료구조 & 알고리즘] 자료구조 개념 총정리 (향후 내용추가)

 

 

0. 이진 트리 (Binary Tree)

• 설명: 각 노드가 최대 두 개의 자식을 가지는 계층적 자료구조.
• 특징:
  • 전위, 중위, 후위 순회 가능.
• 필수 알고리즘:
  1. 트리 순회:
     • 전위, 중위, 후위 탐색.
  2. 최대 깊이 계산:
     • 트리의 깊이 계산.

 

---

1. 이진 검색 트리(Binary Search Tree, BST)란?

이진 검색 트리는 이진 트리의 한 종류로, 특정 규칙을 따릅니다.

이진 검색 트리의 규칙

• 왼쪽 자식 노드의 값은 부모 노드의 값보다 작습니다.
• 오른쪽 자식 노드의 값은 부모 노드의 값보다 큽니다.

예시로 위 트리를 다시 살펴봅시다.

         10
        /  \
       5    15
      / \     \
     3   7     20

• 부모 노드 10: 왼쪽 자식(5)은 10보다 작고, 오른쪽 자식(15)은 10보다 큽니다.
• 부모 노드 5: 왼쪽 자식(3)은 5보다 작고, 오른쪽 자식(7)은 5보다 큽니다.

이 규칙 덕분에 탐색, 삽입, 삭제 등의 연산이 효율적으로 수행됩니다.

---

2. 이진 검색 트리의 주요 연산

1) 탐색(Search)

값이 트리에 있는지 확인하는 과정입니다.
탐색은 루트 노드부터 시작해서 다음과 같은 방식으로 진행됩니다.

1. 찾고자 하는 값이 현재 노드의 값과 같으면 탐색 종료.
2. 찾고자 하는 값이 현재 노드의 값보다 작으면 왼쪽 서브트리로 이동.
3. 찾고자 하는 값이 현재 노드의 값보다 크면 오른쪽 서브트리로 이동.

탐색 예제 코드 (C언어):

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* search(Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;  // 값이 없거나 찾은 경우

    if (key < root->data)
        return search(root->left, key);  // 왼쪽 서브트리 탐색

    return search(root->right, key);     // 오른쪽 서브트리 탐색
}

 

---

2) 삽입(Insertion)

새로운 값을 트리에 추가하는 과정입니다.
삽입할 위치를 찾기 위해 탐색을 수행한 뒤, 해당 위치에 새 노드를 추가합니다.

삽입 규칙

• 삽입할 값이 현재 노드보다 작으면 왼쪽으로 이동.
• 삽입할 값이 현재 노드보다 크면 오른쪽으로 이동.
• 알맞은 위치에 도달하면 노드를 추가.

삽입 예제 코드 (C언어):

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

Node* insert(Node* root, int data) {
    if (root == NULL)
        return createNode(data);  // 새 노드 생성

    if (data < root->data)
        root->left = insert(root->left, data);  // 왼쪽 서브트리로 이동
    else if (data > root->data)
        root->right = insert(root->right, data);  // 오른쪽 서브트리로 이동

    return root;
}

 

---

3) 삭제(Deletion)

트리에서 값을 삭제하는 과정입니다. 삭제하려는 노드의 자식 노드 개수에 따라 다르게 처리합니다.

1. 자식이 없는 경우: 노드를 그냥 삭제합니다.
2. 자식이 하나인 경우: 해당 노드를 삭제하고, 자식을 부모 노드에 연결합니다.
3. 자식이 두 개인 경우: 오른쪽 서브트리에서 가장 작은 값을 가진 노드로 대체하고, 해당 노드를 삭제합니다.

삭제 예제 코드 (C언어):

Node* findMin(Node* root) {
    while (root->left != NULL)
        root = root->left;  // 최솟값 노드 탐색
    return root;
}

Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;

    if (key < root->data)
        root->left = deleteNode(root->left, key);  // 왼쪽 서브트리에서 삭제
    else if (key > root->data)
        root->right = deleteNode(root->right, key);  // 오른쪽 서브트리에서 삭제
    else {
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        Node* temp = findMin(root->right);
        root->data = temp->data;  // 최솟값 노드로 대체
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

 

---

3. 이진 검색 트리의 시간 복잡도

연산 평균 시간 복잡도 최악 시간 복잡도 (편향 트리)

탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)

 

---

4. 생성, 삽입, 삭제, 출력 전체 코드

 

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

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 노드 생성 함수
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 탐색 함수
Node* search(Node* root, int key) {
    if (root == NULL || root->data == key)
        return root;

    if (key < root->data)
        return search(root->left, key);

    return search(root->right, key);
}

// 삽입 함수
Node* insert(Node* root, int data) {
    if (root == NULL)
        return createNode(data);

    if (data < root->data)
        root->left = insert(root->left, data);
    else if (data > root->data)
        root->right = insert(root->right, data);

    return root;
}

// 최소값 찾기 함수 (삭제에 사용)
Node* findMin(Node* root) {
    while (root->left != NULL)
        root = root->left;
    return root;
}

// 삭제 함수
Node* deleteNode(Node* root, int key) {
    if (root == NULL) return root;

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

        Node* temp = findMin(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

// 중위 순회 함수
void inorderTraversal(Node* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}

// 메인 함수
int main() {
    Node* root = NULL;

    // 삽입 연산 테스트
    int values[] = {50, 30, 20, 40, 70, 60, 80};
    for (int i = 0; i < 7; i++) {
        root = insert(root, values[i]);
    }

    // 삽입 후 출력
    printf("삽입 후 중위 순회 결과: ");
    inorderTraversal(root);
    printf("\n");

    // 검색 연산 테스트
    Node* searchResult = search(root, 40);
    if (searchResult != NULL)
        printf("검색 결과 (40): 찾음\n");
    else
        printf("검색 결과 (40): 찾지 못함\n");

    // 삭제 연산 테스트
    root = deleteNode(root, 50);
    printf("50 삭제 후 중위 순회 결과: ");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

 

---

5. 이진 검색 트리의 장단점

장점:

• 탐색, 삽입, 삭제가 평균적으로 빠릅니다.
• 중위 순회를 통해 데이터를 정렬된 순서로 출력할 수 있습니다.

단점:

• 트리가 편향되면 시간 복잡도가 O(n)으로 증가합니다.
• 균형을 유지하기 위해 AVL 트리나 레드-블랙 트리 같은 균형 트리가 필요할 수 있습니다.

 

---

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.