트리 · 이진트리 · BST · 힙 — 계층적 자료구조

트리는 루트(root)에서 시작해 자식(children)으로 가지치기하는 계층 구조. 사이클 없음. 용어: 루트·잎(leaf)·부모·자식·깊이(depth)·높이(height)·서브트리.

이진트리(Binary Tree)는 자식이 최대 2개. 이진탐색트리(BST, Binary Search Tree)는 "왼쪽은 더 작은 값, 오른쪽은 더 큰 값" 규칙이 추가 → 탐색·삽입·삭제 평균 O(log n). 단 편향되면 O(n)이 되므로 현대에는 자가 균형 트리(AVL·Red-Black·B-Tree)가 실무 표준.

// 이진트리 순회 3종 (재귀)
function traverse(node) {
  if (!node) return;

  // 전위(pre-order): 루트 → 좌 → 우  (복사·직렬화)
  visit(node);
  traverse(node.left);
  traverse(node.right);

  // 중위(in-order): 좌 → 루트 → 우  (BST면 정렬 순서)
  // 후위(post-order): 좌 → 우 → 루트  (삭제·의존성 역순)
}

// 실전 용도
// - 전위: JSON 직렬화, 파일 복사
// - 중위: BST 정렬 순회, DB 인덱스 범위 조회
// - 후위: 폴더 삭제 (자식 먼저), 수식 후위표기법

// 레벨 순회(BFS) = 큐 사용 (ch17-4)

힙(Heap)은 "가장 큰(또는 작은) 값을 빨리 꺼내기"에 최적화된 이진트리. 최대 힙은 부모 ≥ 자식, 최소 힙은 반대. push O(log n), peek/pop O(log n). 구현은 배열로(부모 i, 자식 2i+1, 2i+2).