[파이썬] AVL 트리의 개념과 균형 조정

01 Sep 2023

python

AVL 트리는 균형 이진 검색 트리의 일종으로, 삽입 및 삭제 연산 시 트리의 균형을 유지하여 검색 연산의 시간 복잡도를 최소화한다. AVL 트리는 높이 균형 조건을 만족시키기 위해 회전 연산을 통해 트리를 조정한다.

AVL 트리의 개념

AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1 이하인 이진 검색 트리이다. 이러한 트리 구조를 유지하기 위해 삽입이나 삭제 연산 시에는 균형 조정이 필요하다.

각 노드는 키(key), 왼쪽 서브트리(left), 오른쪽 서브트리(right), 높이(height) 정보를 가지고 있다. 키는 노드의 값을 나타내며, 왼쪽 서브트리와 오른쪽 서브트리는 해당 노드보다 작은 값과 큰 값들을 담고 있다. 높이는 해당 노드를 루트로 하는 서브트리의 높이를 나타내며, 비어있는 리프 노드의 높이는 -1로 설정된다.

AVL 트리의 균형 조정

AVL 트리의 균형을 유지하기 위해 삽입이나 삭제 연산 시에는 회전 연산을 통해 트리를 조정한다. 회전 연산은 두 가지 유형으로 구분된다:

왼쪽 회전(left rotation): 오른쪽 서브트리가 왼쪽에 더 높은 경우
오른쪽 회전(right rotation): 왼쪽 서브트리가 오른쪽에 더 높은 경우

이러한 회전 연산을 통해 트리의 균형을 조정하고, 트리의 높이를 최소화하여 검색 연산의 시간 복잡도를 O(log n)으로 유지한다.

Python으로 AVL 트리 구현하기

아래는 Python에서 AVL 트리를 구현하는 간단한 예제이다.

class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def insert(self, root, key):
        # BST 삽입
        if root is None:
            return Node(key)
        elif key < root.key:
            root.left = self.insert(root.left, key)
        else:
            root.right = self.insert(root.right, key)

        # 높이 업데이트
        root.height = 1 + max(self.get_height(root.left), self.get_height(root.right))

        # 균형 조정
        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 left_rotate(self, z):
        y = z.right
        T2 = y.left

        y.left = z
        z.right = T2

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def right_rotate(self, z):
        y = z.left
        T3 = y.right

        y.right = z
        z.left = T3

        z.height = 1 + max(self.get_height(z.left), self.get_height(z.right))
        y.height = 1 + max(self.get_height(y.left), self.get_height(y.right))

        return y

    def get_height(self, root):
        if root is None:
            return 0
        return root.height

    def get_balance(self, root):
        if root is None:
            return 0
        return self.get_height(root.left) - self.get_height(root.right)

위 코드는 Node 클래스와 AVLTree 클래스를 정의하고, insert 메서드를 통해 AVL 트리의 삽입 연산을 구현한다. 또한, 각 노드의 높이와 균형을 확인하기 위해 get_height와 get_balance 메서드를 추가로 구현했다.

이제 위 코드를 기반으로 AVL 트리를 생성하고, 삽입 연산을 통해 트리를 구성할 수 있다.

avl_tree = AVLTree()
root = None

# 키 값을 순서대로 삽입
root = avl_tree.insert(root, 10)
root = avl_tree.insert(root, 20)
root = avl_tree.insert(root, 30)
root = avl_tree.insert(root, 40)
root = avl_tree.insert(root, 50)
root = avl_tree.insert(root, 25)

# 삽입 후, AVL 트리의 구조 확인
print("AVL 트리의 구조:")
avl_tree.print_tree(root)

위 코드를 실행하면 삽입된 키 값에 따라 구성된 AVL 트리의 구조를 확인할 수 있다.

AVL 트리는 검색, 삽입, 삭제의 시간 복잡도가 모두 O(log n)이므로, 실제로 활용하기에 매우 효율적이다. 따라서 데이터의 동적인 관리가 필요한 상황에서 AVL 트리의 개념과 구현 방법을 잘 이해하여 활용하면 좋다.