13. 탐색 (sorting)
- 탐색이란?
- 정렬되지 않은 배열에서의 탐색
- 정렬된 배열에서의 탐색
- 이진 탐색 트리
- AVL 트리
2-3 트리
13.4 이진탐색 트리 (BST: Binary Search Tree)
▶ 이진탐색 vs. 이진탐색 트리
: 근본적으로 같은 원리에 의한 탐색 구조이다.
- 이진탐색(binary search): 자료들이 순차적으로 저장되어 있다. --> 삽입/삭제가 비효율적이다.
- 이진탐색 트리(binary search tree): 삽입/삭제가 빠르다. (삽입: leaf에서!)
Q. 이진탐색의 경우 자료들이 순차적으로 저장되어 있어서 삽입이 비효율적이다. 이진탐색 트리의 경우 항상 leaf에서 삽입을 하기 때문에 삽입이 효율적이다. 그런데 삭제의 경우, 이진탐색과 이진탐색 트리 모두 정렬된 배열에서 탐색한 후 삭제를 해야 하니, 그 효율성이 동일하지 않을까?
균형 이진탐색 트리 (Balanced BST)
▶ 이진탐색 트리에서의 시간 복잡도:
- 균형트리: log(n)
- 불균형트리: n -- 순차탐색과 동일하다.
--> "균형" 이진탐색 트리로 만들자!
--> AVL 트리
13.5 AVL 트리
: 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1 이하인 이진탐색트리(BST)
--> 새로운 노드가 삽입되어 트리가 불균형상태가 되면, 스스로 노드들을 재배치하여 균형상태를 유지한다.
- 시간 복잡도: log(n)
- 균형 인수(balanced factor) -- 새로 도입해야 함!
: 새로운 노드가 삽입되어 불균형상태가 되면, 서브트리를 조정하여 균형을 맞춘다.
Q. AVL 트리의 경우, 알파벳 대신 숫자를 넣어서 생각하면 편하다고 설명해주셨다.
그런데 이렇게 AVL 트리에 숫자를 넣으면, LL, LR, RR, RL의 네 가지 경우를 구분할 필요 없이, 왼쪽부터 숫자가 작은 순서대로 트리를 구성하면 되나요?
13.6 2-3 트리
출처: 이화여자대학교 이숙영교수님 자료구조
'자료구조' 카테고리의 다른 글
[자료구조] 10. 그래프(1) (0) | 2023.12.14 |
---|---|
[자료구조] 1205 (2) 14. 해싱 (1) | 2023.12.07 |
[자료구조] 1201 (2) 13. 탐색 (1) | 2023.12.06 |
[자료구조] 1201 (1) (0) | 2023.12.05 |
[자료구조] 1128 (0) | 2023.12.05 |