이진 트리

Q: 불균형 이진 트리는 왜 성능이 그렇게 나쁜가요?

이진 탐색 트리에서 탐색, 삽입, 삭제는 높이를 `h` 라 할 때 `O(h)` 가 듭니다. 키를 정렬된 순서로 삽입하면 트리가 일직선이 되어 `h` 가 `n` 까지 커지고 모든 연산이 `O(n)` 으로 퇴화합니다. 연결 리스트와 다를 바 없죠. AVL이나 레드-블랙 트리 같은 자가 균형 트리는 이를 막기 위해 높이를 `O(log n)` 으로 유지합니다.

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

이진 트리는 각 노드가 최대 두 개의 자식(왼쪽 자식과 오른쪽 자식)을 갖는 계층 구조입니다. 맨 위 노드는 루트이고, 자식이 없는 노드는 리프이며, 루트에서 가장 깊은 리프까지의 간선 수가 트리의 높이입니다. 이진 탐색 트리와 달리 일반 이진 트리에는 정렬 규칙이 없으며 형태만을 나타냅니다. 위의 재생을 누르면 트리가 레벨별로 채워진 뒤 중위 순서(왼쪽, 노드, 오른쪽)로 순회되는 모습을 볼 수 있습니다.

이진 트리는 이진 탐색 트리, 힙, 식 트리 등 많은 구조의 기반이 됩니다. 순회는 각 노드를 정해진 순서로 방문합니다. 중위, 전위, 후위 순회는 세 가지 깊이 우선 순회이며 각각 서로 다른 작업에 유용합니다.

용어

용어	의미
루트	부모가 없는 맨 위 노드
리프	자식이 없는 노드
높이	루트에서 리프까지의 가장 긴 경로(간선 수)
깊이	루트로부터 노드까지의 거리
완전	마지막 레벨을 제외한 모든 레벨이 가득 차고, 마지막은 왼쪽에서 오른쪽으로 채워짐

세 가지 깊이 우선 순회

순회	순서	일반적인 용도
중위	왼쪽, 노드, 오른쪽	BST의 정렬된 출력
전위	노드, 왼쪽, 오른쪽	트리 복사 / 직렬화
후위	왼쪽, 오른쪽, 노드	트리 삭제 / 평가

예제 풀이

[4, 2, 6, 1, 3, 5] 로 (레벨별로 채워) 만든 트리의 중위 순회:

단계	대상 노드	동작
1	`4`	`4` 를 방문하기 전에 그 왼쪽 서브트리로 재귀
2	`2`	`2` 를 방문하기 전에 그 왼쪽 서브트리로 재귀
3	`1`	리프이고 왼쪽 자식 없음: `1` 방문, 출력 `[1]`
4	`2`	왼쪽 완료: `2` 방문, 출력 `[1, 2]`, 이후 오른쪽으로 재귀
5	`3`	리프: `3` 방문, 출력 `[1, 2, 3]`
6	`4`	왼쪽 서브트리 완료: `4` 방문, 출력 `[1, 2, 3, 4]`, 이후 오른쪽으로 재귀
7	`5`	`6` 의 왼쪽 자식이자 리프: `5` 방문, 출력 `[1, 2, 3, 4, 5]`
8	`6`	왼쪽 완료, 오른쪽 자식 없음: `6` 방문, 출력 `[1, 2, 3, 4, 5, 6]`

이진 트리를 사용해야 할 때

사용할 때	피해야 할 때
본질적으로 계층적인 데이터(파일 시스템, 식 트리, DOM)를 모델링해야 할 때	데이터가 평탄해서 리스트나 배열이면 충분할 때: 트리는 오버헤드만 늘림
정렬된 연산이 필요하고 균형을 유지할 수 있을 때(BST 또는 자가 균형 트리)	키로 평균 `O(1)` 조회가 필요할 때: 해시 테이블이 어떤 트리보다 우수함
구조화된 데이터를 중위, 전위, 후위 순서로 처리해야 할 때	정렬된 순서로 불균형 BST에 노드를 삽입할 때: `O(n)` 리스트로 퇴화함
범위 질의나 정렬된 순회가 중요할 때: 해시 테이블은 제공하지 못함	메모리가 빠듯할 때: 각 노드가 데이터 외에 두 개의 자식 포인터를 지님

