노트

트리 순회

Tree Traversal

CS#algorithm · 연결된 개념 8개

쉽게 말하면

트리 순회는 가계도에 있는 모든 사람을 빠짐없이 한 번씩 부르는 순서를 정하는 일이에요. 부모를 먼저 부를지, 자식들을 다 부른 뒤에 부를지에 따라 복제·삭제처럼 쓰임새가 달라져요.

비유가 깨지는 곳 부르는 순서만 다를 뿐 시간은 모두 O(n)이에요. 실제로 갈리는 건 메모리라서, 넓은 트리에서 너비 우선은 한 층 전체를 큐에 담고, 깊이 우선은 높이만큼만 써요.

트리의 모든 노드를 한 번씩 방문하는 방법. 같은 층을 먼저 훑는 너비 우선(Breadth-First)과, 한 가지를 끝까지 내려가는 깊이 우선(Depth-First)이 있고, 깊이 우선은 노드를 언제 방문하느냐에 따라 셋으로 나뉜다.

type T = { val: number; left?: T; right?: T }
 
const preorder = (n?: T): number[] => (n ? [n.val, ...preorder(n.left), ...preorder(n.right)] : [])
const inorder = (n?: T): number[] => (n ? [...inorder(n.left), n.val, ...inorder(n.right)] : [])
const postorder = (n?: T): number[] => (n ? [...postorder(n.left), ...postorder(n.right), n.val] : [])
  • 전위(Pre-order): 나 → 왼쪽 → 오른쪽. 트리를 그대로 복제하거나 직렬화할 때 구조를 보존한다
  • 중위(In-order): 왼쪽 → 나 → 오른쪽. 이진 탐색 트리에서는 값이 오름차순으로 나온다
  • 후위(Post-order): 왼쪽 → 오른쪽 → 나. 자식을 먼저 처리해야 하는 일, 예컨대 폴더 크기 합산이나 트리 삭제에 맞다
  • 너비 우선(BFS, Breadth-First Search): 큐에 넣으며 층별로 방문한다

무엇을 고를까

시간은 모두 O(n)으로 같고, 메모리가 다르다. 넓고 얕은 트리에서 너비 우선은 한 층 전체를 큐에 담아야 해서 메모리를 많이 쓰고, 깊이 우선은 높이만큼만 쓴다. 반대로 깊고 좁은 트리에서는 깊이 우선의 재귀가 깊어진다.

그래프 일반의 순회는 깊이 우선 탐색 (DFS)와 너비 우선 탐색 (BFS)에 있다. React가 컴포넌트 트리를 훑는 방식도 깊이 우선이다(Fiber 아키텍처).

연결된 개념

이 노트를 가리키는 문서

뜻이 가까운 노트

  • B-tree와 B+tree

    한 노드가 자식을 수백 개 가지는 균형 다진 트리. 높이가 낮아 디스크 페이지를 몇 번만 읽고 값을 찾으며, 잎이 정렬된 채 이어져 있어 범위 검색에 강하다.

  • 연결 리스트

    각 노드가 값과 다음 노드를 가리키는 포인터를 가지고 사슬처럼 이어진 자료구조. 리스트는 맨 앞(Head)과 맨 뒤(Tail), 길이 정도만 기억한다. 배열과 달리 인덱스가 없다.

  • 우선순위 큐

    원소마다 우선순위가 있고, 들어온 순서와 상관없이 우선순위가 가장 높은 것부터 꺼내는 추상 자료형(Abstract Data Type, ADT). 같은 우선순위끼리의 순서는 보장하지 않는다. 응급실 대기 순서가 좋은 비유다.

  • 이진 힙

    부모가 항상 자식보다 크거나(최대 힙, Max Heap) 작은(최소 힙, Min Heap) 완전 이진 트리(Complete Binary Tree). 형제끼리의 순서는 정하지 않는다. 가장 크거나 작은 값이 항상 루트에 있어 꺼내기 쉽다.

  • DB 인덱스와 트레이드오프

    DB 인덱스는 특정 컬럼 값으로 행을 빨리 찾도록 테이블 옆에 따로 유지하는 보조 자료구조(auxiliary data structure)다. 관계형 DB의 기본 인덱스는 정렬된 균형 트리(B-tree 계열)라서, 전체를 훑지 않고 트리를 따라 내려가 원하는 행에 닿는다.

보기 옵션