(7) 이진탐색트리

■ 이진 탐색트리

1) 정의 :

> Linked list

- O(1) 삽입 / 삭제

- O(N) 탐색 복잡도

 

> Binary Search

- 자료구조가 sorting되어있는 상태에서 시행

- O(logN) 탐색 복잡도

 

※ 위 두개의 장점을 합친 방식으로 자료구조를 짠 것이

'이진 탐색 트리'

 

2) 이진탐색 트리 특징

(a) 각 노드의 자식이 2개 이하

(b) 완전이진트리 구조는 아님!!

    - 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 같거나 큼

(c) 중복노드 많은 경우 - 다른 자료구조 사용하는 것이 효율적

(d) 평균시간복잡도 O(log(N))

    편향 트리인 경우 O(N)에 가까워 짐 → 트리가 왼쪽 / 오른쪽으로 쏠려있는 경우

 

3) 트리 변경의 3가지 case

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

---

참조 :

gyoogle.dev/blog/computer-science/data-structure/Binary%20Search%20Tree.html

이진탐색트리 (Binary Search Tree) | 👨🏻‍💻 Tech Interview