이진 검색 트리의 기본 개념

이진 검색 트리(Binary Search Tree, BST)는 데이터의 빠른 탐색을 위해 설계된 계층형 자료구조입니다. 원본 글에서는 이를 'B-tree'로 지칭했으나, 설명된 특성(최대 2개의 자식 노드, 좌우 크기 규칙)은 정확히 이진 검색 트리의 정의에 부합합니다. BST는 다음과 같은 핵심적인 제약 조건을 가집니다.

• 각 노드는 최대 두 개의 자식(Left, Right)을 가질 수 있습니다.
• 모든 노드는 고유한 키(Key)와 데이터 값(Value)을 저장합니다.
• 왼쪽 서브트리에 속한 모든 노드의 키는 부모 노드의 키보다 작아야 합니다.
• 오른쪽 서브트리에 속한 모든 노드의 키는 부모 노드의 키보다 커야 합니다.

탐색 메커니즘과 성능

데이터를 찾을 때는 루트 노드부터 시작합니다. 타겟 키가 현재 노드의 키와 동일하면 탐색을 종료합니다. 타겟 키가 더 작다면 왼쪽 자식 노드로, 크다면 오른쪽 자식 노드로 이동하며 이 과정을 반복합니다. 만약 더 이상 이동할 자식 노드가 없다면 해당 데이터가 존재하지 않음을 의미합니다.

트리의 좌우 높이가 균형을 이루고 있을 경우, 탐색 시간 복잡도는 배열의 이진 탐색과 동일한 O(log N)에 수렴합니다. 연속된 메모리 공간을 사용하는 배열과 달리, 트리 구조는 노드 삽입 및 삭제 시 포인터 변경만으로 구조를 재구성할 수 있어 대규모 데이터 이동에 따른 오버헤드가 없습니다.

균형 문제 (Balancing)

정렬된 순서대로 데이터를 반복해서 삽입하거나 삭제할 경우, 트리는 한쪽으로 치우친 비대칭 구조(예: 연결 리스트 형태)로 퇴화할 수 있습니다. 이 경우 탐색 성능은 O(N)으로 저하됩니다. 이러한 최악의 상황을 방지하기 위해 삽입/삭제 시 자동으로 트리의 높이를 조절하는 '균형 이진 검색 트리(AVL 트리, Red-Black 트리 등)'가 실제 프로덕션 환경에서 주로 사용됩니다.

Java를 활용한 이진 검색 트리 구현

아래는 재귀 방식 대신 반복문을 활용하여 스택 오버플로우 위험을 줄이고, 중위 순회(In-order Traversal)를 지원하는 커스텀 이터레이터를 포함한 이진 검색 트리의 구현 코드입니다. 기존 코드의 구조와 변수명을 개선하여 가독성과 안정성을 높였습니다.

1. 노드 클래스 정의

package com.datastructure.tree;

public class Node<K, V> {
    K key;
    V value;
    Node<K, V> parent;
    Node<K, V> left;
    Node<K, V> right;

    public Node(K key, V value, Node<K, V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
    
    public K getKey() { return key; }
    public V getValue() { return value; }
}

2. 이진 검색 트리 맵 구현

package com.datastructure.tree;

import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

public class BinarySearchTreeMap<K, V> implements Iterable<Node<K, V>> {
    
    private Node<K, V> root;
    private final Comparator<? super K> comparator;

    public BinarySearchTreeMap() {
        this.comparator = null;
    }

    public BinarySearchTreeMap(Comparator<? super K> comparator) {
        this.comparator = comparator;
    }

    @SuppressWarnings("unchecked")
    private int compareKeys(K k1, K k2) {
        if (comparator != null) {
            return comparator.compare(k1, k2);
        }
        return ((Comparable<? super K>) k1).compareTo(k2);
    }

    public void put(K key, V value) {
        if (root == null) {
            root = new Node<>(key, value, null);
            return;
        }

        Node<K, V> current = root;
        while (true) {
            int cmp = compareKeys(key, current.key);
            if (cmp < 0) {
                if (current.left == null) {
                    current.left = new Node<>(key, value, current);
                    break;
                }
                current = current.left;
            } else if (cmp > 0) {
                if (current.right == null) {
                    current.right = new Node<>(key, value, current);
                    break;
                }
                current = current.right;
            } else {
                current.value = value; // 키가 동일하면 값 업데이트
                break;
            }
        }
    }

    public V get(K key) {
        Node<K, V> current = root;
        while (current != null) {
            int cmp = compareKeys(key, current.key);
            if (cmp < 0) {
                current = current.left;
            } else if (cmp > 0) {
                current = current.right;
            } else {
                return current.value;
            }
        }
        return null;
    }

    @Override
    public Iterator<Node<K, V>> iterator() {
        return new InOrderIterator();
    }

    private class InOrderIterator implements Iterator<Node<K, V>> {
        private Node<K, V> nextNode;

        public InOrderIterator() {
            nextNode = findMinNode(root);
        }

        private Node<K, V> findMinNode(Node<K, V> node) {
            if (node == null) return null;
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }

        @Override
        public boolean hasNext() {
            return nextNode != null;
        }

        @Override
        public Node<K, V> next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }
            Node<K, V> result = nextNode;
            nextNode = findSuccessor(result);
            return result;
        }

        private Node<K, V> findSuccessor(Node<K, V> node) {
            if (node.right != null) {
                return findMinNode(node.right);
            }
            Node<K, V> parent = node.parent;
            while (parent != null && node == parent.right) {
                node = parent;
                parent = parent.parent;
            }
            return parent;
        }
    }
}

3. 실행 및 테스트

package com.datastructure.tree;

public class Main {
    public static void main(String[] args) {
        BinarySearchTreeMap<Integer, String> bstMap = new BinarySearchTreeMap<>();
        
        // 데이터 삽입
        bstMap.put(6, "Node-6");
        bstMap.put(4, "Node-4");
        bstMap.put(9, "Node-9");
        bstMap.put(2, "Node-2");
        bstMap.put(7, "Node-7");
        bstMap.put(10, "Node-10");
        bstMap.put(5, "Node-5");
        bstMap.put(4, "Node-4-Updated"); // 기존 키 값 업데이트

        // 특정 키 검색 테스트
        System.out.println("Search Key 6: " + bstMap.get(6));
        System.out.println("Search Key 4: " + bstMap.get(4));
        System.out.println("Search Key 99: " + bstMap.get(99));

        // 이터레이터를 활용한 중위 순회 (오름차순 정렬 출력)
        System.out.println("\nIn-order Traversal using Iterator:");
        for (Node<Integer, String> node : bstMap) {
            System.out.println("Key: " + node.getKey() + ", Value: " + node.getValue());
        }
    }
}