트리(1) - 이진트리

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

목차

• <트리(Tree)>
• <이진 트리>
• 이진 트리의 종류(완전 이진 트리,포화 이진 트리)
• 이진 트리 구현

 

<트리(Tree)>

1) 개념

• 계층적인 구조를 표현
• 트리는 노드(node)들과 노드들을 연결하는 링크(link)들로 구성됨

 

2) 용어

• 루트 노드(root node) : 부모가 없는 노드. 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node) : 자식이 없는 노드
• 내부(internal) 노드 : 리프 노드가 아닌 노드 
• 노드 크기(size) : 자신을 포함한 모든 자손 노드의 개수
• 노드 깊이(depth) : 루트에서 어떤 노드로 가는 경로의 길이
• 노드 레벨(level) : 노드 깊이(depth) + 1
• 노드 차수(degree) : 각 노드가 지닌 가지의 수
• 트리 차수(degree of tree) : 트리의 최대 차수
• 트리 높이(height) : 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

3) 트리의 기본적인 성질

• 노드가 N개인 트리는 항상 N-1개의 링크(link)를 가진다
• 트리에서 어떤 노드로 가는 경로는 유일하다. 또한 임의의 두 노드 간의 경로도 유일하다 (같은 노드를 두 번 이상 방문하지 않는 다는 조건 하에)

 

 

<이진 트리>

이진 트리(Binary tree)

• 노드가 최대 두 개의 자식 노드(left, right)를 갖는 트리
• 자식 노드는 부모 노드에 대한 참조를 포함할 수 있음.

 

이진 트리의 종류

- 완전 이진 트리(Complete binary tree)

트리의 마지막 레벨을 제외한 모든 높이에서 노드가 꽉 차 있는 이진 트리
마지막 레벨은 꽉 차 있지 않아도 되자만 노드가 왼쪽에서 오른쪽으로 채워져야 함.

- 포화 이진 트리(Perfect binary tree)

모든 내부 노드가 두 개의 자식 노드를 가지고, 모든 말단 노드가 같은 레벨을 가지는 트리

포화 이진 트리의 높이h, 말단수n

 

이진 트리 구현

리스트 이용해 구현

def BinaryTreeList(r):
    return [r, [], []]

def insertLeft(root, newBranch):
    t = root.pop(1)
    if len(t) > 1:
        root.insert(1, [newBranch, t, []])
    else:
        root.insert(1, [newBranch, [], []])
    return root

def insertRight(root, newBranch):
    t = root.pop(2)
    if len(t) > 1:
        root.insert(2, [newBranch, [], t])
    else:
        root.insert(2, [newBranch, [], []])
    return root

def getRootVal(root):
    return root[0]

def setRootVal(root, newVal):
    root[0] = newVal

def getLeftChild(root):
    return root[1]

def getRightChild(root):
    return root[2]

def main():
    r = BinaryTreeList(3)
    insertLeft(r, 4)
    insertLeft(r, 5)
    insertRight(r, 6)
    insertRight(r, 7)
    print(getRootVal(r))
    print(getLeftChild(r))
    print(getRightChild(r))

if __name__ == "__main__":
    main() 

이진트리를 클래스로 표현해 구현

"""다음 그림의 이진 트리를 구현한다.
                               1          ---> 레벨 1
                        2           3    ---> 레벨 2
                    4       5            ---> 레벨 3
                6       7                ---> 레벨 4
            8       9                    ---> 레벨 5
    속성은 다음과 같다.
        - 노드의 개수(크기): n = 9
        - 분기(또는 내부 노드) 수: b = n-1 = 8
        - 루트 노드: 1
        - 최대 깊이 또는 높이: h = 4
        - 균형 트리입니까? NO
        - 이진 탐색 트리입니까? NO
"""

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):
        # 전위 순회(pre-order)로 값을 찾는다.
        if self.value == value:
            return self
        else:
            found = None
            if self.left:
                found = self.left._search_for_node(value)
            if self.right:
                found = found or 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):
        # 노드에서 최대 높이를 얻는다 - O(n)
        heightr, 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(heightr, heightl)

    def _is_balanced(self, height=Height())
:        # 균형 트리인지 확인한다 - O(n)
        lh = Height()
        rh = Height()

        if self.value is None:
            return True

        l, r = True, True
        if self.left:
            l = self.left._is_balanced(lh)
        if self.right:
            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):
        # 이진 탐색 트리인지 확인한다 - O(n)
        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_height()

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

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

if __name__ == "__main__":
    bt = BinaryTree()
    for i in range(1, 10):
        bt.add_node(i)
    print("노드 8은 말단 노드입니까? ", bt.is_leaf(8))
    print("노드 8의 레벨은? ", bt.get_node_level(8))
    print("노드 10은 루트 노드입니까? ", bt.is_root(10))
    print("노드 1은 루트 노드입니까? ", bt.is_root(1))
    print("트리의 높이는? ", bt.get_height())
    print("이진 탐색 트리입니까? ", bt.is_bst())
    print("균형 트리입니까? ", bt.is_balanced())