파이썬 자료구조와 알고리즘(13)-이진 트리

그래프 이론 생략 ****

2. 이진 트리 구현하기

리스트로 구현하게 되면 삽입, 삭제 연산 시 비효율적이다. 클래스로 구현해보자

class Height(object):
    def __init__(self):
        self.height = 0


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

    def __repr__(self):
        return '{}'.format(self.value)

    def _add_next_node(self, value, level_here=2):
        new_node = NodeBT(value, level_here)
        if not self.value:
            self.value = new_node
        elif not self.left:
            self.left = new_node
        elif not self.right:
            self.right = new_node
        else:
            # 노드에 왼쪽 오른쪽 자식 모두 있다면
            # 왼쪽 자식 노드에 새 노드를 추가한다
            # 그래서 왼쪽으로 치우치게 된다.
            self.left = self.left._add_next_node(value, level_here+1)
        return self

    def _search_for_node(self, value):
        if self.value == value:
            return self
        else:
            found = None
            if self.left:
                found = self.left._search_for_node(value)
            if self.right:
                found = self.right._search_for_node(value)
            return found

    def _is_leaf(self):
        return not self.right and not self.left

    def _get_max_height(self):
        hightr, heightl = 0, 0
        if self.right:
            heightr = self.right._get_max_height()+1
        if self.left:
            heightl = self.left._get_max_height()+1
        return max(heightl, heightr)

    def _is_balanced(self, height=Height()):
        lh = Height()
        rh = Height()

        if self.value is None:
            return True
        l, r = True, True
        if self.left:
            l = self.left._is_balanced(lh)
            r = self.right._is_balanced(rh)

        height.height = max(lh.height, rh.height) + 1
        if abs(lh.height - rh.height) <= 1:
            return l and r
        return False

    def _is_bst(self, left=None, right=None):
        if self.value:
            if left and self.value < left:
                return False
            if right and self.value > right:
                return False

            l, r = True, True
            if self.left:
                l = self.left._is_bst(left, self.value)
            if self.right:
                r = self.right._is_bst(self.value, right)
            return l and r
        else:
            return True


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

    def add_node(self, value):
        if not self.root:
            self.root = NodeBT(value)
        else:
            self.root._add_next_node(value)

    def is_leaf(self, value):
        node = self.root._search_for_node(value)
        if node:
            return node._is_leaf
        else:
            return False

    def get_node_level(self, value):
        node = self.root._search_for_node(value)
        if node:
            return node.level
        else:
            return False

    def is_root(self, value):
        return self.root.value == value

    def get_height(self):
        return self.root._get_max_heightt()

    def is_balanced(self):
        return self.root._is_balanced()

    def is_bst(self):
        return self.root._is_bst()

3. 이진 탐색 트리

노드를 정렬된 순서로 유지하는 자료구조, 검색/삽입/삭제 연산은 O(logN)이다.

3.1 이진 탐색 트리 구현

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:
            pritnt('중복 노드를 허용하지 않습니다.')
        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)

4. 자가 균형 이진 탐색 트리

균형 트리란 모든 하위 트리의 높이 차가 1이하인 트리이다. 자가 균형 이진 탐색 트리란 트리에서 노드의 삽입과 삭제 등의 연산이 실행될 때 자동으로 균형 트리를 유지하는 이진 탐색 트리다. 연산에서 최악의 경우 O(logN)이다. 다음 두 작업을 기반으로 균형을 조정한다

• 노드 분할 및 병합 : 노드의 자식이 두 개를 초과하면, 두 개의 하위 노드로 나눈다.
• 노드 회전 : 간선을 전환한다.

4.1 AVL 트리

4.2 레드-블랙 트리

4.3 이진 힙

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

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

• 부모 노드의 인덱스는 $\frac{i-1}{2}$이다.
• 왼쪽 노드의 인덱스는 2i + 1이다.
• 오른쪽 노드의 인덱스는 2i + 2이다.