알고리즘 심화: 트리 순회와 이진 탐색 트리(BST)

2024-12-26|

1 min read

트리 구조의 데이터를 모든 노드를 방문하는 세 가지 순회 방식과, 효율적인 검색을 가능하게 하는 이진 탐색 트리의 원리를 정리합니다.

1. 트리 순회 (Tree Traversal)

트리의 모든 노드를 중복 없이 한 번씩 방문하는 과정입니다. 방문 순서에 따라 세 가지로 나뉩니다.

전위 순회 (Preorder): 루트 → 왼쪽 → 오른쪽 (트리 복사나 구조 파악에 유용)
중위 순회 (Inorder): 왼쪽 → 루트 → 오른쪽 (이진 탐색 트리에서 오름차순 정렬 결과 제공)
후위 순회 (Postorder): 왼쪽 → 오른쪽 → 루트 (폴더 삭제 등 하위 노드부터 처리가 필요할 때 사용)

2. 이진 탐색 트리 (Binary Search Tree, BST)

이진 트리의 일종으로, 탐색을 위해 다음과 같은 규칙을 가집니다.

왼쪽 서브트리: 현재 노드보다 작은 값들만 존재
오른쪽 서브트리: 현재 노드보다 큰 값들만 존재

🔹 주요 특징 및 성능

탐색 효율: 균형이 잘 잡힌 경우
text
```
O(log n)
```
의 성능을 보여 배열의 선형 탐색(
text
```
O(n)
```
)보다 훨씬 빠릅니다.
단점: 데이터가 한쪽으로 치우쳐 삽입될 경우(편향 트리), 성능이
text
```
O(n)
```
으로 떨어지는 문제가 있습니다. 이를 해결하기 위해 레드-블랙 트리 같은 균형 트리(Balanced Tree)가 등장했습니다.