BST 삽입, 삭제, 탐색의 핵심 규칙

BST(이진 탐색 트리)는 왼쪽 < 현재 < 오른쪽 규칙을 지키는 트리입니다. 삽입과 탐색은 비교적 쉽지만 삭제, 특히 2자식 삭제에서 실수가 많이 납니다. 그래서 연산을 따로 외우기보다 불변식 하나를 끝까지 지키는 습관이 중요합니다.

아래에서는 삽입/탐색/삭제를 각각 따로 보지 않고 하나의 규칙으로 연결해 설명합니다. 삭제 후 중위 순회 결과가 오름차순인지 확인하면 구현이 맞는지 바로 검증할 수 있습니다. 코드는 복잡한 최적화보다 0/1/2 자식 분기를 명확히 드러내는 방식으로 구성했습니다.

핵심 원리 정돈

BST는 세 가지 규칙만 명확히 잡으면 구현 난도가 크게 내려갑니다. 삭제 코드를 보기 전에 0/1/2 자식 분기를 표로 우선 적어 두세요.

BST 불변식은 왼쪽 서브트리는 작고 오른쪽 서브트리는 크다는 순서 약속입니다. 정확히는 모든 노드에서 left subtree < node < right subtree 관계가 성립해야 합니다. 루트가 8이면 왼쪽에는 8보다 작은 값, 오른쪽에는 8보다 큰 값만 배치됩니다.

삽입/탐색 규칙은 비교 결과에 따라 한 경로를 내려가는 절차입니다. 각 노드에서 키를 비교해 작으면 왼쪽, 크면 오른쪽으로 이동하는 단일 경로 탐색입니다. 값 6을 찾을 때 8보다 작아 왼쪽으로 가고, 3보다 크면 다시 오른쪽으로 이동합니다.

삭제 분기는 대상 노드 자식 수(0/1/2)에 따라 처리 규칙이 달라집니다. 리프 제거, 단일 자식 승격, 두 자식이면 후속자(또는 선행자) 치환으로 나뉩니다. 두 자식 노드는 오른쪽 서브트리 최소값으로 값을 바꾼 뒤 그 최소 노드를 삭제하면 불변식을 유지할 수 있습니다.

BST 연산이 운영 지연에 미치는 영향

BST는 구현 난이도 대비 활용도가 높습니다.
하지만 삭제를 잘못 구현하면 트리 모양은 유지돼도 정렬 성질이 깨질 수 있습니다.

또한 입력 분포가 편향되면 성능이 급격히 악화됩니다.
따라서 연산 정확성과 성능 안정성을 함께 고려해야 합니다.

BST 불변식 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

BST 기본 연산을 작은 트리로 따라가며, 자주 나오는 오답 패턴을 함께 점검합니다.

초기 입력: 8, 3, 10, 1, 6
삭제 대상: 3 (자식 2개)

오답: 3을 후속자 6으로 값만 치환하고, 원래 6 노드 삭제를 생략합니다.
디버깅: 중위 순회 결과가 1, 6, 6, 8, 10처럼 중복되어 데이터 무결성이 깨졌는지 확인합니다.
교정: 치환 후 후속자 키를 대상으로 오른쪽 서브트리에서 삭제를 한 번 더 수행합니다.
검증: 중위 순회가 1, 6, 8, 10처럼 오름차순 + 중복 없음인지 확인합니다.

BST: 삽입과 탐색

문제 의도: BST의 삽입/탐색 규칙을 코드로 고정하고 기본 동작을 확인합니다.
입력 예시: 8,3,10,1,6,14,4,7,13 삽입 후 6, 99 검색
출력 예시: true, false if val < node.val면 왼쪽, 아니면 오른쪽으로 내려가는 비교 규칙이 BST의 핵심입니다.

main.cpp

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    explicit Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* node, int val) {
    if (!node) return new Node(val);
    if (val < node->val) node->left = insert(node->left, val);
    else if (val > node->val) node->right = insert(node->right, val);
    return node;
}

bool search(Node* node, int val) {
    Node* cur = node;
    while (cur) {
        if (val == cur->val) return true;
        if (val < cur->val) cur = cur->left;
        else cur = cur->right;
    }
    return false;
}

