AVL 트리: 두 판 사이의 차이

IT 위키
편집 요약 없음
9번째 줄: 9번째 줄:
* B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림
* B 트리 등과 함께 균형잡힌 트리(height-balanced tree)라고도 불림


== 균형 인수 ==
균형 인수(Balance Factor, BF)는 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이를 의미한다.
{| class="wikitable"
|+균형 인수의 의미
!균형 인수 (BF)!!트리 상태
|-
| -1, 0, 1||균형 상태 (Balanced)
|-
|< -1 또는 > 1||불균형 상태 (Unbalanced, 회전 필요)
|}
== 회전 동작 ==
== 회전 동작 ==
=== 개요 ===
=== 개요 ===
26번째 줄: 36번째 줄:
* LL 회전
* LL 회전
[[파일:AVL RR Rotation.png|600px]]
[[파일:AVL RR Rotation.png|600px]]
== 구현 코드 ==
=== Python ===
<syntaxhighlight lang="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):
        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)
       
        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)
        # LL 회전
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)
        # RR 회전
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)
        # LR 회전
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)
        # RL 회전
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)
        return root
# AVL 트리 테스트
avl = AVLTree()
root = None
for key in [10, 20, 30, 40, 50, 25]:
    root = avl.insert(root, key)
</syntaxhighlight>


== 같이 보기 ==
== 같이 보기 ==
{{틀:데이터베이스 인덱스 트리}}
{{틀:데이터베이스 인덱스 트리}}

2025년 2월 13일 (목) 08:25 판

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 회전 동작

3.1 개요

AVL Rotation.gif

  • LL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽으로 회전
  • LR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽-오른쪽으로 회전
  • RL 회전: A 로부터 N 까지의 경로상의 노드들을 오른쪽-왼쪽으로 회전
  • RR 회전: A 로부터 N 까지의 경로상의 노드들을 왼쪽으로 회전

3.2 동작 예시

  • RR 회전

AVL LL Rotation.png

  • LR 회전

AVL LR Rotation.png

  • RL 회전

AVL RL Rotation.png

  • LL 회전

AVL RR Rotation.png

4 구현 코드

4.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):
        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)
        
        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)

        # LL 회전
        if balance > 1 and key < root.left.key:
            return self.right_rotate(root)

        # RR 회전
        if balance < -1 and key > root.right.key:
            return self.left_rotate(root)

        # LR 회전
        if balance > 1 and key > root.left.key:
            root.left = self.left_rotate(root.left)
            return self.right_rotate(root)

        # RL 회전
        if balance < -1 and key < root.right.key:
            root.right = self.right_rotate(root.right)
            return self.left_rotate(root)

        return root

# AVL 트리 테스트
avl = AVLTree()
root = None
for key in [10, 20, 30, 40, 50, 25]:
    root = avl.insert(root, key)

5 같이 보기