17강. 이진 탐색 트리: 삽입·검색·삭제의 원리

?1. 이번 강의에서 해결할 문제

정렬된 순서를 유지하면서 점수를 계속 추가하고 찾고 싶지만 배열 중간 삽입은 원소 이동이 필요합니다.

✓2. 학습 목표

✓이 강의를 마치면

• BST의 순서 불변식을 설명합니다.
• 삽입·검색과 삭제의 세 경우를 구분합니다.
• 평균 O(log n)과 편향 시 O(n)을 비교합니다.

◇3. 핵심 개념

이진 탐색 트리(BST)는 각 노드보다 작은 키를 왼쪽, 큰 키를 오른쪽에 둡니다. 중복 정책은 개수 저장, 한쪽 배치, 거부 중 하나를 명시해야 합니다. 삭제는 리프, 자식 하나, 자식 둘의 경우로 나뉘며 자식 둘이면 오른쪽 하위 트리의 최솟값 같은 후계자로 대체합니다. 이 구조 자체는 균형을 보장하지 않습니다.

✎4. 단계별 실습

1. 예제 파일 작성

실행 환경: 코드 편집기

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: 같은 이름의 파일이 있다면 덮어쓰기 전에 Git diff로 변경 범위를 확인합니다. 선택한 LTS JDK의 java -version과 javac -version이 모두 실행되어야 합니다.

대상 파일: src/ScoreSearchTree.java

src/ScoreSearchTree.java

public class ScoreSearchTree {
    static final class Node {
        int score, count = 1;
        Node left, right;
        Node(int score) { this.score = score; }
    }
    private Node root;

    void add(int score) { root = add(root, score); }
    Node add(Node node, int score) {
        if (node == null) return new Node(score);
        if (score < node.score) node.left = add(node.left, score);
        else if (score > node.score) node.right = add(node.right, score);
        else node.count++;
        return node;
    }
    int count(int score) {
        Node node = root;
        while (node != null) {
            if (score == node.score) return node.count;
            node = score < node.score ? node.left : node.right;
        }
        return 0;
    }

    void remove(int score) { root = remove(root, score); }
    Node remove(Node node, int score) {
        if (node == null) return null;
        if (score < node.score) node.left = remove(node.left, score);
        else if (score > node.score) node.right = remove(node.right, score);
        else if (node.count > 1) node.count--;
        else if (node.left == null) return node.right;
        else if (node.right == null) return node.left;
        else {
            Node successor = min(node.right);
            node.score = successor.score;
            node.count = successor.count;
            node.right = removeAll(node.right, successor.score);
        }
        return node;
    }
    Node removeAll(Node node, int score) {
        if (score < node.score) node.left = removeAll(node.left, score);
        else if (score > node.score) node.right = removeAll(node.right, score);
        else return node.right;
        return node;
    }
    Node min(Node node) {
        while (node.left != null) node = node.left;
        return node;
    }

    public static void main(String[] args) {
        ScoreSearchTree tree = new ScoreSearchTree();
        for (int score : new int[]{1000, 700, 1300, 1000}) tree.add(score);
        System.out.println("1000점 개수: " + tree.count(1000));
        tree.remove(1000);
        tree.remove(700);
        System.out.println("삭제 후 1000점 개수: " + tree.count(1000));
        System.out.println("삭제 후 700점 개수: " + tree.count(700));
        System.out.println("900점 개수: " + tree.count(900));
    }
}

2. PowerShell에서 컴파일·실행

실행 환경: Windows PowerShell

실행 위치: C:\dev\game-ranking-algorithms

실행 전 확인: src/ScoreSearchTree.java가 저장되었고 out 폴더에는 삭제해도 되는 컴파일 결과만 있는지 확인합니다.

대상: src/ScoreSearchTree.java와 out 아래 생성되는 class 파일

Windows PowerShell

Set-Location C:\dev\game-ranking-algorithms
New-Item -ItemType Directory -Force .\out | Out-Null
javac -Xlint:all -d .\out .\src\ScoreSearchTree.java
java -cp .\out ScoreSearchTree

예상 결과: 1000점 개수는 2에서 한 번 삭제 후 1이 되고, 삭제한 700점과 존재하지 않는 900점 개수는 0이 출력됩니다.

실행 시간은 PC의 CPU·메모리, JDK 버전, JVM 워밍업, 백그라운드 작업과 입력 분포에 따라 달라질 수 있습니다. 측정값은 같은 조건에서 여러 번 비교하고 Big-O 분석과 함께 해석합니다.

→5. 코드와 알고리즘이 동작하는 이유

비교할 때마다 왼쪽 또는 오른쪽 하위 트리 하나만 선택합니다. 삭제는 중복 개수를 줄이거나 자식 0·1개를 바로 연결하고, 자식 둘이면 오른쪽의 최소 후계자와 그 중복 개수를 옮겨 순서 불변식을 지킵니다. 높이 h에 대해 삽입·검색·삭제는 O(h)입니다. 균형에 가까우면 평균 O(log n)이지만 정렬 순서로 삽입해 편향되면 최악 O(n)입니다. 노드는 O(n) 공간을 사용합니다.

!6. 자주 하는 실수와 해결법

!자주 하는 실수

• 실수: BST가 자동으로 균형이라고 생각하기 해결: 기본 BST와 AVL·Red-Black 같은 균형 트리를 구분합니다.
• 실수: 중복 키 정책 없이 한쪽에 계속 넣기 해결: 개수 저장 등 도메인 규칙을 명시합니다.
• 실수: 삭제의 자식 둘 경우를 단순 연결로 처리하기 해결: 후계자 또는 전임자로 순서 불변식을 유지합니다.

✎7. 직접 실습

✎직접 실습

1. 최댓값 조회를 구현합니다.
2. 루트가 자식 둘인 경우를 삭제하고 중위 순서가 유지되는지 확인합니다.
3. 오름차순 입력과 섞인 입력의 높이를 비교합니다.

실습 기록에는 입력 크기, 예상 결과, 실제 결과, 시간·공간 복잡도와 사용한 JDK 버전을 함께 남깁니다. 실제 사용자 ID나 개인정보 대신 P1, P2 같은 가상 데이터를 사용합니다.

?8. 이해 점검 질문 3개

?이해 점검

1. BST의 순서 불변식은 무엇인가요?
2. 검색 복잡도가 O(h)로 표현되는 이유는 무엇인가요?
3. 자식 둘인 노드를 삭제할 때 필요한 대체 값은 무엇인가요?

■9. 핵심 요약

■핵심 요약

BST는 순서 불변식으로 탐색 범위를 줄이지만 성능은 높이에 달려 있습니다. 중복·삭제 정책과 균형 여부를 명시해야 합니다.