13-2. 이진 탐색 트리와 자가 균형 이진 탐색 트리 (Binary Search Tree and Self-balancing Binary Tree): 파이썬 자료구조와 알고리즘

이진 탐색 트리

이진 탐색 트리 (binary search tree) 는 노드를 정렬된 순서로 유지하는 자료구조이다. 이진 트리로 이루어지며, 각 노드에는 값과 두 자식 노드에 대한 포인터가 있다. 또한 선택적으로, 부모 노드의 포인터를 저장할 수도 있다. 각 노드의 값은 왼쪽 하위 트리의 모든 항목보다 크고,  오른쪽 하위 트리의 모든 항목보다 작다. 즉,

• 노드의 왼쪽 하위 트리에는 노드의 값보다 작은 값의 노드만 존재한다.
• 노드의 오른쪽 하위 트리에는 노드의 값보다 큰 값의 노드만 존재한다.
• 왼쪽과 오른쪽 하위 트리 모두 이진 탐색 트리이다.
• 중복 노드가 없다.

이진 탐색 트리가 균형 트리인 경우, 노드 검색/삽입/삭제에 대한 시간 복잡도는 O(log n) 이다.

 

이진 탐색 트리 구현

이진 탐색 트리는 당연히 이진 트리의 종류 중 하나이다. 저번에 구현한 이진 트리 클래스를 슈퍼 클래스로 삼아 이진 탐색 트리를 구현해보자. 이진 트리 코드와의 차이점은 이진 탐색 트리의 조건에 따라 새 노드를 삽입해야 한다는 점이다.

 

from binary_tree import BinaryTree, NodeBT

class NodeBST(NOdeBT):
    def __init__(self, value=None, level=1):
        self.value = value
        self.level = level
        self.left = None
        self.right = None

    def _add_next_node(self, value, level_here=2):
        new_node = NodeBST(value, level_here)
        if value > self.value:
            self.right = self.right and self.right._add_next_node(value, level_here+1) or new_node
        elif value < self..value:
            self.left = self.left and self.left._add_next_node(value, level_here+1) or new_node
        else:
            print("중복 노드를 허용하지 않습니다.")
        return self
    
    def _search_for_node(self, value):
        if self.value == value:
            return self
        elif self.left and value < self.value:
            return self.left._search_for_node(value)
        elif self.right and value > self.value:
            return self.right._search_for_node(value)
        else:
            return False
    
class BinarySearchTree(BinaryTree):
    def __init__(self):
        self.root = None
    
    def add_node(self, value):
        if not self.root:
            self.root = NodeBST(value)
        else:
            self.root._add_next_node(value)

 

위의 경우 크기가 자신보다 더 큰 노드여야만 오른쪽으로 보낸다. 예를 들어 1~9의 값을 가지는 노드들로 이진 탐색 트리를 만들면 아래와 같이 생성될 수 있다.

 

 

자가 균형 이진 탐색 트리

먼저 균형 트리 (balanced tree) 란 모든 하위 트리의 높이 차이가 1 이하인 트리를 말한다. 위의 예제는 노드의 삽입과 삭제 연산이 일어날 때 자동으로 트리의 균형이 유지되지는 않는다. 또한 대부분의 이진 탐색 트리의 경우 시간 복잡도는 O(h) 다 (h는 트리의 높이). 균형이 유지되지 않은, 즉 한쪽으로 치우친 편향 트리 (skewed tree) 의 경우 시간 복잡도는 O(n)이다. 아래는 편향 트리의 예시이다.

 

자가 균형 이진 탐색 트리 (self-balancing binary tree) 란, 트리에서 노드의 삽입과 삭제 같은 연산이 일어날 때 자동으로 균형 트리를 유지하는 이진 탐색 트리이다. 이진 탐색 트리 연산에서 최악의 경우에 시간 복잡도는 O(log n)이다.

 

균형을 유지하기 위해 사용되는 균형도 (balance factor) 란 왼쪽과 오른쪽 하위 트리 높이의 차이를 뜻한다. 트리에는 여러 가지 균형 조정 방법이 있지만 보통 다음 두 작업을 기반으로 한다.

• 노드 분할 및 병합: 노드의 자식은 두 개를 초과하지 못하며, 노드가 많으면 두 개의 하위 노드로 나눈다.
• 노드 회전: 간선을 전환한다. x가 y의 부모이면, y를 x의 부모로 만들고, x는 y의 자식 중 하나를 거둔다.

 

AVL 트리

AVL 트리 (AVL tree) 는 왼쪽과 오른쪽 하위 트리의 높이 차이가 1보다 클 수 없는 자체 균형 조건을 가진 이진 탐색 트리다. 트리에 노드를 추가 또는 삭제할 때마다 이진 탐색 트리 클래스에 자가 균형 조정 메서드 호출을 추가하여 AVL 트리를 구현할 수 있다. 이 메서드는 노드가 추가 또는 삭제될 때마다 트리의 높이를 계속 확인하며 동작한다. AVL 트리는 균형도를 맞추기 위해 오른쪽 또는 왼쪽으로 회전 (rotation) 한다. 다음 그림에서 T1, T2, T3는 트리의 하위 트리다.

 

