[자료구조] - 이진 탐색 트리

1. 이진 탐색 트리(Binary Search Tree)

• 이진 탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 그러나 삽입 삭제 불가능
• 연결리스트 : 삽입 삭제의 시간 복잡도는 O(1), 그러나 탐색하는 시간 복잡도가 O(N)
  이 두가지를 합하여 장점을 모두 얻는 것이 이진탐색트리
• 즉 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게!

2. 특징

• 각 노드의 자식이 2개 이하
• 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큼.
• 이진 탐색트리의 순회는 중위순회
• 중복 노드가 없어야 함.

  검색이 목적인데, 중복이 많은 경우 트리 사용 안함.
  트리에 삽입하는 것보다, 노드에 count 값을 가지게 하여 처리

3. 이진탐색트리 핵심 연산

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

4. 시간 복잡도

• 균등 트리 : 노드 개수가 N개 -> O(logN)
• 편향 트리 : 노드 개수가 N개 -> O(N)
  삽입, 삭제, 검색 시간 복잡도는 트리의 Depth 비례

5. 삭제의 3가지 case

1. 자식이 없는 leaf노드 -> 그냥 삭제
2. 자식이 1개 -> 지워진 노드에 자식 올리기
3. 자식이 2개 -> 오른쪽 자식 노드에서 가장 작은 값 or 왼쪽 자식 노드에서 가장 큰 값 올리기