Binary Tree 코드

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

Python로 구현한 Binary Tree 코드Python
1from collections import deque2
3
4class Node:5    def __init__(self, value):6        self.value = value7        self.left = None8        self.right = None9
10
11def insert(root, value):12    # Level-order insert: fill the first empty child slot found13    if root is None:14        return Node(value)15    queue = deque([root])16    while queue:17        node = queue.popleft()18        if node.left is None:19            node.left = Node(value)20            return root21        queue.append(node.left)22        if node.right is None:23            node.right = Node(value)24            return root25        queue.append(node.right)26
27
28def inorder(node):29    if node is None:30        return []31    return inorder(node.left) + [node.value] + inorder(node.right)32
33
34root = None35for value in [1, 2, 3, 4, 5, 6, 7]:36    root = insert(root, value)37
38print("Root:   ", root.value)39print("Inorder:", inorder(root))
이 코드를 Python 플레이그라운드에서 실행하기

JavaScript로 구현한 Binary Tree 코드JavaScript
1class Node {2    constructor(value) {3        this.value = value;4        this.left = null;5        this.right = null;6    }7}8
9class BinaryTree {10    constructor() {11        this.root = null;12    }13
14    // Insert at the first free spot, top to bottom (level order)15    insert(value) {16        const node = new Node(value);17        if (!this.root) {18            this.root = node;19            return;20        }21        const queue = [this.root];22        while (queue.length > 0) {23            const current = queue.shift();24            if (!current.left) {25                current.left = node;26                return;27            }28            if (!current.right) {29                current.right = node;30                return;31            }32            queue.push(current.left, current.right);33        }34    }35
36    inorder(node = this.root, out = []) {37        if (!node) return out;38        this.inorder(node.left, out);39        out.push(node.value);40        this.inorder(node.right, out);41        return out;42    }43}44
45const tree = new BinaryTree();46for (const value of [1, 2, 3, 4, 5, 6, 7]) tree.insert(value);47console.log("Inorder traversal:", tree.inorder().join(" "));
이 코드를 JavaScript 플레이그라운드에서 실행하기

Java로 구현한 Binary Tree 코드Java
1import java.util.ArrayDeque;2import java.util.Queue;3
4public class Main {5    static class Node {6        int value;7        Node left, right;8        Node(int value) { this.value = value; }9    }10
11    static Node root;12
13    // Insert at the first free slot in level order (keeps the tree complete)14    static void insert(int value) {15        Node node = new Node(value);16        if (root == null) { root = node; return; }17        Queue<Node> queue = new ArrayDeque<>();18        queue.add(root);19        while (!queue.isEmpty()) {20            Node cur = queue.poll();21            if (cur.left == null) { cur.left = node; return; }22            if (cur.right == null) { cur.right = node; return; }23            queue.add(cur.left);24            queue.add(cur.right);25        }26    }27
28    // Inorder: left subtree, node, right subtree29    static void inorder(Node node, StringBuilder sb) {30        if (node == null) return;31        inorder(node.left, sb);32        sb.append(node.value).append(" ");33        inorder(node.right, sb);34    }35
36    public static void main(String[] args) {37        for (int v = 1; v <= 7; v++) insert(v);38        StringBuilder sb = new StringBuilder();39        inorder(root, sb);40        System.out.println("Root: " + root.value);41        System.out.println("Inorder: " + sb.toString().trim());42    }43}
이 코드를 Java 플레이그라운드에서 실행하기

C++로 구현한 Binary 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 root->right = insert(root->right, value);14    return root;15}16
17// In-order traversal: left subtree, node, right subtree18void inorder(const Node* node) {19    if (node == nullptr) return;20    inorder(node->left);21    std::cout << node->value << " ";22    inorder(node->right);23}24
25int countNodes(const Node* node) {26    if (node == nullptr) return 0;27    return 1 + countNodes(node->left) + countNodes(node->right);28}29
30int main() {31    Node* root = nullptr;32    for (int value : {8, 3, 10, 1, 6, 14, 4}) {33        root = insert(root, value);34    }35    std::cout << "In-order: ";36    inorder(root);37    std::cout << "\n";38    std::cout << "Node count: " << countNodes(root) << "\n";39    return 0;40}
이 코드를 C++ 플레이그라운드에서 실행하기

