AVL Tree

• Binary Search Tree의 속성을 가짐
• 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1
• 삽입, 삭제, 검색 시 시간복잡도는 O(logN), N은 노드의 개수
• Node는 key, left node pointer, right node pointer, height 로 구성

Balance Factor

• 균형을 파악할 때 활용
• BF(k) = k의 왼쪽 서브트리의 높이 - k의 오른쪽 서브트리의 높이 (-1, 0, 1 중 하나)

Rotation

• RR, Right Rotation : 회전의 기준이 되는 노드가 오른쪽으로 감.
• LR, Left Rotation : 회전의 기준이 되는 노드가 왼쪽으로 감.

Case

LL(Left Left) Case : 중심 노드를 기준으로 왼쪽에 노드가 깊이 있는 경우 -> RR을 수행하여 균형을 맞춤

RR(Right Right) Case : 중심 노드를 기준으로 오른쪽에 노드가 깊이 있는 경우 -> LR을 수행하여 균형을 맞추

LR(Left Right) Case : 중심 노드의 왼쪽과 왼쪽 아래 오른쪽 자식 노드가 있는 경우 -> LR 이후 RR 수행

RL(Right Left) Case : 중심 노드의 오른쪽과 오른쪽 아래 왼쪽 자식 노드가 있는 경우 -> RR 이후 LR 수행

 

References

https://yoongrammer.tistory.com/72

[자료구조] AVL 트리(Tree)

https://code-lab1.tistory.com/61

[자료구조] AVL트리란? AVL트리 쉽게 이해하기, AVL트리 시뮬레이터