AVL 트리
IT 위키
- Adelson-Velskii and Landis Tree
- 트리내 각각의 노드마다 1 이하의 균형치(Balance Factor, +1,0,1)를 가지기 위해, 삽입과 삭제를 할때마다 균형치를 검사하여 RR, LL, LR, RL 회전연산을 시행하는 이진탐색트리
- 발표자인 1962년 G.M. Adelson-Velskii와 E.M. Landis 가 그들의 이름을 따서 명명
1 특징[편집 | 원본 편집]
- 한 노드를 중심으로 좌우 종속 트리의 높이 차가 1 이하인 균형 잡힌 트리
- 이진 트리의 삽입·삭제 과정에서 한 방향으로 치우치거나, 높이 차이로 인해서 수행 시간이 증가되는 것을 막기 위해 균형 유지
- B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림
2 균형 인수[편집 | 원본 편집]
균형 인수(Balance Factor, BF)는 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 의미한다.
| 균형 인수 (BF) | 트리 상태 |
|---|---|
| -1, 0, 1 | 균형 상태 (Balanced) |
| < -1 또는 > 1 | 불균형 상태 (Unbalanced, 회전 필요) |
3 기본 동작[편집 | 원본 편집]
삽입 동작
- 기본적인 바이너리 트리의 삽입 동작과 동일하다
- 루트부터 대소관계를 따라가서 마지막 Leaf Node로 삽입이 된다.
- 삽입 후 불균형이 생기면 리밸런싱 한다.
삭제 동작
- Leaf Node라면 그냥 삭제한다.
- 자식 노드가 있다면 아래 두 가지 중 선택 가능하다.
- 오른쪽 서브트리에서 가장 작은 노드가 올라온다. (따로 정의된 바 없다면 이게 가장 기본)
- 왼쪽 서브트리에서 가장 큰 노드가 올라온다.
- 삭제 후 불균형이 생기면 리밸런싱 한다.
4 회전 동작[편집 | 원본 편집]
헷갈릴 수 있으니 주의!
불균형 케이스와 회전 동작 간에 명칭이 상당히 헷갈릴 수 있다. 예를 들어 LL 케이스(Left-Left 불균형 케이스)에서는 Right Rotation이 일어난다. 불균형 케이스는 Left-Right, Left-Left, Right-Right와 같이 L과 R의 조합인데, 하필 Right Rotation, Left Rotation도 L과 R의 조합이라 "LL 회전"과 같이 혼란스러운 용어가 나오는 것이다.
- LL 회전, RR 회전이라는 말은 없다. 이 말을 잘못 쓰는 경우는 아래와 같은 경우이다.
- Left 회전을 잘못 표기하는 경우
- LL 케이스에서 이루어지는 회전을 줄여서 표기한 경우 (실제로는 이 경우 Right Roation이 일어난다.)
- 아래 예시들에서 "개요"의 gif는 맞는 용어를 사용하고 있지만 그 아래 "동작 예시"엔 영어 그림상의 표기에 오류가 있으니 주의!
4.1 개요[편집 | 원본 편집]
- L-L 케이스: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전
- L-R 케이스: A 로부터 N 까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전
- R-L 케이스: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전
- R-R 케이스: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전
4.2 동작 예시[편집 | 원본 편집]
- RR(Right-Right 케이스) - 왼쪽 회전(Left Rotation)
- 자식들이 오른쪽에 치우쳐 있을 때 왼쪽 회전이 일어난다.
- 왼쪽 회전이란 노드가 왼쪽(시계 반대 방향)으로 이동하는 경우이다.
- 또는 오른쪽의 자식이 왼쪽위의 루트로 올라오는 것이라고 생각할 수도 있다.
- 아래 그림에서 LL Rotation이라는 말은 잘못되었다. 그냥 Left Rotation이라고 하는 게 맞다.
- LR(Left-Right 케이스) - 왼쪽 회전 후
- RL 회전
- LL 회전
5 구현 코드[편집 | 원본 편집]
5.1 Python[편집 | 원본 편집]
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def get_height(self, node):
return node.height if node else 0
def get_balance(self, node):
# 특정 노드를 기준으로 왼쪽 높이 - 오른쪽 높이를 반환한다.
# 1보다 크면 왼쪽으로 과중된 것이고 -1보다 작으면 반대이다.
# 노드가 없으면 0을 반환한다.
return self.get_height(node.left) - self.get_height(node.right) if node else 0
def right_rotate(self, z):
y = z.left
T3 = y.right
y.right = z
z.left = T3
z.height = max(self.get_height(z.left), self.get_height(z.right)) + 1
y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
return y
def left_rotate(self, z):
y = z.right
T2 = y.left
y.left = z
z.right = T2
z.height = max(self.get_height(z.left), self.get_height(z.right)) + 1
y.height = max(self.get_height(y.left), self.get_height(y.right)) + 1
return y
def insert(self, root, key):
if not root:
return Node(key)
# 재귀적으로 호출되다 위의 "root가 없는경우"까지 반복된다.
if key < root.key:
root.left = self.insert(root.left, key)
else:
root.right = self.insert(root.right, key)
root.height = max(self.get_height(root.left), self.get_height(root.right)) + 1
balance = self.get_balance(root)
if balance > 1 and key < root.left.key:
return self.right_rotate(root)
if balance < -1 and key > root.right.key:
return self.left_rotate(root)
if balance > 1 and key > root.left.key:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance < -1 and key < root.right.key:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def min_value_node(self, node):
current = node
while current.left:
current = current.left
return current
def delete(self, root, key):
if not root:
return root
if key < root.key:
root.left = self.delete(root.left, key)
elif key > root.key:
root.right = self.delete(root.right, key)
else:
if not root.left:
return root.right
elif not root.right:
return root.left
temp = self.min_value_node(root.right)
root.key = temp.key
root.right = self.delete(root.right, temp.key)
if not root:
return root
root.height = max(self.get_height(root.left), self.get_height(root.right)) + 1
balance = self.get_balance(root)
if balance > 1 and self.get_balance(root.left) >= 0:
return self.right_rotate(root)
if balance > 1 and self.get_balance(root.left) < 0:
root.left = self.left_rotate(root.left)
return self.right_rotate(root)
if balance < -1 and self.get_balance(root.right) <= 0:
return self.left_rotate(root)
if balance < -1 and self.get_balance(root.right) > 0:
root.right = self.right_rotate(root.right)
return self.left_rotate(root)
return root
def lookup(self, root, key):
if not root or root.key == key:
return root
if key < root.key:
return self.lookup(root.left, key)
return self.lookup(root.right, key)
def pre_order(self, root):
if root:
print(root.key, end=" ")
self.pre_order(root.left)
self.pre_order(root.right)
# AVL 트리 테스트
avl = AVLTree()
root = None
for key in [10, 20, 30, 40, 50, 25]:
root = avl.insert(root, key)
print("Preorder traversal after insertions:")
avl.pre_order(root)
print("\n")
# Lookup test
search_key = 25
found_node = avl.lookup(root, search_key)
print(f"Lookup {search_key}: {'Found' if found_node else 'Not found'}")
# Deleting a node
delete_key = 20
root = avl.delete(root, delete_key)
print(f"\nPreorder traversal after deleting {delete_key}:")
avl.pre_order(root)
print("\n")
