이진트리의 수직 순회 방법

카테고리

프로그래밍/소프트웨어 개발

서브카테고리

데이터 분석

대상자

• 소프트웨어 개발자 (중급~고급 수준)
• 트리 구조 및 알고리즘에 관심 있는 개발자
• TreeMap, PriorityQueue와 같은 고급 데이터 구조 활용 방법을 배우고자 하는 개발자

핵심 요약

• 수직 순회는 노드의 수직 인덱스 (루트로부터의 수평 거리)와 레벨을 기준으로 트리를 탐색하는 방식
• TreeMap을 사용해 수직 인덱스를 자동 정렬, PriorityQueue로 동일 위치 노드의 순서 결정
• Java, Python, C++의 구현 예시에서 공통적으로 사용하는 데이터 구조: TreeMap>>

섹션별 세부 요약

1. 수직 순회 개념

• 수직 순회는 트리를 열(열) 단위로 탐색하며, 노드의 수직 인덱스와 레벨에 따라 정렬
• 예시 입력 트리:

```

/ \

1. 20

/ \

1. 7

```

• 예상 출력: [[9], [3, 15], [20], [7]]

2. 해결 방식

• 수직 인덱스와 레벨을 추적하여 노드 저장
• TreeMap으로 수직 인덱스 정렬, PriorityQueue로 동일 위치 노드의 값 비교
• 재귀적 DFS 또는 BFS 탐색을 사용하여 트리 순회

3. Java 구현 예시

• TreeMap과 PriorityQueue 활용:

```java

TreeMap>> map = new TreeMap<>();

traverse(node, map, 0, 0);

```

• 재귀 함수에서 level과 verticalIndex를 전달

4. Python 구현 예시

• defaultdict과 deque을 사용한 BFS:

```python

node_map = defaultdict(lambda: defaultdict(list))

queue = deque([(root, 0, 0)])

```

• 정렬된 수직 인덱스와 레벨 기준으로 결과 생성

5. C++ 구현 예시

• map과 multiset 활용:

```cpp

map>> nodes;

queue> q;

```

• multiset으로 노드 값 정렬

6. 시간/공간 복잡도

• 시간 복잡도: O(N log N) (TreeMap 정렬 및 PriorityQueue 연산)
• 공간 복잡도: O(N) (모든 노드를 저장)

결론

• TreeMap과 PriorityQueue의 조합이 수직 순회 문제를 효율적으로 해결
• 수직 인덱스와 레벨을 기준으로 정렬하는 것이 핵심
• Java, Python, C++에서 유사한 구조로 구현 가능하며, 관련 문제(Binary Tree Zigzag Level Order Traversal, Binary Tree Right Side View)로 연습 권장