트리(3) - 자가 균형 이진 탐색 트리

책 <파이썬 자료구조와 알고리즘>을 기본으로 배운 알고리즘 내용입니다

목차

• <자가 균형 이진 탐색 트리>
• 자가 균형 이진 탐색 트리의 종류
• 1. AVL
•  1-1) AVL의 회전(LL, LR, RR, RL)
•  1-2) AVL의 삽입 구현
•  1-3) AVL의 구현
• 2. 레드-블랙 트리
• 3. 이진 힙

 

 

<자가 균형 이진 탐색 트리>

자가 균형 이진 탐색 트리

트리에서 노드의 삽이과 삭제가 이루어질 때 자동으로 균형 트리를 유지하는 이진 탐색 트리

균형 트리 : 모든 하위 트리의 높이 차가 1이하인 트리

균형도 : 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이

균형 조정 방법으로는 

① 노드 분할 및 병합 : 노드의 자식은 2개 이하이다. 노드가 많으면 두 개의 서브 노드로 나뉜다.

② 노드 회전 : 간선을 회전한다. x가 y의 부모이면, y를 x의 부모로 만들고, x는 y의 자식 중 하나늘 거둔다.

 

자가 균형 이진 탐색 트리의 종류

1. AVL

• 자체 균형 조건(균형도의 절댓값이 1을 초과해선 안된다.)을 가진 이진 탐색 트리
• 트리에 노드를 추가, 삭제할 떄마다 BST가 자가 균형 메소드를 호출한다.
• 노드를 회전함으로써 균형을 조정한다.

 

1-1) AVL의 회전 : AVL 트리는 이진 탐색 트리를 기본으로 하지만, 트리의 균형이 깨질 때 4가지 회전(LL, LR, RR, RL)을 통해서, 스스로 균형을 잡는다. 각 회전연산은 두 종류의 기본적인 연산으로 구현된다.

• left_rotate() - 왼쪽 서브트리의 트리레벨이 높아서 불균형이 발생했을 때, 왼쪽 방향으로 회전하기 위한 메소드
• right_rotate() - 오른쪽 서브트리의 트리레벨이 높아서 불균형이 발생했을 때, 오른쪽 방향으로 회전하기 위한 메소드

Case 1) LL회전 - 왼쪽으로 트리가 치우친 경우

Case 2) LR회전 - 왼쪽 자식노드에 오른쪽 자식 노드만 있을 경우

Case 3) RR회전 - 오른쪽으로 트리가 치우친 경우

Case 4) RL회전 - 오른쪽 자식노드에 왼쪽 자식 노드만 있을 경우

 

1-2) AVL의 삽입 구현

1. 이전에 구현한 이진 탐색 트리 구현과 같이 재귀 함수를 사용하여 상향식으로 구현한다.
2. 현재 노드는 새로 삽입될 노드의 조상 노드 중 하나다. 노드가 삽입될 때 조상 노드의 높이를 갱신한다.
3. 현재 노드의 균형도를 계산한다.

균형도>1인 경우에는 LL,LR

균형도<-1인 경우에는 RR.RL

1-3) AVL구현

from binary_tree import NodeBT, BinaryTree

