Ray Book
자료구조와 알고리즘

트리와 이진 탐색 트리

계층 구조와 효율적 탐색, 트리 순회, BST 연산, 그리고 균형 트리의 필요성을 시각화합니다

csdata-structuretreebstbinary-search-treetraversal

트리 기본 개념

배열, 링크드 리스트, 스택, 큐, 해시맵은 모두 선형 자료구조입니다. 데이터가 일렬로 나열되죠. 하지만 현실의 많은 데이터는 계층 구조 (hierarchy) 를 가집니다. 파일 시스템의 폴더, HTML 문서의 태그 구조, 회사의 조직도가 대표적입니다.

트리 (Tree) 는 이런 계층 관계를 표현하는 비선형 자료구조입니다.

핵심 용어

A              <-- 루트 (Root): 최상위 노드
  B            <-- A의 자식 (Child), D/E의 부모 (Parent)
    D          <-- 리프 (Leaf): 자식이 없는 노드
    E          <-- 리프
  C
    F          <-- 리프
  • 루트 (Root) : 부모가 없는 최상위 노드. 트리에 하나만 존재합니다
  • 리프 (Leaf) : 자식이 없는 말단 노드
  • 간선 (Edge) : 부모-자식을 연결하는 선. 노드가 n개면 간선은 n-1개
  • 깊이 (Depth) : 루트에서 해당 노드까지의 간선 수. 루트의 깊이는 0
  • 높이 (Height) : 해당 노드에서 가장 먼 리프까지의 간선 수. 트리의 높이는 루트의 높이
  • 서브트리 (Subtree) : 어떤 노드를 루트로 하는 부분 트리

위 예시에서 노드 B를 루트로 하면 가 서브트리입니다. 트리의 높이는 2, 노드 D의 깊이는 2입니다.

이진 트리 순회

**이진 트리 (Binary Tree)**는 각 노드가 최대 두 개의 자식(왼쪽, 오른쪽)을 가지는 트리입니다. 이진 트리의 모든 노드를 빠짐없이 방문하는 것을 순회 (Traversal) 라고 합니다.

순회 방식은 네 가지가 있으며, "루트를 언제 방문하는가"로 구분합니다.

전위 순회 (Pre-order): 루트 -> 왼쪽 -> 오른쪽

Preorder(node):
    if node is null: return
    visit(node)              // 루트를 먼저 방문
    Preorder(node.left)
    Preorder(node.right)

중위 순회 (In-order): 왼쪽 -> 루트 -> 오른쪽

Inorder(node):
    if node is null: return
    Inorder(node.left)
    visit(node)              // 왼쪽 다 본 후 루트 방문
    Inorder(node.right)

BST에서 중위 순회를 하면 정렬된 순서 로 값을 얻습니다. 이것이 중위 순회가 중요한 이유입니다.

후위 순회 (Post-order): 왼쪽 -> 오른쪽 -> 루트

Postorder(node):
    if node is null: return
    Postorder(node.left)
    Postorder(node.right)
    visit(node)              // 자식 모두 본 후 루트 방문

레벨 순서 순회 (Level-order): 같은 깊이의 노드를 왼쪽에서 오른쪽으로

LevelOrder(root):
    queue = [root]
    while queue is not empty:
        node = queue.dequeue()
        visit(node)
        if node.left:  queue.enqueue(node.left)
        if node.right: queue.enqueue(node.right)

레벨 순서는 큐 를 사용합니다. 다음 글에서 다룰 BFS (너비 우선 탐색)와 동일한 패턴입니다.

순회 예시

8
    3   10
  1   6

전위:  8, 3, 1, 6, 10      (루트 먼저)
중위:  1, 3, 6, 8, 10      (정렬된 순서!)
후위:  1, 6, 3, 10, 8      (루트 마지막)
레벨:  8, 3, 10, 1, 6      (위에서 아래로)

이진 탐색 트리 (BST)

이진 탐색 트리 (Binary Search Tree)는 이진 트리에 정렬 규칙 을 추가한 자료구조입니다.

모든 노드에 대해: 왼쪽 서브트리의 모든 값 < 노드 값 < 오른쪽 서브트리의 모든 값

이 규칙 덕분에 탐색할 때 매 단계마다 절반을 버릴 수 있습니다 . 이진 탐색 (Binary Search)의 원리를 트리 구조에 적용한 것입니다.

8          BST 규칙 확인:
    3   10       - 8의 왼쪽: {1, 3, 6} 모두 < 8
  1   6          - 8의 오른쪽: {10} 모두 > 8
                 - 3의 왼쪽: {1} < 3, 오른쪽: {6} > 3

BST 연산

탐색 (Search) - O(log n)

매 단계에서 현재 노드와 비교하여 왼쪽 또는 오른쪽으로 이동합니다.

