1. AVL 트리란?
균형 트리 중 하나
| AVL 특징 | |
| BF | 밸런스 팩터 Balance Factor |
| 특정 노드의 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이의 절대값 | |
| BF가 2이상이 되지 않는 트리 |
| 구현(삽입) | |
| 우회전 | 부모 노드의 오른쪽 자식을 조부모 노드로 변경 |
| 조부모 노드의 왼쪽 자식을 원래 부모의 오른쪽 자식으로 변경 | |
| 좌회전 | 부모 노드의 왼쪽 자식을 조부모 노드로 변경 |
| 조부모 노드의 오른쪽 자식을 원래 부모의 왼쪽 자식으로 변경 |
| LL | 우회전 |
| LR | 부모을 기준으로 좌회전 후 다시 우회전 |
| RR | 좌회전 |
| RL | 부모를 기준으로 우회전 후 다시 좌회전 |
'bootcamp > Java' 카테고리의 다른 글
| 1211 동적프로그래밍 (1) | 2023.12.22 |
|---|---|
| 1208 정렬 (1) | 2023.12.22 |
| 1206 Red Black Tree (0) | 2023.12.22 |
| 1206 B-Tree (1) | 2023.12.22 |
| 1206 트리 (0) | 2023.12.22 |
