일반적인 이진탐색트리의 경우, O(log n)의 시간복잡도를 보장하지 않습니다. skewed tree는 검색, 삽입, 삭제 모든 연산에서 O(n)의 수행시간을 갖고, complete tree는 검색은 트리의 높이에 따라 수행시간이 빠를 수 있지만, 삽입과 삭제 연산에서는 트리의 모양을 유지해줘야 하기 때문에 O(n)의 시간복잡도를 가질 수밖에 없기 때문입니다.
이를 보안하기 위해 고안된 이진탐색트리가 바로 ! BST ( Balanced Search Tree) 인데요, 모든 연산에서 O(log n)의 수행복잡도를 갖는다는 것이 장점입니다. 이 글에서는 BST 중 AVL Tree에 대해 다뤄보도록 하겠습니다.
BST는 모든 노드의 좌우 서브트리 높이의 차가 0또는 1인 균형트리입니다. 대표적인 BST가 AVL-Tree 입니다.
Concept
: 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 BST를 유지하는 트리
※ 연산을 수행할 때마다 노드의 좌우 서브트리 높이를 계산하는 것은 AVL트리를 구현하는 데 무의미하다. (시간복잡도 O(n) ) 따라서 각각의 노드는 항상 자신의 높이를 기억하고 있어야 한다.
Property
- height - balance property
ADT
<AVL Tree 시간복잡도>
| find(k) | O(log n) |
| put(k) | O(log n) |
| erase(k) | O(log n) |
1. Search
- 탐색방식은 일반적인 이진탐색트리와 동일하다.
- leaf노드에 도달할 때까지 탐색
- 최악의 경우 h O(log n)-time
- 재구조화 필요 x
2. Insertion
- 삽입방식은 이진탐색 방식과 동일하다.
- leaf노드에 도달하면 해당 위치가 삽입위치
- 삽입 후 height - balance 위반 노드를 찾는 것이 중요 . 삽입 후 높이가 변화되었을 가능성이 있기 때문에!
- 탐색 → 삽입 → BST 최초 위반노드 탐색 → 재구조화O(1) = O(log n)- time
- Trinode Restructuring (재구조화)
- O(1) - time 에 수행하는 것이 관건
3. Removal
- 제거방식은 이진탐색트리 방식과 동일하다.
- 제거된 노드는 빈 leaf노드가 된다.
- 재구조화하면, height는 항상!! 감소한다.→ rebalancing 필요 (삽입연산과의 차이)
'Major S-T-U-D-Y > Data Structure' 카테고리의 다른 글
| Heap(힙) 자료구조 (0) | 2024.07.16 |
|---|---|
| Priority Queue(우선순위 큐)와 리스트기반 구현 (0) | 2024.07.16 |
| Binary Search Tree(이진탐색트리) (0) | 2024.07.12 |
| Linked List 기본 코드 정리 (0) | 2024.05.22 |