class NodeAVL(NodeBT):
    def __init__(self, value=None, height=1):
        self.value = value
        self.height = height  # 높이(height)는 +1로 계산한다.
        self.left = None
        self.right = None

    def insert(self, value):
        # 1) 이진 탐색 트리 노드 삽입
        new_node = NodeAVL(value)
        if value < self.value:
            self.left = self.left and self.left.insert(value)\
                 or new_node
        elif value > self.value:
            self.right = self.right and self.right.insert(value)\
                 or new_node
        else:
            raise Exception("중복 노드를 허용하지 않습니다.")
        # 회전 메서드에서 높이를 설정한다.
        return self.rotate(value)

    def rotate(self, value):
        # 2) (조상) 노드의 높이를 갱신한다.
        self.height = 1 + max(self.get_height(self.left),
                              self.get_height(self.right))

        # 3) 균형도(왼쪽 트리 높이 - 오른쪽 트리 높이)
        balance = self.get_balance()

        # 4) 트리의 균형이 맞지 않을 경우 회전한다.
        if balance > 1:
            # [케이스 1] LL - Left Left
            if value < self.left.value:
                return self.right_rotate()

            # [케이스 2] LR - Left Right
            elif value > self.left.value:
                self.left = self.left.left_rotate()
                return self.right_rotate()

        elif balance < -1:
            # [케이스 3] RR - Right Right
            if value > self.right.value:
                return self.left_rotate()

            # [케이스 4] RL - Right Left
            elif value < self.right.value:
                self.right = self.right.right_rotate()
                return self.left_rotate()
        return self

    def left_rotate(self):
        x = self.right
        T2 = x.left

        # 회전한 후,
        x.left = self
        self.right = T2

        # 높이를 갱신한다.
        self.height = 1 + max(self.get_height(self.left),
                              self.get_height(self.right))
        x.height = 1 + max(self.get_height(x.left),
                           self.get_height(x.right))

        # 새 루트 노드를 반환한다.
        return x    

    def right_rotate(self):
        y = self.left
        T2 = y.right

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

    def get_height(self, node):
        if not node:
            return 0
        return node.height

    def get_balance(self):
        return self.get_height(self.left) - self.get_height(self.right)

    def get_min_value_node(self, node):
        if node is None or node.left is None:
            return node
        return self.get_min_value_node(node.left)

    def delete(self, value):
        # 1) 이진 탐색 트리 노드 삭제
        if value < self.value:
            self.left = self.left and self.left.delete(value)
        elif value > self.value:
            self.right = self.right and self.right.delete(value)
        else:
            if self.left is None:
                temp = self.right
                self = None
                return temp
            elif self.right is None:
                temp = self.left
                self = None
                return temp

            temp = self.get_min_value_node(self.right)
            self.value = temp.value
            self.right = self.right and self.right.delete(temp.value)

        if self is None:
            return None
        return self.rotate(value)

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

    def insert(self, value):
        if not self.root:
            self.root = NodeAVL(value)
        else:
            self.root = self.root.insert(value)

    def delete(self, value):
        self.root = self.root.delete(value)

def preorder(root):
    if root:
        print("({0}, {1}) ".format(root.value, root.height-1), end="")
        if root.left:
            preorder(root.left)
        if root.right:
            preorder(root.right)

if __name__ == "__main__":
    myTree = AVLTree()
    for i in range(10, 100, 10):
        myTree.insert(i)
    print("트리의 높이는? ", myTree.get_height())
    print("이진 탐색 트리입니까? ", myTree.is_bst())
    print("균형 트리입니까? ", myTree.is_balanced())
    preorder(myTree.root)
    print() 

 

2. 레드-블랙 트리

• 트리 연산의 복잡도에 영향을 받지않고, 이진탐색트리(BST)의 개선 버전이다.
• 각각의 노드가 레드나 블랙인 색상속성을 가지고 있다.
• 루트 노드부터 가장 먼 경로까지의 거리가, 가장 가까운 경로까지의 거리의 2배 보다 항상 작다.
• BTS가 가지고 있는 일반적인 속성에 다음과 같은 조건을 만족하면 레드-블랙 트리가 된다.

1. 노드는 레드 혹은 블랙 중의 하나이다.
2. 루트 노드는 블랙이다.
3. 모든 리프 노드들(NIL)은 블랙이다.
4. 레드 노드의 자식노드 양쪽은 언제나 모두 블랙이다. (즉, 레드 노드는 연달아 나타날 수 없으며, 블랙 노드만이 레드 노드의 부모 노드가 될 수 있다) ☞ 최단 경로는 모두 블랙 노드로만 구성되어 있다고 했을 때, 최장 경로는 블랙 노드와 레드 노드가 번갈아 나올 것이다.
5. 어떤 노드로부터 시작되어 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다. ☞ 존재하는 모든 경로에 대해 최장 경로의 거리는 최단 경로의 거리의 2배 이상이 될 수 없다.

 

3. 이진 힙

• 힙 속성을 사용한 완전 균형 이진 트리
• 힙의 노드를 분할 또는 회전할 필요가 없어 효율적이다.
• 이진 힙에서 할 작업은 부모 노드와 자식 노드를 교체하는 것 뿐이다.