AVL 트리

AVL 트리란?

• 이진 탐색 트리 (BST)의 한 종류
• AVL 트리는 균형 이진 트리의 일종으로, 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 트리를 말한다.

AVL 트리의 특징

• 스스로 균형을 잡는 트리. 노드의 삽입과 삭제가 일어날 때마다 트리의 균형을 맞추는 작업을 수행한다.
• balance factor를 통해 균형 유지
• balance factor는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.
• balance factor가 0, 1, -1인 경우에는 균형이 잡혀있다고 하며, 2 이상이거나 -2 이하인 경우에는 균형이 깨진 상태이다.
• balance factor가 2 이상이거나 -2 이하인 경우에는 회전 연산을 통해 균형을 맞춘다.

AVL 트리의 회전 연산

• AVL 트리는 회전 연산을 통해 균형을 맞춘다.
• 회전 연산은 노드의 삽입과 삭제가 일어날 때마다 수행된다.
• 왼쪽-왼쪽(LL), 오른쪽-오른쪽(RR), 왼쪽-오른쪽(LR), 오른쪽-왼쪽(RL)의 4가지 경우가 있다.
• 회전 연산은 LL, RR, LR, RL의 4가지 경우에 따라 다르게 수행된다.

LL 회전

• LL 회전은 노드의 왼쪽 서브트리의 왼쪽에 노드가 추가되는 경우이다.
• LL 회전은 오른쪽으로 회전한다.
• LL 회전은 노드의 오른쪽 자식을 노드의 부모로 만들고, 노드의 오른쪽 자식의 왼쪽 자식을 노드의 오른쪽 자식으로 만든다.

RR 회전

• RR 회전은 노드의 오른쪽 서브트리의 오른쪽에 노드가 추가되는 경우이다.
• RR 회전은 왼쪽으로 회전한다.
• RR 회전은 노드의 왼쪽 자식을 노드의 부모로 만들고, 노드의 왼쪽 자식의 오른쪽 자식을 노드의 왼쪽 자식으로 만든다.

LR 회전

• LR 회전은 노드의 왼쪽 서브트리의 오른쪽에 노드가 추가되는 경우이다.
• LR 회전은 두 번의 회전으로 이루어진다.

RL 회전

• RL 회전은 노드의 오른쪽 서브트리의 왼쪽에 노드가 추가되는 경우이다.
• RL 회전은 두 번의 회전으로 이루어진다.

AVL 트리의 삽입 연산

• AVL 트리의 삽입 연산은 BST의 삽입 연산과 동일하다.
• 삽입 연산이 일어난 후, balance factor를 계산한다.
• balance factor가 2 이상이거나 -2 이하인 경우에는 회전 연산을 통해 균형을 맞춘다.

AVL 트리의 삭제 연산

• AVL 트리의 삭제 연산은 BST의 삭제 연산과 동일하다.
• 삭제 연산이 일어난 후, balance factor를 계산한다.
• balance factor가 2 이상이거나 -2 이하인 경우에는 회전 연산을 통해 균형을 맞춘다.

AVL 트리의 시간 복잡도

• AVL 트리의 시간 복잡도는 O(logN)이다.
• AVL 트리는 균형 이진 트리이므로, 높이가 logN이다.