AVL 트리란?

[kkosang]

AVL 트리란?

균형 이진 트리의 한 종류로 탐색 시간을 O(log n)을 유지합니다.

AVL 트리의 특징

• 이진 탐색 트리의 속성
• 높이 차이가 최대 1
• 회전을 통해 균형을 맞춤
• 삽입,삭제,탐색 시간이 O(log n)

불균형 판단 기준

Balance Factor를 사용하여 균형을 판단합니다.
BF(K) = K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이

BF(K) = -1,0,1인 경우 균형 상태를 유지합니다.
BF(K)가 -1 미만이거나 1을 초과하는 경우 트리의 불균형으로 회전을 통해 균형을 맞춥니다.

회전 유형

회전에는 4가지 유형이 있습니다.

LL ( Left-Left)

• 불균형이 발생한 노드를 오른쪽으로 회전합니다.

RR (Right-Right)

• 불균형이 발생한 노드를 왼쪽으로 회전합니다.

LR (Left-Right)

• 불균형이 발생한 노드의 왼쪽 자식을 왼쪽으로 회전합니다.
• 불균형이 발생한 노드를 오른쪽으로 회전합니다.

RL (Right-Left)

• 불균형이 발생한 노드의 오른쪽 자식을 오른쪽으로 회전합니다.
• 불균형이 발생한 노드를 왼쪽으로 회전합니다.