BST-Search(node, key):
    if node is null: return null        // 못 찾음
    if key == node.value: return node   // 발견!
    if key < node.value:
        return BST-Search(node.left, key)   // 왼쪽으로
    else:
        return BST-Search(node.right, key)  // 오른쪽으로

삽입 (Insert) - O(log n)

탐색과 동일한 경로를 따라 내려가다가, 빈 자리를 찾으면 새 노드를 넣습니다.

BST-Insert(node, key):
    if node is null:
        return new Node(key)            // 빈 자리에 삽입
    if key < node.value:
        node.left = BST-Insert(node.left, key)
    else if key > node.value:
        node.right = BST-Insert(node.right, key)
    return node

삭제 (Delete) - O(log n)

삭제는 세 가지 경우로 나뉩니다.

BST-Delete(node, key):
    if node is null: return null

    if key < node.value:
        node.left = BST-Delete(node.left, key)
    else if key > node.value:
        node.right = BST-Delete(node.right, key)
    else:
        // Case 1: 리프 노드 -> 그냥 삭제
        if node.left is null and node.right is null:
            return null
        // Case 2: 자식이 하나 -> 자식으로 대체
        if node.left is null: return node.right
        if node.right is null: return node.left
        // Case 3: 자식이 둘 -> 중위 후속자로 대체
        successor = find-min(node.right)
        node.value = successor.value
        node.right = BST-Delete(node.right, successor.value)

    return node

Case 3이 가장 복잡합니다. 오른쪽 서브트리에서 가장 작은 값 (중위 후속자)을 찾아 현재 노드의 값을 대체하고, 중위 후속자를 삭제합니다.

JavaScript 구현

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class BST {
  constructor() {
    this.root = null;
  }

  // 삽입 - O(log n)
  insert(value) {
    this.root = this._insert(this.root, value);
  }

  _insert(node, value) {
    if (node === null) return new TreeNode(value);

    if (value < node.value) {
      node.left = this._insert(node.left, value);
    } else if (value > node.value) {
      node.right = this._insert(node.right, value);
    }
    // 중복 값은 무시
    return node;
  }

  // 탐색 - O(log n)
  search(value) {
    return this._search(this.root, value);
  }

  _search(node, value) {
    if (node === null) return null;
    if (value === node.value) return node;

    return value < node.value
      ? this._search(node.left, value)
      : this._search(node.right, value);
  }

  // 삭제 - O(log n)
  delete(value) {
    this.root = this._delete(this.root, value);
  }

  _delete(node, value) {
    if (node === null) return null;

    if (value < node.value) {
      node.left = this._delete(node.left, value);
    } else if (value > node.value) {
      node.right = this._delete(node.right, value);
    } else {
      // Case 1 & 2: 자식이 없거나 하나
      if (node.left === null) return node.right;
      if (node.right === null) return node.left;

      // Case 3: 자식이 둘 -> 중위 후속자
      let successor = node.right;
      while (successor.left !== null) {
        successor = successor.left;
      }
      node.value = successor.value;
      node.right = this._delete(node.right, successor.value);
    }
    return node;
  }

  // 중위 순회 - 정렬된 순서로 출력
  inorder() {
    const result = [];
    this._inorder(this.root, result);
    return result;
  }

  _inorder(node, result) {
    if (node === null) return;
    this._inorder(node.left, result);
    result.push(node.value);
    this._inorder(node.right, result);
  }
}

// 사용 예시
const bst = new BST();
[8, 3, 10, 1, 6].forEach((v) => bst.insert(v));
console.log(bst.inorder());   // [1, 3, 6, 8, 10] - 정렬된 순서
console.log(bst.search(6));   // TreeNode { value: 6, ... }
bst.delete(3);
console.log(bst.inorder());   // [1, 6, 8, 10]

시각화

아래 시각화에서 BST의 삽입, 탐색, 삭제 과정을 단계별로 확인해 보세요. 각 단계에서 노드가 어떤 경로를 따라 이동하는지, 삭제 시 트리가 어떻게 재구성되는지 관찰합니다.

빈 트리1 / 8
빈 트리 (empty)
현재 노드탐색 경로삽입삭제발견대체
빈 트리에서 시작합니다. BST는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 따릅니다.

편향 트리의 문제

BST의 시간 복잡도 O(log n)에는 중요한 전제가 있습니다: 트리가 균형 잡혀 있어야 합니다.

만약 이미 정렬된 데이터를 순서대로 삽입하면 어떻게 될까요?

insert(1, 2, 3, 4, 5) 순서로 삽입하면:

1 -> 2 -> 3 -> 4 -> 5    사실상 링크드 리스트!

탐색: O(n)
삽입: O(n)
삭제: O(n)

