이진 탐색 트리: 효율적인 데이터 탐색의 핵심 알고리즘

데이터베이스의 핵심 자료구조 중 하나인 '이진 탐색 트리' 에 대해 알아보려합니다. 데이터의 세계에서 효율적인 탐색은 굉장히 중요한데, 그 중에 하나의 주요 탐색 방식인 이진 탐색 트리는 그 중심 역할을 하고 있습니다. 

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

컴퓨터 과학에서 사용하는 자료구조로, 각 노드는 최대 두 개의 자식 노드를 가질 수 있으며, 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 값을 가집니다. 이진 탐색 트리의 특성상 중위 순회 (in-order traversal)를 하면 정렬된 순서로 데이터를 방문할 수 있습니다. 이진 탐색 트리는 검색, 삽입, 삭제 등의 연산을 로그 시간 내에 수행할 수 있도록 설계되었습니다.

 

이진 탐색의 기본원리

숫자 데이터가 0~99,999까지 있을 때 내가 찾고자 하는 데이터를 찾기 위해 몇번의 탐색이 필요할까요?  log₂(100,000)는 대략 16.6이므로, 최대 17번의 탐색으로 0~99,999 사이의 숫자를 찾을 수 있습니다. 아래에서 예시로 설명드리겠지만 스무고개와 비슷한 형식으로 "당신이 생각한 숫자는 49,999보다 크거나 같나요?" 라는 질문을 던지며 해당 노드의 값을 찾아갑니다. 

이진트리

---

37,988이라는 숫자를 이진 탐색 트리를 통해 어떻게 찾아가는지  아래와 같이 예시를 들겠습니다.
실제 예시 : 37,988 노드 찾기

1. 질문: 숫자는 49,999보다 크거나 같나요?  
답변: 아니오 범위: 0~49,998(왼쪽 서브트리)

2. 질문: 숫자는 24,999보다 크거나 같나요? 
답변: 예 범위: 25,000~49,998(오른쪽 서브트리)

3. 질문: 숫자는 37,499보다 크거나 같나요?
답변: 예 범위: 37,500~49,998(오른쪽 서브트리)

4. 질문: 숫자는 43,749보다 크거나 같나요? 
답변: 아니오 범위: 37,500~43,748(왼쪽 서브트리)

5. 질문: 숫자는 40,624보다 크거나 같나요? 
답변: 아니오 범위: 37,500~40,623(왼쪽 서브트리)

6. 질문: 숫자는 39,061보다 크거나 같나요? 
답변: 아니오 범위: 37,500~39,060(왼쪽 서브트리)

7. 질문: 숫자는 38,280보다 크거나 같나요? 
답변: 아니오 범위: 37,500~38,279(왼쪽 서브트리)

8. 질문: 숫자는 37,889보다 크거나 같나요? 
답변: 예 범위: 37,890~38,279(오른쪽 서브트리)

9. 질문: 숫자는 38,084보다 크거나 같나요? 
답변: 아니오 범위: 37,890~38,083(왼쪽 서브트리)

10. 질문: 숫자는 37,986보다 크거나 같나요? 
답변: 예 범위: 37,987~38,083(오른쪽 서브트리)

11. 질문: 숫자는 38,035보다 크거나 같나요? 
답변: 아니오 범위: 37,987~38,034(왼쪽 서브트리)

12. 질문: 숫자는 38,010보다 크거나 같나요? 
답변: 아니오 범위: 37,987~38,009(왼쪽 서브트리)

13. 질문: 숫자는 37,998보다 크거나 같나요? 
답변: 아니오 범위: 37,987~37,997(왼쪽 서브트리)

14. 질문: 숫자는 37,992보다 크거나 같나요? 
답변: 아니오 범위: 37,987~37,991(왼쪽 서브트리)

15. 질문: 숫자는 37,989보다 크거나 같나요? 
답변: 아니오 범위: 37,987~37,988(왼쪽 서브트리)

16. 질문: 숫자는 37,988인가요?
답변: 예(탐색완료)

이진 탐색은 위 예시처럼 값을 비교하며 왼쪽 또는 오른쪽 자식 노드로 이동하며 37,988 노드의 값을 찾아갑니다. 이진 탐색 트리의 구조 덕분에 매번 절반의 데이터를 탐색 대상에서 제외시키며 탐색 범위를 좁혀나가며 빠르게 원하는 값을 찾아낼 수 있게 됩니다.

이상으로 블로그 포스팅을 마치겠습니다.