[자료구조] 트리(Tree) 시리즈 3: 이진 탐색 트리(Binary Search Tree)란?

이진탐색 트리(BST)란?

• 모든 노드가 아래와 같은 특정 순서를 따르는 속성이 있는 이진 트리다
• 각 노드는 최대 두 개의 자식 노드를 가진다
• 왼쪽 서브트리의 모든 노드는 현재 노드보다 작은 값을 가진다
• 오른쪽 서브트리의 모든 노드는 현재 노드보다 큰 값을 가진다
• 중복된 노드가 없어야 한다.

---

BST의 주요 연산 (조회, 삽입, 삭제) 및 시간 복잡도

조회 (Search)

• 평균 시간 복잡도: O(log n)
• 최악의 경우 (불균형 트리): O(n)

삽입 (Insertion)

• 평균 시간 복잡도: O(log n)
• 최악의 경우 (불균형 트리): O(n)

삭제 (Deletion)

• 평균 시간 복잡도: O(log n)
• 최악의 경우 (불균형 트리): O(n)

---

BST의 균형과 불균형 문제

• BST의 성능은 트리의 균형에 크게 의존한다. 균형 잡힌 BST는 대부분의 연산에서 O(log n)의 시간 복잡도를 보장하지만, 불균형 BST는 최악의 경우 O(n)의 시간 복잡도를 가질 수 있다.

예를 들어, 정렬된 순서로 데이터를 삽입하면 (1, 2, 3, 4, 5) 트리가 한쪽으로 치우치게 되어 연결 리스트와 유사한 형태가 된다.
이를 해결하기위해 균형 탐색 트리를 구현한다.

---

BST 최적화 기법 (균형 트리)

• BST의 불균형 문제를 해결하기 위한 여러 기법들이 있다:

1. AVL 트리: 삽입과 삭제 시 자동으로 균형을 맞추는 자가 균형 이진 탐색 트리다.
2. 레드-블랙 트리: 각 노드에 색깔을 부여하여 균형을 유지하는 자가 균형 이진 탐색 트리다.

---

실제 응용 사례

• 데이터베이스 인덱싱
• 파일 시스템 구현
• 구간 탐색
• 우선순위 큐 구현

---

참고

윤성우의 열혈 자료구조 : 네이버 도서

---