트리의 모양이 성능을 만든다 - 이름과 비용: 자료구조 ep.04

트리는 값을 담는 그릇이 아니라, 값들 사이의 관계를 모양으로 고정해 둔 구조입니다.

절반씩 버릴 수 있다는 약속

이진탐색트리(binary search tree) 의 규칙은 하나입니다. 어떤 노드를 보든 왼쪽 자식들은 그 노드보다 작고, 오른쪽 자식들은 큽니다.

이 규칙 덕분에 탐색이 짧아집니다. 찾는 값이 현재 노드보다 작으면 오른쪽 전체를 볼 필요가 없습니다. 한 번 비교할 때마다 후보의 절반이 사라집니다.

높이가 h인 트리에서 탐색은 최대 h번의 비교로 끝납니다. 노드가 N개이고 트리가 잘 퍼져 있으면 h는 log N입니다. 백만 개 노드에서 스무 번 남짓이면 도달합니다.

문제는 트리가 잘 퍼져 있다는 그 전제입니다.

정렬된 데이터를 넣으면 트리가 아니게 됩니다

1, 2, 3, 4, 5를 차례로 넣어봅니다. 1이 루트가 되고, 2는 1보다 크니 오른쪽으로, 3은 2보다 크니 또 오른쪽으로 갑니다. 왼쪽 가지는 한 번도 쓰이지 않습니다.

결과는 한 줄로 늘어선 노드입니다. 이름만 트리이고 실질은 연결 리스트입니다. 탐색은 O(N)이 됩니다.

같은 값 다섯 개이고 같은 규칙인데 결과가 다릅니다. 갈린 건 삽입 순서 하나입니다.

이런 상황은 실무에서 자연스럽고 흔하게 발생합니다. 데이터베이스에서 정렬된 데이터를 받아 그대로 트리에 넣으면 최악의 경우가 됩니다.

균형은 높이를 통제하는 규칙입니다

균형 이진탐색트리(balanced binary search tree) 는 삽입하거나 삭제할 때마다 트리 모양을 다시 정리해서 높이가 log N을 벗어나지 않게 유지합니다.

AVL 트리(AVL tree) 는 모든 노드에서 좌우 서브트리 높이 차가 1을 넘지 않게 강제합니다. 어긴 순간 회전이라는 국소적인 재배치로 바로잡습니다. 조건이 빡빡한 만큼 트리가 낮게 유지되어 탐색이 빠르고, 대신 삽입과 삭제에서 회전이 자주 일어납니다.

레드블랙 트리(red-black tree) 는 노드에 색을 부여하고 몇 가지 색 규칙으로 높이 차가 두 배를 넘지 않게 제한합니다. AVL보다 느슨해서 트리가 조금 더 높아질 수 있지만 재배치가 덜 일어납니다. 삽입과 삭제가 잦은 환경에서 유리해 여러 표준 라이브러리의 순서 있는 맵 구현에 쓰입니다.

둘 다 세부 회전 절차를 외울 필요는 없습니다. 균형 트리는 최악을 없애기 위해 평상시 비용을 조금 더 내는 거래라는 점만 알면 됩니다.

힙은 전부 정렬하지 않습니다

힙(heap) 은 전체 순서를 매기지 않고 가장 크거나 작은 값 하나만 빠르게 꺼내려고 쓰는 트리입니다.

규칙은 부모가 자식보다 항상 작다는 것 하나입니다. 최소 힙 기준이고, 형제끼리는 아무 관계가 없습니다. 전체를 정렬하지 않으므로 유지 비용이 낮습니다.

여기에 모양 제약이 하나 붙습니다. 힙은 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워지는 완전 이진 트리(complete binary tree) 입니다. 편향이 구조적으로 불가능하니 높이는 항상 log N입니다.

이 모양 덕분에 포인터가 필요 없습니다. 배열에 순서대로 담으면 인덱스 계산만으로 부모와 자식을 찾습니다.

