레벨 순서 순회 (Level Order Traversal)#
트리 자료구조에서 레벨 순서 순회(Level Order Traversal)는 트리의 각 레벨을 위에서 아래로, 각 레벨 내에서는 왼쪽에서 오른쪽으로 노드를 방문하는 방식이다.
이 순회 방식은 너비 우선 탐색(Breadth-First Search, BFS)의 일종으로 볼 수 있다.
레벨 순서 순회는 트리를 레벨별로 탐색하는 강력한 기법이다.
큐를 사용한 반복적 접근법이 가장 효율적인 구현 방식이며, 다양한 트리 문제를 해결하는 데 활용할 수 있다.
특히 트리의 구조적 특성을 분석하거나 레벨별 작업을 수행할 때 매우 유용하다.
레벨 순서 순회의 개념#
트리에서 레벨이란 루트 노드로부터의 거리를 의미한다:
- 레벨 0: 루트 노드
- 레벨 1: 루트 노드의 자식 노드들
- 레벨 2: 레벨 1 노드들의 자식 노드들
- 이런 식으로 계속된다.
레벨 순서 순회는 모든 레벨 0 노드(루트)를 방문한 다음, 모든 레벨 1 노드, 모든 레벨 2 노드… 식으로 진행된다.
레벨 순서 순회의 구현 방법#
레벨 순서 순회를 구현하는 가장 일반적인 방법은 큐(Queue) 자료구조를 사용하는 것이다.
알고리즘은 다음과 같다:
- 루트 노드를 큐에 넣는다.
- 큐가 비어있지 않은 동안:
- 큐에서 노드를 하나 꺼낸다.
- 해당 노드를 방문(처리)한다.
- 해당 노드의 모든 자식 노드를 큐에 넣는다(보통 왼쪽에서 오른쪽 순서로).
파이썬으로 구현한 레벨 순서 순회#
다음은 이진 트리에서의 레벨 순서 순회를 파이썬으로 구현한 예시:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrderTraversal(root):
if not root:
return []
result = [] # 결과를 저장할 리스트
queue = deque([root]) # 큐 초기화: 루트 노드로 시작
while queue:
level_size = len(queue) # 현재 레벨의 노드 수
current_level = [] # 현재 레벨의 노드 값들을 저장
for _ in range(level_size):
node = queue.popleft() # 큐에서 첫 번째 노드를 꺼냄
current_level.append(node.val) # 현재 노드 값을 현재 레벨 리스트에 추가
# 왼쪽 자식이 있으면 큐에 추가
if node.left:
queue.append(node.left)
# 오른쪽 자식이 있으면 큐에 추가
if node.right:
queue.append(node.right)
result.append(current_level) # 현재 레벨의 노드 값들을 결과 리스트에 추가
return result
# 트리 생성 예시:
# 1
# / \
# 2 3
# / \ \
# 4 5 6
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.right = TreeNode(6)
# 레벨 순서 순회 실행
print(levelOrderTraversal(root)) # 출력: [[1], [2, 3], [4, 5, 6]]
|
이 코드는 각 레벨의 노드들을 별도의 하위 리스트로 구분하여 반환한다.
출력 결과인 [[1], [2, 3], [4, 5, 6]]는 레벨 0에 노드 1, 레벨 1에 노드 2와 3, 레벨 2에 노드 4, 5, 6이 있음을 보여준다.
레벨 순서 순회의 활용#
레벨 순서 순회는 다음과 같은 상황에서 유용하다:
- 트리의 너비 계산: 각 레벨의 노드 수를 세어 트리의 최대 너비를 계산할 수 있다.
- 트리의 높이 계산: 레벨 순서 순회로 방문한 레벨의 수가 트리의 높이가 된다.
- 특정 레벨의 노드 찾기: 특정 레벨의 모든 노드를 쉽게 식별할 수 있다.
- 이진 트리가 완전 이진 트리(Complete Binary Tree)인지 확인: 레벨 순서 순회를 사용하여 빈 자리가 있는지 검사할 수 있다.
다른 구현 방식: 재귀를 사용한 레벨 순서 순회#
재귀를 사용하여 레벨 순서 순회를 구현할 수도 있다:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| def levelOrderTraversalRecursive(root):
if not root:
return []
result = []
def height(node):
if not node:
return 0
return max(height(node.left), height(node.right)) + 1
def getCurrentLevel(node, level):
if not node:
return
if level == 1:
result.append(node.val)
elif level > 1:
getCurrentLevel(node.left, level - 1)
getCurrentLevel(node.right, level - 1)
h = height(root)
for i in range(1, h + 1):
getCurrentLevel(root, i)
return result
# 위의 트리 예시를 사용하여 실행
print(levelOrderTraversalRecursive(root)) # 출력: [1, 2, 3, 4, 5, 6]
|
이 재귀 방식은 모든 노드 값을 단일 리스트로 반환하며, 시간 복잡도는 O(n²)로 큐를 사용한 방식(O(n))보다 효율성이 떨어진다.
시간 복잡도와 공간 복잡도#
큐를 사용한 레벨 순서 순회의 경우:
- 시간 복잡도: O(n), 여기서 n은 트리의 노드 수. 각 노드는 정확히 한 번씩 방문됩니다.
- 공간 복잡도: O(w), 여기서 w는 트리의 최대 너비. 이진 트리의 경우 최악의 경우 O(n/2), 즉 O(n)이 됩니다.
재귀를 사용한 레벨 순서 순회의 경우:
- 시간 복잡도: O(n²), 트리의 높이가 h일 때 각 레벨마다 O(n)의 작업을 수행하기 때문.
- 공간 복잡도: O(h), 재귀 호출 스택의 최대 깊이는 트리의 높이.
참고 및 출처#