int main() {
    Node* root = nullptr;
    for (int x : {8, 3, 10, 1, 6, 14, 4, 7, 13}) root = insert(root, x);
    cout << boolalpha << search(root, 6) << "\n";
    cout << boolalpha << search(root, 99) << "\n";
    return 0;
}

Main.java

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    static Node insert(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }

    static boolean search(Node node, int val) {
        Node cur = node;
        while (cur != null) {
            if (val == cur.val) return true;
            if (val < cur.val) cur = cur.left;
            else cur = cur.right;
        }
        return false;
    }

    public static void main(String[] args) {
        Node root = null;
        int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        for (int x : arr) root = insert(root, x);
        System.out.println(search(root, 6));
        System.out.println(search(root, 99));
    }
}

main.py

class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(node, val):
    if node is None:
        return Node(val)

    if val < node.val:
        node.left = insert(node.left, val)
    elif val > node.val:
        node.right = insert(node.right, val)
    return node

def search(node, val):
    cur = node
    while cur:
        if val == cur.val:
            return True
        if val < cur.val:
            cur = cur.left
        else:
            cur = cur.right
    return False

root = None
for x in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
    root = insert(root, x)

print(search(root, 6))   # True
print(search(root, 99))  # False

main.rs

#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }
}

fn insert(node: &mut Option<Box<Node>>, val: i32) {
    match node {
        None => *node = Some(Box::new(Node::new(val))),
        Some(n) => {
            if val < n.val {
                insert(&mut n.left, val);
            } else if val > n.val {
                insert(&mut n.right, val);
            }
        }
    }
}

fn search(node: &Option<Box<Node>>, val: i32) -> bool {
    let mut cur = node.as_deref();
    while let Some(n) = cur {
        if val == n.val {
            return true;
        }
        cur = if val < n.val {
            n.left.as_deref()
        } else {
            n.right.as_deref()
        };
    }
    false
}

fn main() {
    let mut root: Option<Box<Node>> = None;
    for x in [8, 3, 10, 1, 6, 14, 4, 7, 13] {
        insert(&mut root, x);
    }
    println!("{}", search(&root, 6));
    println!("{}", search(&root, 99));
}

동작 검토 포인트

삽입과 탐색은 같은 비교 로직을 공유합니다.
값이 작으면 왼쪽, 크면 오른쪽으로 이동한다는 규칙만 지키면 됩니다.
중복 키 정책은 문제 요구에 따라 명시적으로 정의해야 합니다.

평균 시간복잡도: O(log N)
최악 시간복잡도: O(N) (편향 트리)
공간복잡도: O(H)

BST: 삭제(0/1/2 자식 분기)

문제 의도: 자식 수에 따라 삭제 로직이 어떻게 분기되는지 확인합니다.
입력 예시: BST에서 3 삭제
출력 예시: 삭제 대상 검색 false, 대체 노드 유지 확인 true 삭제는 자식 0개/1개/2개를 먼저 나누고 처리하면 코드가 안정됩니다.

main.cpp

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    explicit Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* node, int val) {
    if (!node) return new Node(val);
    if (val < node->val) node->left = insert(node->left, val);
    else if (val > node->val) node->right = insert(node->right, val);
    return node;
}

bool search(Node* node, int val) {
    while (node) {
        if (val == node->val) return true;
        node = (val < node->val) ? node->left : node->right;
    }
    return false;
}

Node* minNode(Node* node) {
    Node* cur = node;
    while (cur->left) cur = cur->left;
    return cur;
}

Node* removeNode(Node* node, int val) {
    if (!node) return nullptr;
    if (val < node->val) node->left = removeNode(node->left, val);
    else if (val > node->val) node->right = removeNode(node->right, val);
    else {
        if (!node->left) return node->right;
        if (!node->right) return node->left;
        Node* succ = minNode(node->right);
        node->val = succ->val;
        node->right = removeNode(node->right, succ->val);
    }
    return node;
}

int main() {
    Node* root = nullptr;
    for (int x : {8, 3, 10, 1, 6, 14, 4, 7, 13}) root = insert(root, x);
    root = removeNode(root, 3);
    cout << boolalpha << search(root, 3) << "\n";
    cout << boolalpha << search(root, 4) << "\n";
    return 0;
}

