이진 트리 순회와 BST 편향
전위·중위·후위를 문제 유형에 붙여 외우기
순회 순서만 외우면 문제 앞에서 다시 헷갈린다. 전위는 복사, 중위는 정렬 출력, 후위는 삭제·계산으로 붙여 두고, 배열 표현과 인접 리스트의 갈림길, BST가 O(N)으로 무너지는 조건까지.
트리 순회는 “전위-중위-후위” 순서만 외우면 정작 문제 앞에서 어느 걸 써야 할지 다시 헷갈린다. 이 글에서는 순회를 문제 유형에 붙여서 기억하는 방식으로 정리한 과정을 이야기하려 한다 — 트리 표현 방식(배열 vs 인접 리스트)을 고르는 기준과, BST가 한쪽으로 치우칠 때 탐색이 O(N)으로 무너지는 지점까지 함께 다룬다.
트리 — 표현 방식과 순회, 그리고 BST의 함정
트리는 비선형 자료구조로 계층적 데이터를 표현한다. 순회는 세 가지를 구분한다 — 전위는 루트-왼-오, 중위는 왼-루트-오, 후위는 왼-오-루트 순서다. 처음에는 순서를 그냥 외우려고 했는데, “이 순회가 어떤 문제에 쓰이는가”와 연결하니 훨씬 정리가 쉬웠다. 특히 중위 순회는 BST(이진 탐색 트리)에서 정렬된 순서를 뽑아내는 것과 직결된다는 점이 와닿았다.
같은 BST를 세 방식으로 순회한 결과. 전위는 루트-왼-오, 후위는 왼-오-루트, 중위는 왼-루트-오라서 결과가 오름차순으로 정렬된다.
구현 관점에서는 두 가지 표현을 비교했다. 배열 기반은 완전이진트리 형태에서 인덱스 계산이 단순하고, 인접리스트 기반은 일반 트리나 희소 구조에 유연하다.
1
2
vector<vector<int>> tree(n+1);
tree[parent].push_back(child);
BST는 현재 노드를 기준으로 작은 값은 왼쪽, 큰(또는 크거나 같은) 값은 오른쪽에 배치하는 규칙으로 동작한다. 균형이 잡혀 있으면 탐색/삽입/삭제가 빠르지만, 한쪽으로 편향되면 성능이 리스트 수준까지 떨어질 수 있다.
| 연산 | 평균 | 최악 |
|---|---|---|
| 탐색 | O(log N) | O(N) |
| 삽입 | O(log N) | O(N) |
| 삭제 | O(log N) | O(N) |
복습으로 할 것:
- 전위/중위/후위 순회 템플릿 손코딩 1회
- BST 삽입+탐색 미니 문제 1개 풀이
핵심 요약 — 트리 순회는 순서 암기가 아니라 문제 목적과 연결해서 이해해야 한다. 중위 순회가 BST의 정렬 순서 추출과 직결된다는 것, 그리고 BST는 편향되면 최악 O(N)까지 떨어진다는 것이 핵심이다.