AVL 트리
AVL(Adelson-Velsky And Landis) 트리는 스스로 균형 잡는 이진 탐색 트리로 삽입과 삭제 시 트리의 균형도를 계산하여 불균형을 완화하는 트리이다.
- AVL 트리는 균형도만 존재한다.
- 균형도가 절댓값 2 이상이면 불균형 트리이다.
- 균형도를 계산한 후 트리의 회전 여부를 판단하여 불균형할 경우 LL, RR, LR, RL 회전을 한다.
- null 노드인 경우 높이는 -1, 노드가 존재할 경우 노드의 높이는 Max(좌측 자식 노드 높이, 우측 자식 노드 높이) +1
- 균형도 = 좌측 자식 노드 높이 - 우측 자식 노드 높이
- 균형도가 양수인 경우 좌측 서브 트리가 비대한 트리, 음수인 경우 우측 서브 트리가 비대한 트리
- Leaf노드는 항상 높이와 균형도가 0이다.
LL 불균형 트리
부모의 균형도가 양수(2)이고 좌측 자식 노드의 균형도가 0 또는 1인 경우
< LL 회전 >
- LL 문제를 해결하기 위해 노드를 회전 시켜 균형도를 맞추는 것
RR 불균형 트리
부모의 균형도가 -2이고 우측 자식 노드의 균형도가 0 또는 -1인 경우
< RR 회전 >
LR 불균형 트리
부모의 균형도가 2이고 좌측 자식 노드의 균형도가 음수(-1)인 경우
< LR 회전 >
- 먼저 RR 문제를 해결 후 LL 문제를 해결
RL 불균형 트리
부모의 균형도가 음수(-2)이고 우측 자식 노드의 균형도가 양수(1)인 경우
< RL 회전 >
- 먼저 LL 문제를 해결 후 RR 문제를 해결
참조
https://www.codelatte.io/topics
'6. 자료구조 & 알고리즘 > 6-1. 자료구조' 카테고리의 다른 글
자료구조 - [ Binary Heap ] (0) | 2022.08.23 |
---|---|
자료구조 - [ Red-Black 트리 ] (0) | 2022.08.18 |
자료구조 - [ 이진 탐색 트리 ] (0) | 2022.08.10 |
자료구조 - [ 이진 트리 순회 ( 깊이 우선 / 너비 우선 ) ] (0) | 2022.08.10 |
자료구조 - [ 재귀 - 점화식 관점 / 분할 관점 / 백트래킹 관점 ] (0) | 2022.08.08 |