Main.java

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    static Node insert(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }

    static boolean search(Node node, int val) {
        while (node != null) {
            if (val == node.val) return true;
            node = (val < node.val) ? node.left : node.right;
        }
        return false;
    }

    static Node minNode(Node node) {
        Node cur = node;
        while (cur.left != null) cur = cur.left;
        return cur;
    }

    static Node delete(Node node, int val) {
        if (node == null) return null;
        if (val < node.val) node.left = delete(node.left, val);
        else if (val > node.val) node.right = delete(node.right, val);
        else {
            if (node.left == null) return node.right;
            if (node.right == null) return node.left;
            Node succ = minNode(node.right);
            node.val = succ.val;
            node.right = delete(node.right, succ.val);
        }
        return node;
    }

    public static void main(String[] args) {
        Node root = null;
        int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        for (int x : arr) root = insert(root, x);
        root = delete(root, 3);
        System.out.println(search(root, 3));
        System.out.println(search(root, 4));
    }
}

main.py

def min_node(node):
    cur = node
    while cur.left:
        cur = cur.left
    return cur

def delete(node, val):
    if node is None:
        return None

    if val < node.val:
        node.left = delete(node.left, val)
    elif val > node.val:
        node.right = delete(node.right, val)
    else:
        # 자식 0개 또는 1개
        if node.left is None:
            return node.right
        if node.right is None:
            return node.left

        # 자식 2개: 중위 후속자 사용
        succ = min_node(node.right)
        node.val = succ.val
        node.right = delete(node.right, succ.val)

    return node

root = delete(root, 3)
print(search(root, 3))   # False
print(search(root, 4))   # True

main.rs

#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }
}

fn insert(node: &mut Option<Box<Node>>, val: i32) {
    match node {
        None => *node = Some(Box::new(Node::new(val))),
        Some(n) => {
            if val < n.val {
                insert(&mut n.left, val);
            } else if val > n.val {
                insert(&mut n.right, val);
            }
        }
    }
}

fn search(node: &Option<Box<Node>>, val: i32) -> bool {
    let mut cur = node.as_deref();
    while let Some(n) = cur {
        if val == n.val {
            return true;
        }
        cur = if val < n.val {
            n.left.as_deref()
        } else {
            n.right.as_deref()
        };
    }
    false
}

fn pop_min(node: &mut Option<Box<Node>>) -> i32 {
    if let Some(n) = node {
        if n.left.is_none() {
            let mut boxed = match node.take() {
                Some(boxed) => boxed,
                None => return -1,
            };
            let val = boxed.val;
            *node = boxed.right.take();
            return val;
        }
        return pop_min(&mut n.left);
    }
    -1
}

fn delete(node: &mut Option<Box<Node>>, val: i32) {
    if let Some(n) = node {
        if val < n.val {
            delete(&mut n.left, val);
        } else if val > n.val {
            delete(&mut n.right, val);
        } else {
            if n.left.is_none() {
                *node = n.right.take();
            } else if n.right.is_none() {
                *node = n.left.take();
            } else {
                let succ = pop_min(&mut n.right);
                n.val = succ;
            }
        }
    }
}

fn main() {
    let mut root: Option<Box<Node>> = None;
    for x in [8, 3, 10, 1, 6, 14, 4, 7, 13] {
        insert(&mut root, x);
    }
    delete(&mut root, 3);
    println!("{}", search(&root, 3));
    println!("{}", search(&root, 4));
}

삭제 분기 문제분석

삭제는 자식 수 기준 분기가 핵심입니다.
2자식 케이스에서는 오른쪽 서브트리 최소값(중위 후속자)으로 대체하면 불변식을 유지할 수 있습니다.
후속자 노드를 실제로 제거하는 호출까지 반드시 수행해야 중복 값이 남지 않습니다.

평균 시간복잡도: O(log N)
최악 시간복잡도: O(N)
공간복잡도: 재귀 기준 O(H)

BST: 중위 순회로 불변식 재확인

