[TIL][Mon] AVL 트리

https://www.youtube.com/watch?v=wpaRL-WZn7c&t=410s

AVL tree

BBST(균형이진트리)의 가장 엄격한 형태의 트리 중 하나로 균형 요소(balance factor)를 1개 이하로 유지한다. 이 균형 요소는 트리의 높이(height)가 노드의 개수에 대해 로그함수적으로 상대적임을 보장한다.(Balance factor guarantees the tree's height to be logarithmic relative to the number of nodes.)

Balance Factor 균형 요소 [**]

BF란?

BF는 balanced Factor의 줄임말로, 왼쪽의 하위 트리의 높이에서 오른쪽의 하위 트리의 높이를 뺀 값을 뜻한다.

BF 계산과 균형 판별

중요한 점은 **노드의 갯수가 아닌 높이(height)**라는 점과, 모든 각각의 노드에 대해 BF의 절댓값이 1보다 작거나 같아야 이 트리는 balanced 하다, 균형이 잡힌 트리라고 말할 수 있다는 점이 핵심이다.

#Balance Factor
height of left subtree - height of right subtree

#height-balanced property
bf = hl -hr = {-1, 0, 1}
bf = | hl -hr | <= 1

if bf <= 1 : balanced
if bf > 1 : imbalanced

만약 BF의 값, 즉 어떤 노드를 기준으로 왼쪽 하위 트리의 높이와 오른쪽 하위 트리의 높이를 뺀 값이 -1, 0, 1이 아닌 다른 수가 나온다면 이건 불균형(imbalance)한 것이며, 트리는 불균형한 트리라고 말할 수 있다.

이런 불균형을 해결하기 위해 회전(rotation)을 한다.

Rotations

회전 수(count)	rotation 종류	이름	스텝
1	single rotation	LL roation	1
1	single rotation	RR rotation	1
1	double rotation	LR rotation	2
1	double rotation	RL rotation	2

핵심

• 트리의 height balance를 맞춰주는 방향으로 회전 시킨다. 언제? 트리가 생성될 때, 그리고 삽입될 때.
• 트리의 rotation은 3개의 노드(와 그 하위 트리) 사이에서만 이루어진다. 즉, unbalanced가 된 노드를 기준으로, 해당 노드를 포함하여 3개의 노드와 그것의 자식(child) 노드, 그리고 자손(grandson) 노드까지만 생각한다. 왜냐하면 그 아래(gradson의 child, grandson…)는 어디에 오든지 imbalanced 된 노드에게 큰 영향을 끼치지 못하기 때문이다.

Insertion

https://www.geeksforgeeks.org/insertion-in-an-avl-tree/

Deletion

https://www.geeksforgeeks.org/deletion-in-an-avl-tree/

 

직접 구현을 시도했는데 오류가 났다. 디버깅은 좀 시간이 걸려서 수제작 코드는 일단 보류… 조금 더 공부하고 올려볼 예정.

 

~ RB Tree와의 연관성~

BST가 정렬된 상태에서 O(logN)이지만 최악의 경우 O(N)의 시간복잡도를 가지는데, 이 격차를 극복하고자 BBST, 그중에서도 self-balancing tree인 AVL 트리와 Red-Black 트리가 등장함.

 

	AVL Tree	Red-Black Tree
핵심개념	balance factor, rotations	coloring, properties
비교해서?	more balanced, more rotations	faster i/d operation
균형 연산	엄격하여 회전이 더 잦음	느슨하여 회전이 잦진 않음
탐색 연산	rb트리보다 더 균형이 잡혀있기에 평균적으로 약간 더 빠르다.
	하지만 두 트리 모두 O(log N)의 시간복잡도를 가지기에 이 차이는 크지 않다.
삽입/삭제 연산		rb 트리가 더 적은 회전과 재균형 연산이 덜 필요하기 때문에 일반적으로 더 빠르다.
	그러나 이 두 구조 모두 최악의 시간복잡도는 O(log N)이다.
어떨 때 쓸까?	시스템이 잦은 탐색과 적은 갱신이 예정되어있다면 AVL 트리가 balancing의 정도가 높아 좀 더 효율적이다. /	시스템이 잦은 삽입과 삭제 연산이 수반되는 데이터 업데이트가 있을 에정이라면 rb트리가 갱신 후 덜 엄격한 규제를 보이기 때문에 효율적이다. / memory allocation…
하지만..!	둘 다 self-balanced tree로 삽입 시 rebalancing의 과정을 거치며, 두 구조 모두 균형탐색트리를 위한 효율적인 선택이 가능케 하는 모든 연산이 로그함수적인 시간 동안 수행될 수 있음을 보장한다.