AVL 트리 (Adelson-Velskii and Landis tree)

AVL트리

 

#정의: 편향트리일 경우 이진탐색트리(Binary Search Tree)의 탐색속도 저하되는 단점을 보완하기 위한 높이균형트리

 

높이차, 즉 Balance Factor의 절대값이 1이하가 아니기 때문에 회전해서 균형을 맞추는 겁니다. 

 - 각각의 노드마다 균형치가 +-1 이하힌 height balancd Tree를 위해 균형치를 검사하여 회전연산을 시행하는 자료구조

 

#균형인수(Balance Factor(BF) : 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이

 >> AVL트리는 모든 노드의 균형인수가 =-1 이하

- BF > +-2 >> 4가지 방식으로 회전수행, 트리 전체를 재배열하지 않아도 균형유지(장점)

 

# AVL 트리에서 균형이 깨지는 경우 4가지 >> 회전(Rotation) 으로 자동으로 균형을 맞춤

- LL 타입 : Left 서브트리의 Left에 신규 노드 삽입 >> 경로상의 노드를 오른방향으로 회전

- RR 타입 : Right 서브트리의 Right에 신규 노드 삽입 >> 경로상의 노드를 왼쪽방향으로 회전

- LR 타입 : Left 서브트리의 Right에  신규 노드 삽입 >> 경로상 노드의 왼쪽방향 및 오른쪽반향 회전 수행

- RL 타입 : Right 서브트리의 Left에 신규 노드 삽입 >>  경로상 노드의 오른방향 및 왼쪽방향 회전수행

 

#응용분야: 이진탐색트리 사용분야 모두 가능, 컴퓨터 디렉토리 구조등의 계층구조