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

이진탐색트리란?

이진탐색트리는 이진트리의 한 형태로, 특정 규칙을 따르는 노드들로 이루어진 트리이다. 각 노드에는 값이 저장되고, 다음과 같은 속성을 가진다.

각 노드에 중복되지 않는 키(key)가 있다. 
왼쪽 서브트리의 모든 노드는 루트 노드보다 작은 값을 가진다.
오른쪽 서브트리의 모든 노드는 루트 노드보다 큰 값을 가진다. 
좌우 서브 트리도 모두 이진 탐색 트리(자식 노드가 최대 2개인 트리)여야 한다.

 

이 속성 덕분에 효율적인 탐색, 삽입, 삭제 연산이 가능하다.

 

주요 연산

1. 탐색(Search): 원하는 값을 찾을 때, 루트 노드에서 시작하여 값을 비교하며 왼쪽 또는 오른쪽으로 이동한다. 탐색의 시간 복잡도는 트리의 높이에 따라 O(h)가 된다. 
2. 삽입(Insertion): 새로운 노드를 삽입할 때도 루트부터 시작하여 적절한 위치를 찾아 삽입한다. 
3. 삭제(Deletion): 자식이 없는 노드 삭제, 자식이 하나인 노드 삭제, 자식이 두 개인 노트 삭제 이 새 가지 경우를 처리해야 한다. 

class Node {
    int key;
    Node left, right;

    public Node(int item) {
        key = item;
        left = right = null;
    }
}

class BinarySearchTree {
    Node root;

    BinarySearchTree() {
        root = null;
    }

    // 노드 삽입
    void insert(int key) {
        root = insertRec(root, key);
    }

    // 재귀적으로 삽입하는 메서드
    Node insertRec(Node root, int key) {
        // 빈 트리일 경우 새로운 노드 반환
        if (root == null) {
            root = new Node(key);
            return root;
        }

        // 키를 비교하여 왼쪽 또는 오른쪽에 삽입
        if (key < root.key) {
            root.left = insertRec(root.left, key);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key);
        }

        return root;
    }

    // 값 탐색
    boolean search(int key) {
        return searchRec(root, key) != null;
    }

    // 재귀적으로 탐색하는 메서드
    Node searchRec(Node root, int key) {
        // 노드를 찾거나 트리 끝에 도달하면 반환
        if (root == null || root.key == key) {
            return root;
        }

        // 찾고자 하는 값이 루트보다 작으면 왼쪽 서브트리 탐색
        if (key < root.key) {
            return searchRec(root.left, key);
        }

        // 찾고자 하는 값이 루트보다 크면 오른쪽 서브트리 탐색
        return searchRec(root.right, key);
    }

    // 중위 순회 (Inorder traversal)
    void inorder() {
        inorderRec(root);
    }

    // 재귀적으로 중위 순회하는 메서드
    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.print(root.key + " ");
            inorderRec(root.right);
        }
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        // 값 삽입
        bst.insert(50);
        bst.insert(30);
        bst.insert(20);
        bst.insert(40);
        bst.insert(70);
        bst.insert(60);
        bst.insert(80);

        // 중위 순회 출력
        System.out.println("중위 순회 결과:");
        bst.inorder(); // 20 30 40 50 60 70 80 출력

        // 값 탐색
        System.out.println("\n70이 존재하나요? " + bst.search(70)); // true
        System.out.println("25가 존재하나요? " + bst.search(25)); // false
    }
}

 

근데 굳이 이렇게 구현해서 사용할 필요는 없다. 자바에서는 효율적인 자료구조가 라이브러리 형태로 구현되어 있어서 가져다가 쓰면 된다. 직접 구현하는 이유는 자료구조의 동작 원리를 이해하고, 자료구조를 커스텀해서 쓰기 위함이다. 

 

자바에서 이미 제공되는 자료구조 (java.util)

다음 자료구조는 레드-블랙 트리라는 자가 균형 이진탐색트리로 구현되어 있다. 

1. TreeSet: 중복을 허용하지 않으며, 자동으로 정렬된 데이터를 유지한다. 

2. TreeMap: 키-값 쌍을 저장하고, 키를 기준으로 자동으로 정렬된 트리를 유지한다. 

 

💡 갑자기 궁금!
TreeMap과 HashMap은 뭐가 다를까?
- 자료 구조:
HashMap은 해시 테이블을 기반으로 동작
TreeMap은 레드-블랙 트리라는 자가 균형 이진탐색트리를 사용
- 정렬 여부:
HashMap은 순서를 보장하지 않으며, 키의 삽입 순서나 크기와는 무관하게 저장
TreeMap은 키가 정렬된 상태로 저장되며, 키가 자동으로 오름차순으로 정렬
- 시간 복잡도:
HashMap: 평균적으로 삽입, 삭제, 탐색 모두 O(1).
TreeMap: 삽입, 삭제, 탐색이 O(log n).