---

이진 탐색 트리(Binary Search Tree)

---

1. 이진 탐색 트리

• 이진탐색 + 연결리스트

• 이진탐색 : 탐색에 소요되는 시간복잡도 O(logN)이지만 삽입/삭제 불가능하다.

• 연결리스트 : 삽입/삭제의 시간복잡도 O(1)이지만 탐색하는 시간복잡도가 O(N)이다.

• 효율적인 탐색 능력 + 자료의 삽입/삭제 가능

2. 특징

• 각 노드의 자식은 2개 이하이다.

• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.

• 중복된 노드가 없어야 한다.

cf) 중복이 없어야 하는 이유
-> 검색이 목적인 자료구조로써 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요는 없다.
-> 노드에 count 값을 가지게 하여 처리하는 것이 훨씬 효율적이다.

• 이진 탐색 트리(BST)의 순회는 중위순회(in-order) 방식이다.

3. BST 핵심연산

• 검색
• 삽입
• 삭제
• 트리 생성
• 트리 삭제

4. 시간 복잡도

• 균등 트리 : O(logN)

• 편향 트리 : O(N)

• 삽입, 검색, 삭제의 시간복잡도는 트리의 depth에 비례한다.

5. 삭제할 때

1. 자식이 없는 leaf 노드일 때
   -> 그냥 삭제한다.

2. 자식이 1개인 노드일 때
   -> 지워진 노드에 자식을 올린다.

3. 자식이 2개인 노드일 때
   -> 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값을 올린다.