이진 탐색 트리

/* ── BST 노드 ───────────────────────────────────────────── */
public class BSTNode {
    int val;
    BSTNode left, right;
    BSTNode(int val) { this.val = val; }
}

/* ── 삽입: 루트부터 비교하며 null 위치를 찾아 삽입 ─────── */
public BSTNode insert(BSTNode root, int val) {
    if (root == null) return new BSTNode(val); // 삽입 위치
    if (val < root.val)
        root.left  = insert(root.left,  val);    // 왼쪽으로
    else if (val > root.val)
        root.right = insert(root.right, val);    // 오른쪽으로
    return root;                                   // 이미 존재하면 무시
}

/* ── 탐색 ────────────────────────────────────────────────── */
public boolean search(BSTNode root, int val) {
    if (root == null) return false;  // 탐색 실패
    if (val == root.val) return true; // 탐색 성공
    return val < root.val
        ? search(root.left,  val)
        : search(root.right, val);
}

public BSTNode delete(BSTNode root, int val) {
    if (root == null) return null;  // 값이 없음

    if (val < root.val) {
        root.left  = delete(root.left,  val); // 왼쪽 서브트리에서 삭제
    } else if (val > root.val) {
        root.right = delete(root.right, val); // 오른쪽 서브트리에서 삭제
    } else {
        // 삭제 대상 발견
        if (root.left  == null) return root.right; // Case 1,2: 왼쪽 없음
        if (root.right == null) return root.left;  // Case 2: 오른쪽 없음

        // Case 3: 자식 2개 → 중위 후계자(오른쪽 서브트리의 최솟값)로 대체
        BSTNode successor = findMin(root.right);
        root.val   = successor.val;                       // 값만 교체
        root.right = delete(root.right, successor.val); // 후계자 제거
    }
    return root;
}

private BSTNode findMin(BSTNode node) {
    while (node.left != null) node = node.left; // 가장 왼쪽 = 최솟값
    return node;
}

/* ── TreeMap: Red-Black Tree 기반 BST — 항상 O(log n) 보장 */
TreeMap<Integer, String> map = new TreeMap<>();

map.put(50, "root");
map.put(30, "left");
map.put(70, "right");

// 정렬 순서 보장
map.firstKey();          // 30  — 최솟값 O(log n)
map.lastKey();           // 70  — 최댓값 O(log n)

// 범위 탐색: 30 이상 70 미만 키를 정렬 순서로
map.subMap(30, 70).forEach((k, v) ->
    System.out.println(k + " → " + v)
);

// 50보다 작은 가장 큰 키 (전임자)
map.lowerKey(50);        // 30

// 50보다 크거나 같은 가장 작은 키 (후임자)
map.ceilingKey(50);     // 50

/* ── HashMap vs TreeMap 비교 ─────────────────────────────── */
// HashMap : 평균 O(1) 탐색/삽입, 순서 없음
// TreeMap : O(log n) 탐색/삽입, 정렬 순서 보장, 범위 탐색 지원