중위 순회(Inorder Traversal)
중위 순회(Inorder Traversal)는 트리 자료구조, 특히 이진 트리를 탐색하는 세 가지 기본적인 방법(전위, 중위, 후위) 중 하나이다. 이 순회 방식은 특유의 방문 순서 때문에 특별한 의미와 활용 가치를 지니고 있다.
왼쪽 서브트리를 먼저 방문한 후 현재 노드를 방문하고 마지막으로 오른쪽 서브트리를 방문하는 이 방법은 정렬된 데이터가 필요한 다양한 문제에 활용된다.
이진 검색 트리에서 중위 순회를 수행하면 노드 값이 오름차순으로 방문되는 특성은 검색, 삽입, 삭제, 범위 쿼리 등 많은 작업에서 핵심적인 역할을 한다. 또한 표현식 트리에서 중위 표기법을 생성하거나 트리의 유효성을 검사하는 데에도 널리 사용된다.
재귀적 구현이 가장 간단하고 직관적이지만, 스택을 사용한 반복적 구현이나 모리스 순회와 같은 최적화된 알고리즘을 통해 성능과 공간 효율성을 개선할 수 있다.
중위 순회의 기본 개념
중위 순회는 이진 트리를 탐색할 때 다음과 같은 순서로 노드를 방문하는 방법이다:
- 왼쪽 서브트리를 중위 순회한다.
- 현재 노드(루트)를 방문한다.
- 오른쪽 서브트리를 중위 순회한다.
“중위(Inorder)“라는 이름은 현재 노드가 왼쪽과 오른쪽 서브트리 “사이(in order)“에 방문된다는 의미를 담고 있다. 이 순회 방식은 깊이 우선 탐색(DFS)의 한 형태로, 트리의 가장 왼쪽 노드부터 시작하여 점차 오른쪽으로 이동하는 특성을 가진다.
중위 순회의 알고리즘
아래 이진 트리를 예로 들어 중위 순회 과정을 단계별로 살펴보면:
중위 순회 순서: 4 → 2 → 5 → 1 → 6 → 3 → 7
이 순서를 단계별로 설명하면:
- 가장 왼쪽 경로를 따라 내려가 노드 4에 도달한다.
- 노드 4를 방문한다 (왼쪽 자식이 없음).
- 노드 4의 부모인 노드 2로 돌아가 방문한다.
- 노드 2의 오른쪽 자식인 노드 5를 방문한다.
- 노드 5의 부모의 부모인 노드 1로 돌아가 방문한다.
- 노드 1의 오른쪽 서브트리로 이동하여 노드 6, 3, 7을 순서대로 방문한다.
중위 순회(Inorder Traversal)의 과정은 다음과 같다.
- D 방문 (B의 왼쪽 자식) → 출력:
D - B 방문 (B의 루트) → 출력:
D B - E 방문 (B의 오른쪽 자식) → 출력:
D B E - A 방문 (A의 루트) → 출력:
D B E A - C 방문 (A의 오른쪽 자식) → 출력:
D B E A C - F 방문 (C의 오른쪽 자식) → 출력:
D B E A C F
재귀적 구현
중위 순회의 재귀적 구현은 직관적이고 간결하다:
| |
실행결과
| |
반복적(비재귀적) 구현
스택을 사용한 반복적 구현도 가능하다:
| |
실행 결과
| |
이 알고리즘은 먼저 현재 노드부터 시작하여 왼쪽 자식 노드를 따라 내려가며 모든 노드를 스택에 추가한다.
그런 다음 스택에서 노드를 꺼내서 방문하고, 오른쪽 자식으로 이동하여 프로세스를 반복한다.
다양한 트리 구조에서의 중위 순회
이진 검색 트리(Binary Search Tree)
이진 검색 트리는 각 노드에 대해 왼쪽 서브트리의 모든 노드 값이 현재 노드보다 작고, 오른쪽 서브트리의 모든 노드 값이 현재 노드보다 큰 특성을 가진 이진 트리이다.중위 순회 순서: 1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14
이진 검색 트리에서 중위 순회를 수행하면 노드 값이 정렬된 순서로 방문된다. 이 특성은 정렬된 배열이 필요한 많은 알고리즘에서 활용된다.
편향 트리(Skewed Tree)
한쪽으로만 자식 노드가 있는 트리이다.왼쪽 편향 트리:
중위 순회 순서: 4 → 3 → 2 → 1
오른쪽 편향 트리:
중위 순회 순서: 1 → 2 → 3 → 4
완전 이진 트리(Complete Binary Tree)
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 채워진 트리이다.중위 순회 순서: 4 → 2 → 5 → 1 → 6 → 3
중위 순회의 활용 사례
이진 검색 트리 검증
이진 검색 트리의 유효성을 검사할 때 중위 순회가 유용하다.
중위 순회 결과가 오름차순으로 정렬되어 있다면 유효한 이진 검색 트리이다.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20def is_valid_bst(root): prev = [float('-inf')] # 이전 값을 추적하기 위한 리스트 def inorder(node): if not node: return True # 왼쪽 서브트리 검사 if not inorder(node.left): return False # 현재 노드 값 검사 if node.value <= prev[0]: return False prev[0] = node.value # 오른쪽 서브트리 검사 return inorder(node.right) return inorder(root)중위 표기법 생성
표현식 트리에서 중위 순회를 수행하면 중위 표기법(infix notation)의 수식을 얻을 수 있다.
중위 표기법은 우리가 일상적으로 사용하는 수식 표기법이다(예: a + b * c).중위 순회 결과: a + b * c
이진 검색 트리에서의 검색, 삽입, 삭제
이진 검색 트리에서 중위 순회는 정렬된 데이터를 얻는 데 사용된다.
이는 범위 쿼리(range query)나 정렬된 데이터가 필요한 작업에 유용하다.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20def kth_smallest(root, k): """이진 검색 트리에서 k번째로 작은 요소를 찾습니다.""" count = [0] result = [None] def inorder(node): if not node or count[0] >= k: return inorder(node.left) count[0] += 1 if count[0] == k: result[0] = node.value return inorder(node.right) inorder(root) return result[0]모리스 중위 순회(Morris Inorder Traversal)
모리스 순회는 추가 공간을 사용하지 않고(O(1) 공간 복잡도) 트리를 순회하는 고급 기법이다.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 26def morris_inorder_traversal(root): result = [] current = root while current: if not current.left: # 왼쪽 자식이 없으면 현재 노드를 방문하고 오른쪽으로 이동 result.append(current.value) current = current.right else: # 중위 순회에서 현재 노드의 선행자(왼쪽 서브트리에서 가장 오른쪽 노드) 찾기 predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right if not predecessor.right: # 선행자의 오른쪽이 없으면 현재 노드로 연결하고 왼쪽으로 이동 predecessor.right = current current = current.left else: # 선행자의 오른쪽이 현재 노드를 가리키면 그 연결을 끊고 현재 노드를 방문한 후 오른쪽으로 이동 predecessor.right = None result.append(current.value) current = current.right return result이 알고리즘은 트리의 구조를 일시적으로 수정하여 스택이나 재귀 없이 순회를 가능하게 한다.
중위 순회의 시간 및 공간 복잡도
시간 복잡도
중위 순회는 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)이다. 여기서 n은 트리의 노드 수이다.공간 복잡도
- 재귀적 구현: 재귀 호출 스택의 크기는 트리의 높이 h에 비례하므로 공간 복잡도는 O(h)이다. 최악의 경우(편향 트리)에는 O(n)이 될 수 있다.
- 반복적 구현: 명시적 스택을 사용하는 경우에도 공간 복잡도는 O(h)이다. 마찬가지로 최악의 경우에는 O(n)이 될 수 있다.
- 모리스 순회: 추가 공간을 사용하지 않으므로 공간 복잡도는 O(1)이다.
중위 순회와 다른 순회 방법 비교
중위 순회 vs 전위 순회(Preorder Traversal)
- 중위 순회: 왼쪽 → 루트 → 오른쪽
- 전위 순회: 루트 → 왼쪽 → 오른쪽
전위 순회는 루트 노드를 먼저 방문하므로 트리의 복제나 전위 표기법 생성에 유용하다.
중위 순회 vs 후위 순회(Postorder Traversal)
- 중위 순회: 왼쪽 → 루트 → 오른쪽
- 후위 순회: 왼쪽 → 오른쪽 → 루트
후위 순회는 자식 노드를 먼저 방문한 후 부모 노드를 방문하므로 트리 삭제나 후위 표기법 생성에 유용하다.
중위 순회 vs 레벨 순회(Level Order Traversal)
- 중위 순회: 깊이 우선(DFS) 방식으로 왼쪽 가지를 먼저 완전히 탐색한다.
- 레벨 순회: 너비 우선(BFS) 방식으로 각 레벨의 노드를 순서대로 방문한다.
레벨 순회는 트리의 레벨별 특성을 분석하거나 최단 경로 문제에 유용합니다.
실제 코드 예제: 이진 트리의 중위 순회 구현
아래는 Python으로 이진 트리 노드 클래스와 중위 순회 메서드를 구현한 예제:
| |
중위 순회의 응용 문제
이진 검색 트리의 두 노드 값 교환 복구
이진 검색 트리에서 두 노드의 값이 실수로 교환되었을 때, 트리를 복구하는 문제이다.
중위 순회를 사용하면 값이 정렬되지 않은 노드를 찾을 수 있다.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 27def recover_bst(root): first = second = prev = None def inorder(node): nonlocal first, second, prev if not node: return # 왼쪽 서브트리 순회 inorder(node.left) # 현재 노드 검사 if prev and prev.value > node.value: if not first: first = prev second = node prev = node # 오른쪽 서브트리 순회 inorder(node.right) inorder(root) # 발견한 두 노드의 값 교환 first.value, second.value = second.value, first.value중위 순회 결과로부터 트리 재구성
중위 순회의 결과와 전위 순회의 결과가 주어졌을 때, 원래 이진 트리를 재구성하는 문제이다.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16def build_tree(inorder, preorder): if not inorder or not preorder: return None # 전위 순회의 첫 번째 요소는 루트 root_value = preorder[0] root = TreeNode(root_value) # 중위 순회에서 루트의 위치 찾기 root_index = inorder.index(root_value) # 왼쪽 서브트리와 오른쪽 서브트리로 분할 root.left = build_tree(inorder[:root_index], preorder[1:1+root_index]) root.right = build_tree(inorder[root_index+1:], preorder[1+root_index:]) return root
중위 순회의 고급 응용
중위 순회를 사용한 이진 트리 균형 검사
이진 검색 트리가 균형 잡혀 있는지 검사하는 방법 중 하나는 중위 순회를 사용하는 것이다.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18def is_balanced(root): balanced = [True] def get_height(node): if not node or not balanced[0]: return 0 left_height = get_height(node.left) right_height = get_height(node.right) # 왼쪽과 오른쪽 서브트리의 높이 차이가 1보다 크면 균형이 맞지 않음 if abs(left_height - right_height) > 1: balanced[0] = False return max(left_height, right_height) + 1 get_height(root) return balanced[0]중위 순회를 사용한 스레드 이진 트리(Threaded Binary Tree) 구현
스레드 이진 트리는 null 포인터를 사용하는 대신 중위 순회에서 선행자나 후속자를 가리키는 “스레드"를 사용하여 공간을 절약하는 특수한 이진 트리이다.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 32class ThreadedTreeNode: def __init__(self, value=0): self.value = value self.left = None self.right = None self.is_threaded_right = False # 오른쪽 포인터가 스레드인지 여부 def create_inorder_threaded_tree(root): if not root: return prev = [None] def inorder(node): if not node: return # 왼쪽 서브트리 순회 inorder(node.left) # 이전 노드의 오른쪽이 없으면 현재 노드를 가리키는 스레드 생성 if prev[0] and not prev[0].right: prev[0].right = node prev[0].is_threaded_right = True prev[0] = node # 오른쪽 서브트리 순회 if not node.is_threaded_right: inorder(node.right) inorder(root)
트리 순회의 실제 응용 사례
컴파일러에서의 표현식 파싱
컴파일러에서 중위 표기법으로 작성된 표현식을 파싱할 때 중위 순회가 사용된다.
표현식은 구문 분석 트리(parse tree)로 변환된 후, 중위 순회를 통해 원래 표현식을 재구성하거나 다른 표기법으로 변환할 수 있다.데이터베이스 인덱싱
B-트리나 B+ 트리와 같은 자기 균형 이진 검색 트리는 데이터베이스 시스템의 인덱싱에 널리 사용된다.
이러한 트리의 중위 순회는 정렬된 순서로 레코드를 검색하는 데 사용된다.기계 학습에서의 결정 트리
결정 트리 알고리즘에서 트리 구조를 시각화하거나 규칙을 추출할 때 중위 순회가 사용될 수 있다.
중위 순회의 변형
역중위 순회(Reverse Inorder Traversal)
역중위 순회는 오른쪽 서브트리를 먼저 방문한 후 현재 노드를 방문하고 마지막으로 왼쪽 서브트리를 방문한다. 이진 검색 트리에서 역중위 순회를 수행하면 노드 값이 내림차순으로 방문된다.대칭 중위 순회(Symmetric Inorder Traversal)
대칭 중위 순회는 트리의 대칭성을 검사하는 데 사용된다. 왼쪽 서브트리는 중위 순회로, 오른쪽 서브트리는 역중위 순회로 방문하여 결과를 비교한다.1 2 3 4 5 6 7 8 9 10 11 12 13 14 15def is_symmetric(root): if not root: return True def is_mirror(left, right): if not left and not right: return True if not left or not right: return False return (left.value == right.value and is_mirror(left.left, right.right) and is_mirror(left.right, right.left)) return is_mirror(root.left, root.right)
중위 순회를 사용한 실제 문제 해결 예시
이진 검색 트리의 범위 합(Range Sum)
주어진 범위 [low, high] 내에 있는 이진 검색 트리의 모든 노드 값의 합을 구하는 문제.
| |
이 문제는 중위 순회의 특성을 활용하여 효율적으로 해결할 수 있다.
불필요한 서브트리 탐색을 피하기 위해 현재 노드 값을 범위와 비교하여 조건부로 탐색한다.