자료 구조 - Chapter 12
탐색의 이해2
이진 트리의 단점
저장 순서에 따라 탬색의 성능에 큰 차이를 보인다.
따라서 이러한 단점을 해결한 트리를 가리켜 '균형 잡힌 이진트리'라고 한다.
- AVL 트리
- 2 - 3 트리
- 2 - 3 - 4 트리
- Red - Black 트리
- B 트리
AVL 트리 (AVL Tree)
AVL 트리는 G.M.Adelson-Velskii와 E.M.Landis에 의해 고안되었다.
AVL트리는 토드가 추가될 때, 그리고 삭제될 때 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여
균형을 잡는다.
균형 인수(Balance Factor)
AVL 트리가 균형을 잡기 위해 지표로 사용하는 것
균형 인수 = 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이
AVL 트리는 균형 인수의 절대값이 2 이상인 경우에 균형을 잡기 위한 트리의 재조정을 진행한다.
리밸런싱(Rebalancing)
- LL 회전
- LR 회전
- RL 회전
- RR 회전
RL 및 RR회전의 경우 한번의 회전을 통해 LL 또는 RR 상태로 바꾸어 접근하면 해결하기 편리하다.
예제 : AVL트리 구현하기
기존에 제작한 BinarySearchTree에 Rebalance함수를 추가하여 자료를 삽입하고 삭제할 때 마다
트리의 균형에 신경쓴다.