위 트리가 회전하더라도, 이진 탐색 트리의 조건에 벗어나지 않는다.

 

AVL 트리 삽입 구현

1. 이전에 구현한 이진 탐색 트리 구현과 같이 재귀 함수를 사용하여 상향식 (bottom-up) 으로 구현한다.
2. 현재 노드는 새로 삽입될 노드의 조상 노드 중 하나다. 노드가 삽입될 때 조상 노드의 높이를 갱신한다.
3. 현재 노드의 균형도를 계산한다 (현재 노드의 왼쪽 하위 트리 높이 - 현재 노드의 오른쪽 하위 트리 높이).
4. 트리의 균형도가 맞지 않는 경우 회전한다.
   
   1. 균형도가 1보다 큰 경우 LL 케이스와 LR 케이스가 있다.
      1. 새 노드 값이 현재 노드의 왼쪽 노드 값보다 작다면 LL 케이스다. 이 경우 R 회전을 수행한다.
      2. 새 노드 값이 현재 노드의 왼쪽 노드 값보다 크다면 LR 케이스다. 이 경우 LR 회전을 수행한다.
   2. 균형도가 -1 보다 작은 경우 RR 케이스와 RL 케이스가 있다.
      1. 새 노드 값이 현재 노드의 오른쪽 노드 값보다 크다면 RR 케이스다. 이 경우 L 회전을 수행한다.
      2. 새 노드 값이 현재 노드의 오른쪽 노드 값보다 작다면 RL 케이스다. 이 경우 RL 회전을 수행한다.

4-1-1. (LL 케이스)

 

 

4-1-2. (LR 케이스)

 

4-2-1. (RR 케이스)

 

 

4-2-2. (RL 케이스)

 

AVL 트리를 구현한 코드는 다음과 같다.

 

from binary_tree import NodeBT, BinaryTree

class NodeAVL(NodeBT):
    def __init__(self, value=None, height=1):
        self.value = value
        self.height = height
        self.left = None
        self.right = None

    def insert(self, value):
        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):
        # 조상 노드의 높이를 갱신한다.
        self.height = 1 + max(self.get_height(self.left), self.get_height(self.right))

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

        # 트리의 균형이 맞지 않을 경우 회전한다.
        if balance > 1:
            # 케이스 1: LL 케이스
            if value < self.left.value:
                return self.right_rotate()
            # 케이스 2: LR 케이스
            elif value > self.left.value:
                self.left = self.left.left_rotate()
                return self.right_rotate()
        if balance < -1:
            # 케이스 3: RR 케이스
            if value > self.right.value:
                return self.left_rotate()
            # 케이스 4: RL 케이스
            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):
        # 이진 탐색 트리 노드 삭제
        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()    

 

레드-블랙 트리

레드-블랙 트리 (red-black tree) 는 트리 연산의 복잡성에 영향을 미치지 않으면서 트리 균형을 유지하는 것을 목표로 한 이진 탐색 트리의 개선 버전이다. 각 트리의 노드를 레드와 블랙으로 표시하고, 트리의 가장 깊은 경로가 가장 짧은 경로의 두 배가 되지 않도록 유지하는 방식이다. AVL 트리는 레드-블랙 트리에 비해 더 균형적이지만, 노드와 삽입과 삭제 과정에 더 많은 회전 연산이 일어날 수 있다. 따라서, 노드의 삽입 및 삭제 연산의 빈도가 높은 경우에는 레드-블랙 트리를 사용하는 것이 좋다.

 

레드-블랙 트리의 조건은 다음과 같다.

• 노드는 레드 혹은 블랙 중 하나다.
• 루트 노드는 블랙이다.
• 모든 널 포인터 (NIL) 은 블랙이다.
• 레드 노드의 양쪽 자식 노드는 언제나 모두 블랙이다 (즉, 레드 노드는 연달아 있을 수 없으며, 블랙 노드만이 레드 노드의 부모가 될 수 있다).
• 어떤 노드부터 말단 노드에 도달하는 모든 경로에는 말단 노드를 제외하면 모두 같은 개수의 블랙 노드가 있다.

 

이진 힙

이진 힙 (binary heap) 은 완전 균형 이진 트리로, 힙 속성을 사용하면 트리의 균형을 유지하는 것이 쉬워진다. 힙의 노드를 분할하거나 회전하여 트리의 구조를 수정할 필요가 없기 때문이다. 이진 힙의 유일한 직업은 부모 노드와 자식 노드를 교체하는 것이다.

 

이진 힙에서 루트 (가장 작은 또는 큰 노드) 는 0번째 인덱스고, i번째 인덱스의 노드는 다음과 같은 특성이 있다.

• 부모 노드의 인덱스는 (i-1)/2 이다.
• 왼쪽 노드의 인덱스는 2i + 1이다.
• 오른쪽 노드의 인덱스는 2i + 2이다.

 

출처

파이썬 자료구조와 알고리즘 - 한빛미디어, 미아 스타인