모든 노드가 오른쪽 자식만 가지므로, 트리의 높이가 n-1이 됩니다. 이것을 편향 트리 (Skewed Tree) 라고 합니다. 링크드 리스트와 동일한 O(n) 성능으로 퇴화합니다.

트리 상태높이탐색/삽입/삭제
균형 BSTO(log n)O(log n)
편향 BSTO(n)O(n)

n = 1,000,000일 때:

  • 균형 BST: 약 20번의 비교
  • 편향 BST: 최대 1,000,000번의 비교

이 문제를 해결하기 위해 자가 균형 트리 (Self-balancing Tree) 가 등장합니다.

균형 트리

자가 균형 트리는 삽입/삭제 시 자동으로 트리의 높이를 O(log n)으로 유지합니다. 대표적인 두 가지를 소개합니다.

AVL 트리

Adelson-Velsky, Landis가 1962년에 발표한 최초의 자가 균형 BST입니다.

  • 균형 인수 (Balance Factor) = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
  • 모든 노드의 균형 인수가 -1, 0, 1 중 하나여야 합니다
  • 균형이 깨지면 회전 (Rotation) 으로 복구합니다
삽입 후 균형 깨짐:       왼쪽 회전 후:

3 (BF = -2)                5
  5 (BF = -1)            3   7
    7

AVL 트리는 엄격하게 균형을 유지하므로 탐색이 빠르지만, 삽입/삭제 시 회전 연산이 자주 발생합니다.

레드블랙 트리

1978년 Guibas와 Sedgewick이 발표한 자가 균형 BST입니다.

  • 각 노드에 빨간색또는 검은색 속성을 부여합니다
  • 다섯 가지 규칙으로 균형을 유지합니다.
    1. 모든 노드는 빨간색 또는 검은색
    2. 루트는 검은색
    3. 모든 리프 (NIL 노드)는 검은색
    4. 빨간 노드의 자식은 모두 검은색 (연속 빨간 노드 불가)
    5. 루트에서 모든 리프까지의 경로에 있는 검은 노드 수가 동일

AVL보다 균형이 느슨하지만, 삽입/삭제 시 회전이 적어 쓰기가 많은 상황 에서 유리합니다.

비교

특성AVL 트리레드블랙 트리
균형 기준높이 차이 <= 1색상 규칙 5가지
탐색약간 빠름 (더 엄격한 균형)약간 느림
삽입/삭제회전 많음회전 적음
사용 사례읽기 많은 경우읽기/쓰기 균형
실사용데이터베이스 인덱스Java TreeMap, Linux CFS 스케줄러

두 구조 모두 탐색/삽입/삭제가 O(log n)을 보장 합니다. 구현 세부사항은 이 글의 범위를 넘어가므로, 핵심 원리만 기억하면 충분합니다.

실무 연결

트리 구조는 웹 개발에서 이미 곳곳에 사용되고 있습니다.

DOM 트리

DOM은 HTML 문서를 트리 구조로 표현한 것입니다. 브라우저가 HTML을 파싱하면 다음과 같은 트리가 만들어집니다.

<html>
  <head>
    <title>Page</title>
  </head>
  <body>
    <div>
      <p>Hello</p>
    </div>
  </body>
</html>
html
  head
    title
  body
    div
      p

document.querySelector, parentNode, children 같은 DOM API는 모두 이 트리를 순회하는 연산입니다. 다음 글에서 다룰 BFS/DFS가 여기에 직접 적용됩니다.

AST (추상 구문 트리)

AST는 소스 코드의 구조를 트리로 표현한 것입니다. 1 + 2 * 3을 파싱하면:

+
1   *
  2   3

1 + (2 * 3) 의 AST

Babel, ESLint, Prettier, TypeScript 컴파일러 모두 AST를 기반으로 동작합니다. 코드를 AST로 변환하고, 트리를 순회하며 변환/분석/포맷팅을 수행합니다.

데이터베이스 인덱스

대부분의 관계형 데이터베이스 (MySQL, PostgreSQL)는 인덱스에 B-트리또는 B+ 트리 를 사용합니다. BST의 아이디어를 확장한 것으로, 각 노드가 여러 개의 키를 가져서 디스크 I/O를 최소화합니다.

다음 단계

트리는 계층 구조를 표현하는 자료구조였습니다. 하지만 현실에는 계층이 아닌 네트워크 관계도 많습니다. 소셜 네트워크의 친구 관계, 도로의 교차로, 웹 페이지 간의 링크 구조가 그렇습니다.

다음 글에서는 노드와 간선으로 이루어진 그래프 (Graph) 와 두 가지 핵심 탐색 알고리즘 BFS, DFS를 다룹니다.

자료구조와 알고리즘4 / 6
이전해시맵다음그래프와 탐색