AVL 트리 개념과 특징

AVL 트리란?

이진 탐색 트리(BST)의 한 종류

스스로 균형(balancing)을 잡는 트리

balance factor(BF)를 통해 균형 유지

 

노드의 balance factor란?

임의의 노드 x에 대해서
BF(x) = h(lSubtree(x)) - h(rSubtree(x))
BF = balance factor, h = height, lSubtree = left subtree, rSubtree = right subtree

 

 

AVL의 트리의 특징

balance factor가 -1, 0, 1 셋 중 하나의 값을 가짐.

트리에 삽입 혹은 삭제 후 BF(x)가 -1, 0, 1이 아니라면 노드가 생기면 균형을 맞추는 작업을 수행!

 

 

AVL 동작 방식

🟨 오른쪽 오른쪽으로 편향된 상태

중간값을 위로 올림.

(왼쪽으로 rotate 시킴)

 

🟨 왼쪽 왼쪽으로 편향된 상태

중간값을 위로 올림.

(오른쪽으로 rotate 시킴)

 

🟨 오른쪽 왼쪽으로 편향된 상태

중간 값을 제일 위로 올림.

(중간값과 제일 큰 값을 오른쪽으로 회전 후 중간값과 제일 작은 값을 왼쪽으로 회전)

 

🟨 왼쪽 오른쪽으로 편향된 상태

중간 값을 제일 위로 올림.

(중간값과 제일 큰 값을 왼쪽으로 회전 후 중간값과 제일 큰 값을 오른쪽으로 회전)

 

삽입/삭제가 발생한 위치에서 루트 노드를 거꾸로 올라오면서 BF를 확인하여 균형이 깨졌다면 재조정을 해준다.

 

	best	avg	worst
insert	O(1)	O(logN)	O(logN)
delete	O(1)	O(logN)	O(logN)
search	O(1)	O(logN)	O(logN)

N = 트리의 노드 수

 

엄격하게 균형을 유지하기 때문에 삽입/삭제 시 트리 균형을 확인하고 만약 균형이 깨졌다면 트리 구조를 재조정하기 때문에 이때 시간이 꽤 소요된다

➡️ 이 문제를 해결한 것이 Red-Black 트리!