이진 탐색 트리(BST)

Q: 이진 탐색 트리의 시간 복잡도는 무엇인가요?

균형 트리에서 탐색, 삽입, 삭제는 `O(log n)`입니다. 각 비교가 남은 노드의 절반을 버리기 때문입니다. 최악의 경우 — 정렬된 삽입으로 사슬 형태로 치우친 트리 — 에는 `O(n)`으로 퇴화합니다.

Q: 이진 탐색 트리와 해시 테이블의 차이는 무엇인가요?

해시 테이블은 평균 `O(1)` 조회를 제공하지만 키를 특정 순서로 저장하지 않으므로 범위 질의나 후속 질의에 답할 수 없습니다. 이진 탐색 트리는 `O(log n)`으로 약간 느리지만 키를 정렬된 상태로 유지하여 순서대로 순회하고 가장 가까운 값을 찾을 수 있습니다. 순서가 중요하면 BST를, 소속 여부만 필요하면 해시 테이블을 선택하세요.

Q: 일반 BST 대신 자가 균형 트리를 언제 사용해야 하나요?

삽입 순서를 제어할 수 없고 보장된 `O(log n)` 성능이 필요할 때는 언제든 자가 균형 트리(AVL, 레드-블랙)를 사용하세요. 일반 BST는 교육용, 작은 데이터셋, 또는 키가 무작위 순서로 들어올 때는 적합하지만 치우친 최악의 경우에 대한 보호는 없습니다.

마지막 업데이트 2026년 7월 1일

이진 탐색 트리는 값을 정렬된 상태로 유지합니다. 모든 노드에 대해 왼쪽 서브트리의 모든 값은 더 작고 오른쪽 서브트리의 모든 값은 더 큽니다. 값을 삽입하거나 찾으려면 루트에서 시작해 비교에 따라 반복적으로 왼쪽 또는 오른쪽으로 이동하므로, 각 단계마다 탐색 범위가 절반으로 줄어듭니다. 위의 재생 버튼을 눌러 값이 비교로 배치되고 탐색이 트리를 따라 내려가는 모습을 확인하세요.

균형 트리에서는 이 연산들이 O(log n) 시간에 실행됩니다. 함정은 이미 정렬된 데이터를 삽입하면 트리가 연결 리스트로 퇴화하여 연산이 O(n)이 된다는 점입니다. 바로 이 때문에 AVL 트리, 레드-블랙 트리 같은 자가 균형 변형이 존재합니다.

시간 및 공간 복잡도

연산	균형	최악의 경우(치우침)
탐색	O(log n)	O(n)
삽입	O(log n)	O(n)
삭제	O(log n)	O(n)
공간	O(n)	O(n)

단계별 (삽입)

단계	무슨 일이 일어나는가
1	트리가 비어 있으면 새 값이 루트가 된다.
2	그렇지 않으면 루트에서 시작한다.
3	값이 더 작으면 왼쪽 자식으로, 더 크면 오른쪽으로 간다.
4	빈 자리에 도달할 때까지 반복한다.
5	그곳에 새 값을 잎으로 붙인다.

풀이 예제

빈 트리에 [5, 3, 8, 1, 4]를 하나씩 삽입하는 경우:

삽입	지나온 경로	동작
`5`	-	트리가 비어 있으므로 `5`가 루트가 된다.
`3`	`5`	`3 < 5`이므로 왼쪽으로 간다. 자리가 비어 있으므로 `3`을 `5`의 왼쪽 자식으로 붙인다.
`8`	`5`	`8 > 5`이므로 오른쪽으로 간다. 자리가 비어 있으므로 `8`을 `5`의 오른쪽 자식으로 붙인다.
`1`	`5 -> 3`	`1 < 5`로 왼쪽, 이어서 `1 < 3`으로 왼쪽으로 간다. `1`을 `3`의 왼쪽 자식으로 붙인다.
`4`	`5 -> 3`	`4 < 5`로 왼쪽, 이어서 `4 > 3`으로 오른쪽으로 간다. `4`를 `3`의 오른쪽 자식으로 붙인다.

이진 탐색 트리를 사용해야 할 때

사용하면 좋을 때	피해야 할 때
정렬된 순서와 빠른 조회가 모두 필요하고 삽입이 무작위 순서로 들어올 때.	데이터가 이미 정렬되어 들어올 때: 불균형 BST는 연산당 `O(n)`으로 퇴화한다.
중위 순회로 값을 정렬된 순서로 공짜로 얻고 싶을 때.	순서 없이 소속 여부만 필요할 때: 해시 테이블은 평균 `O(1)` 조회를 제공한다.
범위 질의나 키의 후속/선행 값이 필요할 때.	보장된 `O(log n)` 한계가 필요할 때: 대신 자가 균형 AVL 트리나 레드-블랙 트리를 사용한다.
데이터셋이 자주 바뀌어 정적인 정렬 배열을 갱신하는 비용이 클 때.	데이터셋이 고정이고 읽기 전용일 때: 이진 탐색이 붙은 정렬 배열이 더 단순하고 캐시 친화적이다.