문제 의도: 중위 순회 결과가 정렬 상태인지로 BST 불변식 유지 여부를 검증합니다.
입력 예시: 삽입/삭제 연산 후 트리
출력 예시: 중위 순회 결과와 정렬 여부 true/false 중위 순회 결과가 오름차순이면 BST 규칙이 깨지지 않았다고 빠르게 확인할 수 있습니다.

main.cpp

#include <iostream>
#include <vector>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    explicit Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* insert(Node* node, int val) {
    if (!node) return new Node(val);
    if (val < node->val) node->left = insert(node->left, val);
    else if (val > node->val) node->right = insert(node->right, val);
    return node;
}

void inorder(Node* node, vector<int>& out) {
    if (!node) return;
    inorder(node->left, out);
    out.push_back(node->val);
    inorder(node->right, out);
}

bool isNonDecreasing(const vector<int>& arr) {
    for (int i = 1; i < static_cast<int>(arr.size()); ++i) {
        if (arr[i - 1] > arr[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    Node* root = nullptr;
    for (int x : {8, 3, 10, 1, 6, 14, 4, 7, 13}) root = insert(root, x);
    vector<int> arr;
    inorder(root, arr);
    for (int x : arr) cout << x << " ";
    cout << "\n";
    cout << boolalpha << isNonDecreasing(arr) << "\n";
    return 0;
}

Main.java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class Node {
        int val;
        Node left, right;
        Node(int val) { this.val = val; }
    }

    static Node insert(Node node, int val) {
        if (node == null) return new Node(val);
        if (val < node.val) node.left = insert(node.left, val);
        else if (val > node.val) node.right = insert(node.right, val);
        return node;
    }

    static void inorder(Node node, List<Integer> out) {
        if (node == null) return;
        inorder(node.left, out);
        out.add(node.val);
        inorder(node.right, out);
    }

    static boolean isNonDecreasing(List<Integer> arr) {
        for (int i = 1; i < arr.size(); i++) {
            if (arr.get(i - 1) > arr.get(i)) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        Node root = null;
        int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        for (int x : arr) root = insert(root, x);

        List<Integer> out = new ArrayList<>();
        inorder(root, out);
        System.out.println(out);
        System.out.println(isNonDecreasing(out));
    }
}

main.py

def inorder(node, out):
    if node is None:
        return
    inorder(node.left, out)
    out.append(node.val)
    inorder(node.right, out)

def is_non_decreasing(arr):
    for i in range(1, len(arr)):
        if arr[i - 1] > arr[i]:
            return False
    return True

arr = []
inorder(root, arr)
print(arr)  # 오름차순이면 BST 불변식 유지
print(is_non_decreasing(arr))

main.rs

#[derive(Debug)]
struct Node {
    val: i32,
    left: Option<Box<Node>>,
    right: Option<Box<Node>>,
}

impl Node {
    fn new(val: i32) -> Self {
        Self {
            val,
            left: None,
            right: None,
        }
    }
}

fn insert(node: &mut Option<Box<Node>>, val: i32) {
    match node {
        None => *node = Some(Box::new(Node::new(val))),
        Some(n) => {
            if val < n.val {
                insert(&mut n.left, val);
            } else if val > n.val {
                insert(&mut n.right, val);
            }
        }
    }
}

fn inorder(node: &Option<Box<Node>>, out: &mut Vec<i32>) {
    if let Some(n) = node {
        inorder(&n.left, out);
        out.push(n.val);
        inorder(&n.right, out);
    }
}

fn main() {
    let mut root: Option<Box<Node>> = None;
    for x in [8, 3, 10, 1, 6, 14, 4, 7, 13] {
        insert(&mut root, x);
    }
    let mut arr = Vec::new();
    inorder(&root, &mut arr);
    println!("{:?}", arr);
    let mut sorted = true;
    let mut i = 1usize;
    while i < arr.len() {
        if arr[i - 1] > arr[i] {
            sorted = false;
            break;
        }
        i += 1;
    }
    println!("{}", sorted);
}

불변식 확인 해석

중위 순회 결과가 오름차순이면 BST 성질이 유지된 것입니다.
삭제 구현 후 검증 단계에서 매우 유용한 체크입니다.
테스트 자동화에 이 검증을 넣으면 구조 손상 버그를 빠르게 감지할 수 있습니다.

시간복잡도: O(N)
공간복잡도: O(N) (결과 배열 + 순회 스택/재귀)

구조 운용 관점

BST 사용 전 확인할 항목입니다.

정렬된 탐색/범위 질의가 자주 필요한가
입력이 편향될 가능성이 높은가
균형 트리(AVL/RB Tree)까지 필요한가
구현 복잡도 대비 성능 이득이 충분한가

편향 위험이 크면 균형 트리 또는 다른 구조를 함께 검토해야 합니다.

구현 비용 균형 지점

BST 선택에서 자주 맞닥뜨리는 균형점입니다.

장점: 정렬된 탐색과 범위 질의에 유리
단점: 편향 입력에서 선형 성능으로 악화
장점: 구현 개념이 명확
단점: 삭제 분기가 복잡해 버그 가능성 증가

문제 요구가 단순 조회라면 해시가 더 적합할 수 있습니다.

BST 삭제 반례와 복구 절차

BST 구현에서 흔한 오류를 케이스 기준으로 정리합니다.

케이스 A - 부모 연결 갱신 누락: 오답은 삭제 후 반환 노드를 부모 포인터에 다시 연결하지 않는 것입니다. 디버깅은 삭제된 값이 탐색에서 다시 발견되는지 확인합니다. 교정은 재귀 반환값을 node->left 또는 node->right에 항상 재대입하는 것입니다.
케이스 B - 2자식 후속자 미삭제: 오답은 후속자 값을 복사한 뒤 원본 노드를 남겨두는 것입니다. 디버깅은 중위 순회에서 값이 중복되는지 확인합니다. 교정은 후속자 키를 대상으로 추가 삭제 호출을 수행하는 것입니다.
케이스 C - 중복 키 정책 미정의: 오답은 </<=를 혼용해 삽입·삭제 경로가 흔들리는 것입니다. 디버깅은 특정 입력에서 결과가 비결정적으로 바뀌는지 확인합니다. 교정은 중복 허용/비허용 정책을 고정하고 비교 연산을 일관되게 적용하는 것입니다.
케이스 D - 편향 입력 무시: 오답은 이미 정렬된 입력에서도 BST를 그대로 사용하는 것입니다. 디버깅은 트리 높이와 탐색 시간의 급격한 증가를 확인합니다. 교정은 균형 BST나 다른 자료구조를 선택하는 것입니다.

반례 테스트는 루트 삭제, 리프 삭제, 단일 자식 삭제를 모두 포함해야 합니다.

BST 편향 성능 경계 정리

균형 지점 판단 시에는 평균 성능뿐 아니라 최악 입력 분포, 메모리 제약, 구현 복잡도를 함께 비교해야 합니다.

연산	평균 시간	최악 시간	공간
삽입	`O(log N)`	`O(N)`	`O(H)`
탐색	`O(log N)`	`O(N)`	`O(1)` 반복 구현
삭제	`O(log N)`	`O(N)`	`O(H)`

복잡도 상한은 트리 높이 H에 의해 결정됩니다.

제출 전 체크점

재귀 구현에서는 반환값 연결(return node) 누락을 특히 주의합니다.
대량 데이터에서는 균형 유지 전략이 없는 BST가 병목이 될 수 있습니다.
디버깅 시 중위 순회 결과를 함께 비교하면 구조 오류를 빠르게 찾을 수 있습니다.
스레드 환경에서 동시 수정은 별도 동기화 전략이 필요합니다.

BST 품질 체크포인트

삽입/탐색에서 비교 기준(<, >)을 일관되게 적용했는가
삭제 0/1/2자식 케이스를 모두 테스트했는가
중위 순회 결과로 불변식 검증을 자동화했는가
편향 입력에서 성능 저하 가능성을 고려했는가

BST 연산 규칙 정리

BST는 불변식 중심으로 이해하면 삽입/탐색/삭제가 하나의 규칙으로 연결됩니다.
삭제 분기와 검증 루틴을 정확히 갖추면, 실전에서도 안정적으로 활용할 수 있는 구조가 됩니다.

BST 삽입, 삭제, 탐색의 핵심 규칙

목차