[자료구조] 1205 (1)

13. 탐색 (sorting)

1. 탐색이란?
2. 정렬되지 않은 배열에서의 탐색
3. 정렬된 배열에서의 탐색
4. 이진 탐색 트리 
5. AVL 트리
6. 2-3 트리

 

---

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

▶ 이진탐색 vs. 이진탐색 트리

: 근본적으로 같은 원리에 의한 탐색 구조이다.

• 이진탐색(binary search): 자료들이 순차적으로 저장되어 있다. --> 삽입/삭제가 비효율적이다.
• 이진탐색 트리(binary search tree): 삽입/삭제가 빠르다. (삽입: leaf에서!)

Q. 이진탐색의 경우 자료들이 순차적으로 저장되어 있어서 삽입이 비효율적이다. 이진탐색 트리의 경우 항상 leaf에서 삽입을 하기 때문에 삽입이 효율적이다. 그런데 삭제의 경우, 이진탐색과 이진탐색 트리 모두 정렬된 배열에서 탐색한 후 삭제를 해야 하니, 그 효율성이 동일하지 않을까?

교수님 답변!

 

균형 이진탐색 트리 (Balanced BST)

▶ 이진탐색 트리에서의 시간 복잡도:

• 균형트리: log(n)
• 불균형트리: n -- 순차탐색과 동일하다.

균형트리 vs. 불균형트리

--> "균형" 이진탐색 트리로 만들자!

--> AVL 트리

 

---

13.5 AVL 트리

: 모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차가 1 이하인 이진탐색트리(BST)

--> 새로운 노드가 삽입되어 트리가 불균형상태가 되면, 스스로 노드들을 재배치하여 균형상태를 유지한다.

• 시간 복잡도: log(n)
• 균형 인수(balanced factor) -- 새로 도입해야 함!

AVL 트리 vs. 비 AVL 트리

 

AVL 트리의 삽입 전/후

: 새로운 노드가 삽입되어 불균형상태가 되면, 서브트리를 조정하여 균형을 맞춘다.

 

서브트리를 조정하여 균형을 맞추는 방법: 4가지

Q. AVL 트리의 경우, 알파벳 대신 숫자를 넣어서 생각하면 편하다고 설명해주셨다.

그런데 이렇게 AVL 트리에 숫자를 넣으면, LL, LR, RR, RL의 네 가지 경우를 구분할 필요 없이, 왼쪽부터 숫자가 작은 순서대로 트리를 구성하면 되나요?

교수님 답변!

 

 

AVL 트리 구축 - 예

 

 

---

13.6 2-3 트리

2-3 트리

 

---

 

 

 

 

 

출처: 이화여자대학교 이숙영교수님 자료구조