AVL트리
- AVL 트리란 이진 검색 트리가 항상 균형을 유지하도록 하는 대표적인 예다.
- 어떤 노드 t의 좌서브 트리(t.left) 우서브 트리(t.right)의 높이 차가 1이하이다.
- [왼쪽 서브트리 깊이 - 오른쪽 서브트리 깊이] = -1이 나온다면 균형이 맞다는 뜻이다.
- 위 성질을 만족한다면 AVL트리이다.
정상적인 AVL트리 | 정상적인 AVL트리가 아님
균형이 깨졌을 때 해결할 수 있는 유형 4가지
1. LL: t.left.left가 가장 깊을 때
2. LR: t.left.right가 가장 깊을 때
3. RR: t.right.right가 가장 깊을 때
4. RL: t.right.left가 가장 깊을 때
LL유형의 해결
- t를 기준으로 우회전하면 깊이가 같은 것을 확인할 수 있다.
LR유형의 해결
- t.left를 기준으로 좌회전해서 LL유형으로 만든 다음 t를 기준으로 우회전한다.
RR유형의 해결
- t를 기준으로 좌회전한다. LL타입과 정확히 좌우 대칭으로 동일한 원리 적용
RL유형의 해결
- t.left를 기준으로 우회전해서 RR유형으로 만든 다음 t를 기준으로 좌회전한다.
LR타입과 정확히 좌우 대칭으로 동일한 원리가 적용된다.
반응형
'자료구조' 카테고리의 다른 글
| [자료구조] 선형 큐, 원형 큐란? 자바(JAVA)로 구현하기 (11) | 2023.07.27 |
|---|---|
| [자료구조] 특수정렬 - 계수 정렬, 기수 정렬, 버킷 정렬이란? (1) | 2023.07.17 |
| [자료구조] 고급 정렬 - 병합 정렬, 퀵 정렬, 힙 정렬, 셸 정렬이란? (0) | 2023.07.16 |
| [자료구조] 버블 정렬(Bubble Sort)이란 with JAVA (0) | 2023.07.16 |
| [자료구조] 선택 정렬(Selection Sort)이란 with JAVA (0) | 2023.07.15 |
