검색 vs 우선순위 처리, 이진 탐색 트리와 이진 힙의 모든 것 - 코드카인 티스토리

안녕하세요 😊 코드카인 여러분!

오늘은 두 가지 유명한 자료구조, 이진 탐색 트리(Binary Search Tree, BST)와 이진 힙(Binary Heap)에 대해 이야기해 보려고 해요. 이 둘은 이름부터 비슷하지만, 동작 방식, 목적, 그리고 사용되는 곳이 완전히 다릅니다. 자, 두 자료구조를 일상생활에 빗대어 쉽게 설명해 드릴게요! 😊

---

🎯 이진 탐색 트리: 정리 정돈된 도서관

이진 탐색 트리를 떠올리면 정리된 도서관을 상상하면 됩니다.
책이 제목 순서대로 완벽히 정렬되어 있어서 찾고 싶은 책을 쉽게 찾을 수 있어요.

특징

1. 정렬된 구조 :
   • 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큽니다.
   • 항상 오름차순 또는 내림차순으로 정렬된 상태를 유지해요.
2. 효율적인 탐색 :
   • 필요한 값을 찾기 위해 절반씩 나누며 검색합니다.
   • 탐색 시간 복잡도: O(log n) (균형이 잡혀 있을 때)

장점과 단점

장점	단점
DATA가 정렬된 상태로 저장됨	트리가 한쪽으로 치우치면 성능이 떨어짐 (O(n))
탐색, 삽입, 삭제가 효율적	균형을 맞추는 추가 작업 필요 (AVL, Red-Black Tree)

사용 사례

• DATA 검색 (ex. 전화번호부)
• 정렬된 DATA 유지가 필요한 경우
• DATA베이스의 인덱스

---

🎯 이진 힙: 바쁜 음식 배달 서비스

이진 힙은 바쁜 배달 시스템 같아요.
주문이 많아도, 가장 중요한(최대값/최소값) 주문부터 신속하게 처리해야 하죠.

특징

1. 최대/최소 우선 순위 유지 :
   • 최대 힙(Max-Heap): 부모가 자식보다 크거나 같다.
   • 최소 힙(Min-Heap): 부모가 자식보다 작거나 같다.
2. 완전 이진 트리 구조 :
   • 모든 노드가 위에서 아래로, 왼쪽에서 오른쪽으로 채워집니다.

장점과 단점

장점	단점
우선 순위가 가장 높은 요소를 빠르게 찾음	특정 값을 탐색하려면 시간이 오래 걸림 (O(n))
삽입, 삭제가 효율적 (O(log n))	정렬된 DATA를 직접적으로 유지하지 않음

사용 사례

• 우선순위 큐 (Priority Queue)
• 작업 스케줄링 (ex. CPU 스케줄링)
• DATA 흐름 제어 (ex. 네트워크 라우팅)

---

🆚 이진 탐색 트리 vs 이진 힙

기준	이진 탐색 트리 (BST)	이진 힙 (Binary Heap)
용도	빠른 검색과 정렬	빠른 삽입/삭제 및 최대/최소값 관리
구조	왼쪽 < 부모 < 오른쪽	부모 >= 자식 (최대 힙) / 부모 <= 자식 (최소 힙)
탐색 속도	O(log n) (균형 트리일 때)	O(n)
삽입/삭제 속도	O(log n)	O(log n)
정렬된 DATA	항상 유지됨	유지되지 않음

---

📂 실전 코드 예제

이진 탐색 트리

class Node {
    int value;
    Node left, right;

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

class BinarySearchTree {
    Node root;

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

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

    void inorder() {
        inorderRec(root);
    }

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

이진 힙

import java.util.PriorityQueue;

class BinaryHeap {
    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        minHeap.add(10);
        minHeap.add(5);
        minHeap.add(20);

        while (!minHeap.isEmpty()) {
            System.out.println(minHeap.poll());
        }
    }
}

---

😊 마무리하며..

이진 탐색 트리와 이진 힙, 둘 다 개발자라면 반드시 이해해야 할 자료구조입니다.
각각의 장단점을 이해하고 상황에 맞게 선택한다면 훨씬 효율적인 코드와 설계를 할 수 있어요.
공부하는 과정에서 헷갈릴 수 있지만, 차근차근 따라가다 보면 자연스럽게 익숙해질 거예요! 😊