[알고리즘] 11. 이진 탐색 트리

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

1) 이진 탐색 트리의 개념

• 이진 트리의 한 형태로, 노드가 유일한 키값을 가짐.

• 왼쪽 서브트리는 부모 노드보다 작은 값, 오른쪽 서브트리는 부모 노드보다 큰 값을 가짐.

• 탐색 시 루트 노드부터 시작하여 왼쪽 또는 오른쪽 서브트리를 따라가며 진행.

• 삽입, 삭제, 탐색이 빈번한 경우 효율적.

 

2) 이진 탐색 트리의 삽입

• 새로운 데이터를 삽입할 위치를 루트부터 탐색.

• 루트보다 작으면 왼쪽, 크면 오른쪽으로 이동하며 적절한 위치에 삽입.

 

3) 이진 탐색 트리의 삭제

• 삭제할 노드를 탐색한 후, 삭제 유형에 따라 재구성 필요.

 

(1) 단말 노드 삭제 (차수 = 0)

• 부모 노드의 연결을 끊어 삭제.

 

(2) 하나의 자식 노드를 가진 노드 삭제 (차수 = 1)

• 삭제 후 자식 노드를 부모 노드와 연결.

 

(3) 두 개의 자식 노드를 가진 노드 삭제 (차수 = 2)

• 왼쪽 서브트리에서 가장 큰 값 또는 오른쪽 서브트리에서 가장 작은 값을 삭제 노드 위치로 이동.

 

4) 이진 탐색 트리의 탐색 시간 복잡도

• 최악의 경우: O(n) (편향된 트리일 때)

• 평균적인 경우: O(log n) (균형 잡힌 트리일 때)

 

5) 결론

• 이진 탐색 트리의 탐색 효율은 트리의 균형과 밀접한 관계가 있음.

• 최악의 경우를 방지하려면 AVL 트리와 같은 균형 트리 기법이 필요.

• 삽입과 삭제가 빈번한 경우 유용한 자료구조.

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.