트리(2) - 이진 탐색 트리(Binary Search Tree)의 원리, 구조, 예제 코드(C언어, Java, Python), 장단점, 사용 사례 총정리

이진탐색트리

 

 

이진 탐색 트리(Binary Search Tree, BST)는 프로그래밍에서 가장 중요한 자료구조 중 하나입니다. 효율적인 데이터 검색, 삽입, 삭제를 가능하게 하며 다양한 알고리즘과 시스템에서 사용됩니다. 

---

(1) 이진 탐색 트리란?

이진 탐색 트리는 **이진 트리(Binary Tree)**의 한 종류로, 데이터를 정렬된 상태로 저장하며 효율적인 검색과 관리가 가능하도록 설계된 자료구조입니다.

 

 

(2) 기본 원리

• 각 노드는 최대 두 개의 자식을 가집니다.
• 왼쪽 서브트리에는 부모 노드보다 작거나 같은 값이 저장됩니다.
• 오른쪽 서브트리에는 부모 노드보다 큰 값이 저장됩니다.

 

(3) 이진 탐색 트리의 특징

1. 정렬된 데이터 구조: 노드를 중위 순회(Inorder Traversal)하면 정렬된 데이터가 출력됩니다.
2. 효율적인 연산: 검색, 삽입, 삭제가 트리 높이에 비례하는 시간 복잡도 O(log n)로 동작합니다.

---

 

(4) 이진 탐색 트리의 구조와 동작

반응형

삽입(Insert)

새로운 데이터를 추가할 때, 부모 노드와 값을 비교하며 적절한 위치를 찾아 삽입합니다. 삽입 후 항상 "부모노드보다 작거나 같은 자식 노드는 부모노드 왼쪽에 존재"하고, "부모노드보다 큰 자식 노드는 부모노드 오른쪽에 존재"한다는 규칙을 항상 만족합니다.

 

검색(Search)

특정 데이터를 찾기 위해 루트에서 시작하여 값을 비교하며 트리를 내려갑니다. 현재 노드보다 찾는 값이 작은경우 왼쪽으로, 현재 노드보다 찾는 값이 큰 경우 오른쪽으로 내려갑니다. 

삭제(Delete)

노드를 삭제할 때, 다음 세 가지 경우를 고려합니다:

1. 자식이 없는 노드: 단순히 제거.
2. 자식이 하나인 노드: 자식을 부모와 연결.
3. 자식이 둘인 노드: 오른쪽 서브트리의 최소값을 찾아 교체 후 삭제.

---

 

(5) 이진 탐색 트리 구현 예제 코드

C 언어

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

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

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

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

void inorder(struct Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);

    printf("Inorder Traversal: ");
    inorder(root);
    return 0;
}

---

Java

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BST {
    Node root;

    BST() {
        root = null;
    }

    void insert(int data) {
        root = insertRec(root, data);
    }

    Node insertRec(Node root, int data) {
        if (root == null) {
            root = new Node(data);
            return root;
        }
        if (data < root.data)
            root.left = insertRec(root.left, data);
        else if (data > root.data)
            root.right = insertRec(root.right, data);
        return root;
    }

    void inorder() {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.data + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BST tree = new BST();
        tree.insert(50);
        tree.insert(30);
        tree.insert(70);
        tree.insert(20);
        tree.insert(40);

        System.out.print("Inorder Traversal: ");
        tree.inorder();
    }
}

---

Python

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, root, data):
        if root is None:
            return Node(data)
        if data < root.data:
            root.left = self.insert(root.left, data)
        else:
            root.right = self.insert(root.right, data)
        return root

    def inorder(self, root):
        if root:
            self.inorder(root.left)
            print(root.data, end=" ")
            self.inorder(root.right)

# Usage
bst = BST()
root = None
root = bst.insert(root, 50)
bst.insert(root, 30)
bst.insert(root, 70)
bst.insert(root, 20)
bst.insert(root, 40)

print("Inorder Traversal:", end=" ")
bst.inorder(root)

---

 

4. 이진 탐색 트리의 장단점

장점

1. 빠른 탐색: 평균 시간 복잡도 O(log n).
2. 정렬 유지: 삽입 순서와 관계없이 정렬된 데이터 관리.
3. 다양한 확장성: AVL, Red-Black Tree로 개선 가능.

단점

1. 불균형 문제: 한쪽으로 치우친 트리는 O(n) 시간 복잡도를 가짐.
2. 추가 메모리 사용: 포인터와 링크 관리 필요.

---

 

5. 이진 탐색 트리의 사용 사례

1. 데이터베이스 인덱싱: 효율적인 검색과 정렬.
2. 검색 알고리즘: 주어진 값의 존재 여부를 빠르게 확인.
3. 네트워크 라우팅: IP 주소 관리와 검색.
4. 문자열 자동 완성: 텍스트 예측 및 검색.
5. 운영체제 프로세스 관리: 프로세스 우선순위 트리 관리.

 

2024.12.18 - [자료구조] - 트리 (1) - 이진 트리(Binary Tree)의 모든 것: 원리, 구조, 예제 코드(C언어 Java, Python), 장단점, 사용 사례

트리 (1) - 이진 트리(Binary Tree)의 모든 것: 원리, 구조, 예제 코드(C언어 Java, Python), 장단점, 사용

 

2024.12.18 - [자료구조] - 트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함)

트리(3) - 문자열 검색 문제에 최적화된 트라이(Trie) 자료구조(C언어, Java, Python 예시코드 포함)