[자료구조] 이진 탐색 트리(Binary Search Tree)

📍 이진 탐색 트리란?

• 이진 탐색 트리는 이진 트리의 일종으로, 탐색에 최적화된 트리 구조입니다.
• 이진 트리란 각 노드가 최대 두개의 자식을 가질 수 있는 트리 구조를 말합니다.

💡 이진 탐색 트리의 주요 특징

• 왼쪽 서브트리의 모든 값은 부모 노드의 값보다 작아야 한다.
• 오른쪽 서브트리의 모든 값은 부모 노드의 값보다 커야 한다.
• 각각의 서브트리 또한 이진 탐색 트리의 속성을 만족한다.
• 이 규칙을 통해 이진 탐색 트리는 데이터를 정렬된 형태로 유지하며 탐색, 삽입, 삭제와 같은 연산을 효율적으로 수행할 수 있습니다.

출처: https://yoongrammer.tistory.com/71

 

📍 이진 탐색 트리의 연산

1. 탐색 (Search) : O(log n) (평균), O(n) (최악)
   • 원하는 값을 찾을 때, 루트 노드에서 시작하여 현재 노드와 비교하면서 왼쪽 또는 오른쪽으로 이동하며 탐색합니다.
   • 트리의 균형이 잘 잡혀있는 경우, O(log n) 의 시간복잡도를 가집니다.
   • 검색 값이 없으면 null을 반환합니다.
2. 삽입 (Insertion) : O(log n) (평균), O(n) (최악)
   • 새로운 값을 삽입할 때, 해당 값이 현재 노드보다 크거나 작은지를 비교하면서 적절한 자식 노드 위치에 삽입합니다.
3. 삭제 (Deletion) : O(log n) (평균), O(n) (최악)
   • 삭제할 때도 탐색을 통해 노드를 찾고, 삭제할 노드의 자식 노드가 있는 경우 그 구조를 재배치해야 합니다.

출처: https://yoongrammer.tistory.com/71

 

📍 이진 탐색 트리 생성 예시

8, 3, 10, 1, 6, 14, 4, 7, 13

1. 값 8 삽입
   • 트리가 비어 있으므로 첫번째 값인 8을 루트 노드로 삽입
2. 값 3 삽입
   • 3은 8보다 작으므로, 8의 왼쪽 자식으로 삽입
3. 값 10 삽입
   • 10은 8보다 크므로, 8의 오른쪽 자식으로 삽입
4. 값 1 삽입
   • 1은 8보다 작고, 3보다도 작으므로, 3의 왼쪽 자식으로 삽입
5. 값 6 삽입
   • 6은 8보다 작고, 3보다 크므로, 3의 오른쪽 자식으로 삽입
6. 값 14 삽입
   • 14는 8보다 크고, 10보다 크므로, 10의 오른쪽 자식으로 삽입
7. 값 4 삽입
   • 4는 8보다 작고, 3보다 크고, 6보다 작으므로, 6의 왼쪽 자식으로 삽입
8. 값 7 삽입
   • 7은 8보다 작고, 3보다 크고, 6보다 크므로, 6의 오른쪽 자식으로 삽입
9. 값 13 삽입
   • 13은 8보다 크고, 10보다 크고, 14보다 작으므로, 14의 왼쪽 자식으로 삽입
10. 최종 이진 탐색 트리

       8
      /   \
     3     10
    / \      \
   1   6     14
      / \    /
     4   7  13