Data structures (with python) - 8.Tree - 8.5 Balanced Tree

Data structures (with python) - 8.Tree - 8.5 Balanced Tree

 

💡 A balanced binary tree, also referred to as a height-balanced binary tree, is defined as a binary tree in which the height of the left and right subtree of any node differ by not more than 1.

높이-균형 이진 트리라고도 하는 균형 이진 트리는 모든 노드의 왼쪽과 오른쪽 하위 트리의 높이가 1 이하로 차이가 나는 이진 트리로 정의됩니다.

 

균형트리(Balanced Tree)에 대해 알아봅시다.

 

균형 트리는 모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 최대 1인 특징을 가지고 있습니다.

이렇게 균형을 유지하게 되면, 트리의 높이를 최소화하여 탐색, 삽입, 삭제 등의 연산을 빠르게 수행할 수 있습니다.

이러한 균형 트리의 예로는 AVL 트리, 레드-블랙 트리 등이 있습니다.

 

In Python

AVL 트리를 예로 파이썬에서 밸런스드 트리를 만들어 보겠습니다.

(AVL 트리는 자체 균형을 유지하는 이진 탐색 트리의한 종류입니다.)

 

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

class AVLTree:
    def __init__(self):
        self.root = None

    def insert(self, key):
        # 코드 생략...

    def delete(self, key):
        # 코드 생략...

    def search(self, key):
        # 코드 생략...

    # 추가적인 메소드(회전, 높이 계산, 균형 계산 등)...

이런 형식으로 구현됩니다.

 

생략된 부분을 정말 예시를 들어본다면,

삽입 (insert) 메소드를 먼저 예시로 들어 보겠습니다.

def insert(self, root, key):
    if not root:
        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.getHeight(root.left),
                          self.getHeight(root.right))

    balance = self.getBalance(root)

    if balance > 1:
        if key < root.left.key:
            return self.rightRotate(root)
        else:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

    if balance < -1:
        if key > root.right.key:
            return self.leftRotate(root)
        else:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

    return root

위코드에서 먼저 이진탐색트리의 삽입 연산을 수행한 뒤,

높이를 갱신하고 균형을 확인합니다.

if balance 를 통해 균형이 꺠지는 경우,

적절한 연산을 수행하여 균형을 복원합니다.

 

삭제(delete)

def delete(self, root, key):
    if not root:
        return root

    elif key < root.key:
        root.left = self.delete(root.left, key)

    elif key > root.key:
        root.right = self.delete(root.right, key)

    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = self.getMinValueNode(root.right)
        root.key = temp.key
        root.right = self.delete(root.right,
                                  temp.key)

    if root is None:
        return root

    root.height = 1 + max(self.getHeight(root.left),
                          self.getHeight(root.right))

    balance = self.getBalance(root)

    if balance > 1:
        if self.getBalance(root.left) >= 0:
            return self.rightRotate(root)
        else:
            root.left = self.leftRotate(root.left)
            return self.rightRotate(root)

    if balance < -1:
        if self.getBalance(root.right) <= 0:
            return self.leftRotate(root)
        else:
            root.right = self.rightRotate(root.right)
            return self.leftRotate(root)

    return root

 

1. 먼저 삭제할 키를 가진 노드를 찾습니다.

이때 키가 루트 노드의 키보다 작으면 왼쪽 서브트리에서 찾고, 크면 오른쪽 서브트리에서 찾습니다.

(elif key )

 

2. 키를 찾았다면, 해당 노드륵 삭제합니다.

- 삭제할 노드가 자식 노드가 없는 경우: 그냥 삭제

- 삭제할 노드가 한 개의 자식 노드를 가지는 경우 : 삭제할 노드를 그 자식 노드로 대체

- 삭제할 노드가 두 개의 자식 노드를 가지는 경우 : 삭제할 노드의 오른쪽 서브트리에서 가장 작은 값을 가진 노드

(즉, 오른쪽 서브트리의 가장 왼쪾 노드)를 찾아서 삭제할 노드의 위치에 놓고, 그 노드를 오른쪽 서브트리에서 삭제합니다.

 

3. 노드를 삭제한 후에는 높이를 갱신, 균형을 확인합니다.

균형이 깨지는 경우, 적절한 회전 연산을 수행하여 균형을 복원합니다.

회전연산은 삽입연산 때와 마찬가지로, 균형이 꺠진 노드의 상태에 따라 결정됩니다.

 

 

AVL 트리를 나타내는 클래스를 알아보았습니다.

이러한 균형 트리는 탐색, 삽입, 삭제연산을 빠르게 수행할수 있어 다양한 알고리즘과 프로그램에서 사용합니다.

예로, DB 시스템에서 빠른 탐색 속도를 보장하기위해 이러한 균형 트리를 활용합니다.

 

 

 

Appendix

회전연산이 뭔데?

 

균형 트리를 설명할때 탐색후 균형이 안맞으면 회전연산을 통하여 균형을 복구한다고 말하였습니다.

회전연산은 뭘까요?

 

회전 연산은 AVL 트리가 균형을 유지하기 위해 사용하는 연산입니다. 

AVL 트리에서는 삽입이나 삭제 연산이 이루어질 때마다 트리의 균형을 확인하고, 필요한 경우 회전 연산을 수행하여 균형을 복원합니다. 이때 회전은 크게 왼쪽 회전과 오른쪽 회전, 그리고 이를 조합한 왼쪽-오른쪽 회전과 오른쪽-왼쪽 회전으로 나눌 수 있습니다.

왼쪽 회전: 노드의 오른쪽 자식이 부모가 되고, 원래의 노드는 그 자식의 왼쪽 자식이 됩니다. 이 연산은 노드의 오른쪽 서브트리의 높이가 너무 높아져 균형이 깨졌을 때 사용하며, 이를 통해 오른쪽 서브트리의 높이를 줄일 수 있습니다.

오른쪽 회전: 노드의 왼쪽 자식이 부모가 되고, 원래의 노드는 그 자식의 오른쪽 자식이 됩니다. 이 연산은 노드의 왼쪽 서브트리의 높이가 너무 높아져 균형이 깨졌을 때 사용하며, 이를 통해 왼쪽 서브트리의 높이를 줄일 수 있습니다.

왼쪽-오른쪽 회전: 노드의 왼쪽 자식에 대해 왼쪽 회전을 수행한 후, 노드에 대해 오른쪽 회전을 수행합니다. 이 연산은 노드의 왼쪽 서브트리의 높이가 높아진 상태에서, 그 서브트리의 오른쪽 서브트리의 높이가 너무 높아져 균형이 깨졌을 때 사용합니다.

오른쪽-왼쪽 회전: 노드의 오른쪽 자식에 대해 오른쪽 회전을 수행한 후, 노드에 대해 왼쪽 회전을 수행합니다. 이 연산은 노드의 오른쪽 서브트리의 높이가 높아진 상태에서, 그 서브트리의 왼쪽 서브트리의 높이가 너무 높아져 균형이 깨졌을 때 사용합니다.

이러한 회전 연산들은 AVL 트리의 균형을 유지하는 데 핵심적인 역할을 합니다. 회전 연산을 통해 AVL 트리는 모든 노드에서 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 많아야 1이 되도록 균형을 유지합니다.

 

한마디로,

회전 연산은 AVL 트리에서 균형이 깨진 경우 이를 복원하기 위해 사용하는 트리 재구조화 방법입니다