C로 구현한 Binary Tree 코드C
1#include <stdio.h>2#include <stdlib.h>3
4typedef struct Node {5    int value;6    struct Node* left;7    struct Node* right;8} Node;9
10Node* newNode(int value) {11    Node* n = malloc(sizeof(Node));12    n->value = value;13    n->left = n->right = NULL;14    return n;15}16
17Node* insert(Node* root, int value) {18    if (root == NULL) return newNode(value);19    if (value < root->value) root->left = insert(root->left, value);20    else root->right = insert(root->right, value);21    return root;22}23
24// In-order traversal: left subtree, node, right subtree25void inorder(const Node* node) {26    if (node == NULL) return;27    inorder(node->left);28    printf("%d ", node->value);29    inorder(node->right);30}31
32int countNodes(const Node* node) {33    if (node == NULL) return 0;34    return 1 + countNodes(node->left) + countNodes(node->right);35}36
37int main(void) {38    int values[] = {8, 3, 10, 1, 6, 14, 4};39    Node* root = NULL;40    for (int i = 0; i < 7; i++) root = insert(root, values[i]);41    printf("In-order: ");42    inorder(root);43    printf("\n");44    printf("Node count: %d\n", countNodes(root));45    return 0;46}
이 코드를 C 플레이그라운드에서 실행하기

이진 트리 FAQ

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

이진 트리는 단지 각 노드를 최대 두 개의 자식으로 제한할 뿐 정렬이 없습니다. 이진 탐색 트리는 왼쪽 서브트리의 모든 값은 더 작고 오른쪽 서브트리의 모든 값은 더 크다는 규칙을 더하며, 이것이 탐색을 빠르게 만듭니다.

중위 순회란 무엇인가요?

중위 순회는 재귀적으로 왼쪽 서브트리, 그다음 노드, 그다음 오른쪽 서브트리를 방문합니다. 이진 탐색 트리에서는 이것이 값을 오름차순으로 산출하므로 가장 흔히 보여 주는 순회입니다.

완전 이진 트리란 무엇인가요?

완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워지고, 마지막 레벨은 왼쪽에서 오른쪽으로 채워집니다. 이 형태 덕분에 트리를 배열에 (자식 포인터 없이) 압축해 저장할 수 있으며, 이진 힙이 이렇게 구현됩니다.

배열이나 해시 테이블 대신 언제 이진 트리를 사용해야 하나요?

데이터가 자연스럽게 계층적이거나 범위 질의와 정렬된 순회 같은 정렬 연산이 필요할 때(해시 테이블이 제공하지 못하는 것) 트리를 선택하세요. 정렬 없이 빠른 키 조회만 필요하다면 해시 테이블의 평균 O(1) 접근이 트리를 능가하며, 평탄한 데이터에는 배열이 더 단순하고 캐시에도 유리합니다.

이진 트리의 높이와 깊이의 차이는 무엇인가요?

깊이는 루트에서 특정 노드까지 아래로 측정하며, 루트에서 그 노드까지 경로의 간선 수입니다. 높이는 한 노드에서 가장 깊은 리프까지 아래로 측정하므로 전체 트리의 높이는 가장 깊은 노드의 깊이입니다. 노드가 하나뿐인 트리는 높이가 0 이며, 그 유일한 노드의 깊이도 0 입니다.

불균형 이진 트리는 왜 성능이 그렇게 나쁜가요?

이진 탐색 트리에서 탐색, 삽입, 삭제는 높이를 h 라 할 때 O(h) 가 듭니다. 키를 정렬된 순서로 삽입하면 트리가 일직선이 되어 h 가 n 까지 커지고 모든 연산이 O(n) 으로 퇴화합니다. 연결 리스트와 다를 바 없죠. AVL이나 레드-블랙 트리 같은 자가 균형 트리는 이를 막기 위해 높이를 O(log n) 으로 유지합니다.