인덱스 i의 부모는 (i - 1) >> 1
왼쪽 자식은 2 * i + 1, 오른쪽 자식은 2 * i + 2

인덱스 4의 부모는 1, 자식은 9와 10과 같이 바로 계산해 찾을 수 있습니다.

우선순위 큐 직접 만들기

자바스크립트에는 우선순위 큐(priority queue) 가 내장되어 있지 않습니다. 최단 경로나 스케줄링을 다루려면 직접 만들어야 합니다.

class MinHeap {
  #data = [];
  #compare;

  constructor(compare = (a, b) => a - b) {
    this.#compare = compare;
  }

  get size() {
    return this.#data.length;
  }

  push(value) {
    this.#data.push(value);
    this.#siftUp(this.#data.length - 1);
  }

  pop() {
    if (this.#data.length === 0) return undefined;
    const top = this.#data[0];
    const last = this.#data.pop();
    if (this.#data.length > 0) {
      this.#data[0] = last;
      this.#siftDown(0);
    }
    return top;
  }

  // 새로 넣은 값을 부모와 비교하며 위로 올린다
  #siftUp(i) {
    while (i > 0) {
      const parent = (i - 1) >> 1;
      if (this.#compare(this.#data[i], this.#data[parent]) >= 0) break;
      [this.#data[i], this.#data[parent]] = [this.#data[parent], this.#data[i]];
      i = parent;
    }
  }

  // 맨 위로 올라온 값을 더 작은 자식과 바꾸며 내린다
  #siftDown(i) {
    const n = this.#data.length;
    while (true) {
      const left = 2 * i + 1;
      const right = left + 1;
      let smallest = i;
      if (left < n && this.#compare(this.#data[left], this.#data[smallest]) < 0) smallest = left;
      if (right < n && this.#compare(this.#data[right], this.#data[smallest]) < 0) smallest = right;
      if (smallest === i) break;
      [this.#data[i], this.#data[smallest]] = [this.#data[smallest], this.#data[i]];
      i = smallest;
    }
  }
}

비교 함수를 주입받게 해두면 객체도 담을 수 있습니다. 최대 힙이 필요하면 비교 방향만 뒤집습니다.

const tasks = new MinHeap((a, b) => a.priority - b.priority);
tasks.push({ name: "결제 확인", priority: 1 });
tasks.push({ name: "로그 정리", priority: 9 });
tasks.pop(); // { name: "결제 확인", priority: 1 }

삽입과 삭제 모두 높이만큼만 움직이므로 O(log N)입니다. 최솟값 확인은 배열 첫 칸을 읽는 O(1)입니다.

순회는 방문 시점의 문제입니다

트리를 전부 훑는 방법은 자식을 언제 방문하느냐로 갈립니다.

전위 순회(preorder): 현재 노드를 먼저 처리하고 자식으로 내려갑니다. 트리를 복사하거나 구조를 그대로 출력할 때 씁니다
중위 순회(inorder): 왼쪽을 다 처리하고 현재 노드, 그다음 오른쪽입니다. 이진탐색트리에서 이 순서로 훑으면 값이 정렬된 순으로 나옵니다
후위 순회(postorder): 자식을 모두 처리한 뒤 현재 노드입니다. 하위 결과를 모아 올리는 계산이나 자원 해제에 맞습니다

중위 순회가 정렬 순서를 낸다는 성질은 자주 쓰입니다. 트리에 값을 넣기만 하면 정렬은 순회로 얻는 셈입니다.

참고 자료

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

다음 편 예고

ep.05 - 같은 구간을 반복해 묻는다면

배열의 특정 구간 합을 한 번 구하는 건 쉽습니다. 같은 질문이 십만 번 들어오고 중간에 값이 바뀌기까지 하면 이야기가 달라집니다. 누적합에서 세그먼트 트리까지의 선택지를 봅니다.