트리 (Tree)

순회 방식

트리의 모든 노드를 방문하는 것을 순회(traversal)라고 하며, 방문 순서에 따라 네 가지가 기본이다. 전위 순회(preorder)는 자신, 왼쪽, 오른쪽 순서로 방문하며 트리 복사나 직렬화에 쓰인다. 중위 순회(inorder)는 왼쪽, 자신, 오른쪽 순서이며 이진 탐색 트리(Binary Search Tree)에 적용하면 오름차순 정렬 결과를 얻는다. 후위 순회(postorder)는 왼쪽, 오른쪽, 자신 순서로, 자식을 먼저 정리해야 하는 삭제나 디렉터리 용량 계산에 적합하다. 레벨 순회(level order)는 큐(Queue)를 이용해 같은 깊이의 노드를 차례로 방문하는 너비 우선 탐색(BFS)이다. 앞의 세 방식은 재귀나 스택으로 구현하는 깊이 우선 탐색(DFS)에 해당하며, 모두 O(n)에 끝난다.

코드 예시

다음은 이진 트리의 중위 순회와 높이 계산을 재귀로 구현한 자바(Java) 예시다. 트리 문제 대부분이 이런 재귀 구조로 환원된다.

class Node {
    int value;
    Node left, right;
}

void inorder(Node node) {
    if (node == null) return;
    inorder(node.left);
    System.out.println(node.value);
    inorder(node.right);
}

int height(Node node) {
    if (node == null) return -1; // 리프의 높이를 0으로 두는 관례
    return 1 + Math.max(height(node.left), height(node.right));
}

균형의 중요성과 파생 구조

트리 연산의 비용은 대부분 높이에 비례한다. 노드 n개짜리 이진 트리의 높이는 균형이 잡혀 있으면 O(log n)이지만, 편향되면 O(n)까지 늘어난다. 그래서 탐색 성능을 보장하려면 AVL 트리나 레드 블랙 트리(Red-Black Tree) 같은 자가 균형(self-balancing) 트리가 필요하고, 디스크 기반 저장소에서는 한 노드에 키를 여러 개 담아 높이를 극단적으로 낮춘 B 트리 계열이 쓰인다. 문자열 검색에는 트라이, 우선순위 관리에는 힙이 있다. 결국 트리를 이해한다는 것은 "높이를 어떻게 관리하느냐"라는 관점으로 파생 구조들을 꿰는 일이다.

면접에서 이렇게 물어본다

• 트리가 그래프와 구별되는 조건을 말하고, 노드 n개인 트리의 간선 수가 항상 n-1개인 이유를 설명해 보라.
• 완전 이진 트리와 포화 이진 트리의 차이를 설명하고, 완전 이진 트리를 배열로 표현하는 방법을 말해 보라.
• 전위, 중위, 후위 순회의 방문 순서를 설명하고 각각이 유용한 사례를 들어 보라.
• 트리의 높이가 성능에 미치는 영향과, 균형을 유지하는 트리가 필요한 이유를 설명해 보라.
• 재귀 없이 중위 순회를 구현하려면 어떤 자료구조가 필요한지 설명해 보라.