Binary Search Tree 코드

Python, JavaScript, Java, C++, C로 작성된 깔끔하고 실행 가능한 Binary Search Tree 구현입니다. 언어를 선택해 코드를 복사하거나 Coddy 플레이그라운드에서 바로 열어보세요.

Python로 구현한 Binary Search Tree 코드Python
1class Node:2    def __init__(self, key):3        self.key = key4        self.left = None5        self.right = None6
7
8def insert(node, key):9    if node is None:10        return Node(key)11    if key < node.key:12        node.left = insert(node.left, key)13    elif key > node.key:14        node.right = insert(node.right, key)15    return node  # duplicates are ignored16
17
18def search(node, key):19    if node is None:20        return False21    if key == node.key:22        return True23    if key < node.key:24        return search(node.left, key)25    return search(node.right, key)26
27
28def inorder(node):29    if node is None:30        return []31    return inorder(node.left) + [node.key] + inorder(node.right)32
33
34root = None35for key in [8, 3, 10, 1, 6, 14, 4, 7]:36    root = insert(root, key)37
38print("Inorder (sorted):", inorder(root))39print("search(6): ", search(root, 6))40print("search(5): ", search(root, 5))
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Binary Search Tree 코드JavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.left = null;5        this.right = null;6    }7}8
9class BinarySearchTree {10    constructor() {11        this.root = null;12    }13
14    insert(value) {15        const attach = (node) => {16            if (!node) return new Node(value);17            if (value < node.value) node.left = attach(node.left);18            else node.right = attach(node.right);19            return node;20        };21        this.root = attach(this.root);22    }23
24    search(value) {25        let current = this.root;26        while (current) {27            if (value === current.value) return true;28            current = value < current.value ? current.left : current.right;29        }30        return false;31    }32
33    // Inorder traversal of a BST visits values in sorted order34    inorder(node = this.root, out = []) {35        if (!node) return out;36        this.inorder(node.left, out);37        out.push(node.value);38        this.inorder(node.right, out);39        return out;40    }41}42
43const bst = new BinarySearchTree();44for (const value of [8, 3, 10, 1, 6, 14, 4]) bst.insert(value);45console.log("Inorder:", bst.inorder().join(" "));46console.log("search(6):", bst.search(6));47console.log("search(7):", bst.search(7));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Binary Search Tree 코드Java
1public class Main {2    static class Node {3        int key;4        Node left, right;5        Node(int key) { this.key = key; }6    }7
8    static Node insert(Node node, int key) {9        if (node == null) return new Node(key);10        // Smaller keys go left, larger keys go right11        if (key < node.key) node.left = insert(node.left, key);12        else if (key > node.key) node.right = insert(node.right, key);13        return node;14    }15
16    static boolean search(Node node, int key) {17        if (node == null) return false;18        if (key == node.key) return true;19        return key < node.key ? search(node.left, key) : search(node.right, key);20    }21
22    static void inorder(Node node, StringBuilder sb) {23        if (node == null) return;24        inorder(node.left, sb);25        sb.append(node.key).append(" ");26        inorder(node.right, sb);27    }28
29    public static void main(String[] args) {30        Node root = null;31        int[] keys = {8, 3, 10, 1, 6, 14, 4};32        for (int k : keys) root = insert(root, k);33
34        StringBuilder sb = new StringBuilder();35        inorder(root, sb);36        System.out.println("Inorder (sorted): " + sb.toString().trim());37        System.out.println("search 6: " + search(root, 6));38        System.out.println("search 7: " + search(root, 7));39    }40}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Binary Search Tree 코드C++
1#include <iostream>2
3struct Node {4    int value;5    Node* left = nullptr;6    Node* right = nullptr;7    explicit Node(int v) : value(v) {}8};9
10Node* insert(Node* root, int value) {11    if (root == nullptr) return new Node(value);12    if (value < root->value) root->left = insert(root->left, value);13    else if (value > root->value) root->right = insert(root->right, value);14    return root;  // duplicates are ignored15}16
17bool contains(const Node* root, int value) {18    // Walk down: smaller goes left, larger goes right19    while (root != nullptr) {20        if (value == root->value) return true;21        root = value < root->value ? root->left : root->right;22    }23    return false;24}25
26void inorder(const Node* node) {27    if (node == nullptr) return;28    inorder(node->left);29    std::cout << node->value << " ";30    inorder(node->right);31}32
33int main() {34    Node* root = nullptr;35    for (int value : {50, 30, 70, 20, 40, 60, 80}) {36        root = insert(root, value);37    }38    std::cout << "Sorted: ";39    inorder(root);40    std::cout << "\n" << std::boolalpha;41    std::cout << "contains(40): " << contains(root, 40) << "\n";42    std::cout << "contains(45): " << contains(root, 45) << "\n";43    return 0;44}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Binary Search Tree 코드C
1#include <stdbool.h>2#include <stdio.h>3#include <stdlib.h>4
5typedef struct Node {6    int value;7    struct Node* left;8    struct Node* right;9} Node;10
11Node* newNode(int value) {12    Node* n = malloc(sizeof(Node));13    n->value = value;14    n->left = n->right = NULL;15    return n;16}17
18Node* insert(Node* root, int value) {19    if (root == NULL) return newNode(value);20    if (value < root->value) root->left = insert(root->left, value);21    else if (value > root->value) root->right = insert(root->right, value);22    return root;  // duplicates are ignored23}24
25bool contains(const Node* root, int value) {26    // Walk down: smaller goes left, larger goes right27    while (root != NULL) {28        if (value == root->value) return true;29        root = value < root->value ? root->left : root->right;30    }31    return false;32}33
34void inorder(const Node* node) {35    if (node == NULL) return;36    inorder(node->left);37    printf("%d ", node->value);38    inorder(node->right);39}40
41int main(void) {42    int values[] = {50, 30, 70, 20, 40, 60, 80};43    Node* root = NULL;44    for (int i = 0; i < 7; i++) root = insert(root, values[i]);45    printf("Sorted: ");46    inorder(root);47    printf("\n");48    printf("contains(40): %s\n", contains(root, 40) ? "true" : "false");49    printf("contains(45): %s\n", contains(root, 45) ? "true" : "false");50    return 0;51}
이 코드를 C 플레이그라운드에서 실행하기

이진 탐색 트리 자주 묻는 질문

이진 탐색 트리의 시간 복잡도는 무엇인가요?

균형 트리에서 탐색, 삽입, 삭제는 O(log n)입니다. 각 비교가 남은 노드의 절반을 버리기 때문입니다. 최악의 경우 — 정렬된 삽입으로 사슬 형태로 치우친 트리 — 에는 O(n)으로 퇴화합니다.

이진 트리와 이진 탐색 트리의 차이는 무엇인가요?

이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리로, 순서 규칙이 없습니다. 이진 탐색 트리는 왼쪽 서브트리 값이 노드보다 작고 오른쪽 서브트리 값이 크다는 불변식을 더하며, 이것이 빠른 탐색을 가능하게 합니다.

이진 탐색 트리가 왜 느려질 수 있나요?

값이 정렬(또는 역정렬) 순서로 삽입되면 모든 새 노드가 같은 쪽으로 가서 연결 리스트처럼 동작하는 높고 치우친 트리가 됩니다 — 연산당 O(n)입니다. 자가 균형 트리(AVL, 레드-블랙)는 이를 막기 위해 노드를 회전시킵니다.

이진 탐색 트리와 해시 테이블의 차이는 무엇인가요?

해시 테이블은 평균 O(1) 조회를 제공하지만 키를 특정 순서로 저장하지 않으므로 범위 질의나 후속 질의에 답할 수 없습니다. 이진 탐색 트리는 O(log n)으로 약간 느리지만 키를 정렬된 상태로 유지하여 순서대로 순회하고 가장 가까운 값을 찾을 수 있습니다. 순서가 중요하면 BST를, 소속 여부만 필요하면 해시 테이블을 선택하세요.

일반 BST 대신 자가 균형 트리를 언제 사용해야 하나요?

삽입 순서를 제어할 수 없고 보장된 O(log n) 성능이 필요할 때는 언제든 자가 균형 트리(AVL, 레드-블랙)를 사용하세요. 일반 BST는 교육용, 작은 데이터셋, 또는 키가 무작위 순서로 들어올 때는 적합하지만 치우친 최악의 경우에 대한 보호는 없습니다.

BST의 중위 순회는 정렬된 값을 반환하나요?

네. 왼쪽 서브트리, 그다음 노드, 그다음 오른쪽 서브트리를 방문하면 키가 오름차순으로 나오며, 이는 BST 불변식에서 곧바로 따라옵니다. 흔한 실수는 일반 이진 트리에도 같은 것을 기대하는 것입니다. 순서 규칙이 없으면 중위 순회는 의미 있는 순서를 만들어내지 못합니다.