트리와 이진 탐색 트리

트리(tree)는 노드(node)들이 부모-자식 관계로 이어진 계층 구조이고, 어느 노드에서 출발해도 제자리로 돌아오는 길이 없다. 폴더 구조나 조직도처럼 "위에서 아래로 갈라지는" 데이터를 담는다. 이 문서는 트리를 말할 때 쓰는 용어, 자식이 최대 둘인 트리의 모양별 이름, 모든 노드를 정해진 순서로 한 번씩 방문하는 방법을 다루고, 여기에 크기 규칙을 더한 이진 탐색 트리(binary search tree)는 이어지는 문서에서 다룬다.

트리 용어

트리에서 노드 사이의 연결을 간선(edge)이라 한다. 루트를 뺀 모든 노드는 부모와 잇는 간선을 정확히 하나씩 가지므로, 노드가 n개인 트리는 간선이 늘 n − 1개다. 한 노드에서 출발해 다시 그 노드로 돌아오는 경로를 사이클(cycle)이라 하는데, 트리에는 사이클이 없다.

• 루트 노드(root node): 맨 위에 있고 부모가 없는 노드. 트리에 하나뿐이다.
• 부모와 자식: 간선으로 바로 이어진 두 노드 중 위쪽이 부모, 아래쪽이 자식이다.
• 리프 노드(leaf node): 자식이 없는 맨 끝 노드.
• 서브트리(subtree): 어떤 노드와 그 아래 모든 자손으로 이뤄진 작은 트리.
• 깊이(depth): 루트에서 그 노드까지 거치는 간선 수. 루트의 깊이는 0이다.
• 높이(height): 그 노드에서 가장 먼 리프 노드까지의 간선 수. 트리의 높이는 루트의 높이다. 깊이와 높이를 간선 수가 아니라 노드 수로 세는 교재도 있으니 기준을 확인한다.

이진 트리의 종류

이진 트리(binary tree)는 모든 노드의 자식이 최대 두 개인 트리다. 자식을 왼쪽·오른쪽으로 구분한다. 모양에 따라 부르는 이름이 있다.

• 포화 이진 트리(perfect binary tree): 모든 층이 꽉 찬 이진 트리. 층마다 노드가 1, 2, 4, …로 두 배씩 늘어나므로, 높이가 h이면 노드는 1 + 2 + … + 2^h = 2^(h+1) − 1개다.
• 완전 이진 트리(complete binary tree): 마지막 층을 뺀 모든 층이 꽉 차 있고, 마지막 층은 왼쪽부터 채워진 이진 트리. 빈칸 없이 배열(array)에 차례로 담을 수 있다. 그러면 i번 칸 노드의 자식이 2i + 1번과 2i + 2번 칸(0번부터 셀 때)에 있어, 포인터(pointer) 없이 계산만으로 부모와 자식을 찾는다. 힙이 이 모양을 쓰는 이유다.
• 편향 이진 트리(skewed binary tree): 모든 노드가 한쪽 자식만 가진 트리. 모양은 트리지만 사실상 한 줄로 늘어선 연결 리스트(linked list)라서 높이가 n − 1이 되고, 맨 아래까지 내려가려면 노드를 전부 거쳐야 한다.

순회: 모든 노드를 한 번씩

순회(traversal)는 모든 노드를 정해진 순서로 한 번씩 방문하는 것이다. 아래 트리로 네 가지 순서를 비교한다.

다이어그램 로딩…

순서	방문 규칙	위 트리 결과	쓰임
전위	나 → 왼쪽 → 오른쪽	8 3 1 6 10 14	트리 복사, 구조 출력
중위	왼쪽 → 나 → 오른쪽	1 3 6 8 10 14	이진 탐색 트리의 오름차순 출력
후위	왼쪽 → 오른쪽 → 나	1 6 3 14 10 8	자식을 먼저 처리(폴더 크기 합산, 트리 삭제)
레벨 순서	위층부터 왼쪽→오른쪽	8 3 10 1 6 14	층별 처리

전위 순회(preorder traversal)는 노드 자신을 먼저 방문한다. 부모를 먼저 만들어야 자식을 붙일 수 있는 트리 복사에 맞는다. 중위 순회(inorder traversal)는 왼쪽 서브트리를 다 돈 뒤 자신을 방문한다. 이진 탐색 트리는 왼쪽 서브트리에 더 작은 값, 오른쪽 서브트리에 더 큰 값만 두므로, 중위 순회로 돌면 값이 오름차순으로 나온다. 후위 순회(postorder traversal)는 자식을 모두 처리한 뒤 자신을 방문한다. 자식을 먼저 지워야 부모를 지울 수 있는 트리 삭제에 맞는다. 앞의 세 가지는 재귀(recursion)로 짧게 쓸 수 있다. 레벨 순서 순회(level-order traversal)는 같은 층을 먼저 다 도는 방식이라, 방문할 노드를 먼저 넣은 순서대로 꺼내는 큐(queue)를 쓴다.

void inorder(Node n) {
    if (n == null) return;
    inorder(n.left);
    visit(n);          // 이 줄을 맨 앞으로 옮기면 전위, 맨 뒤로 옮기면 후위
    inorder(n.right);
}

이어지는 내용은 트리와 이진 탐색 트리 2에서 다룬다.

면접 포인트

• "깊이와 높이의 차이는?" → 깊이는 루트에서 그 노드까지, 높이는 그 노드에서 가장 먼 리프까지의 간선 수. 노드 수로 세는 교재도 있다.
• "완전 이진 트리란?" → 마지막 층을 뺀 모든 층이 꽉 차고 마지막 층은 왼쪽부터 채운 이진 트리. 배열에 빈칸 없이 담겨 힙(heap)이 쓴다.
• "중위 순회의 특징은?" → 이진 탐색 트리에서 오름차순 출력.
• "레벨 순서 순회는 어떻게 짜나요?" → 같은 층을 먼저 도므로 큐. 전위·중위·후위는 재귀로 짧게.