[python] 자료구조 - 트리(Tree) / 이진 탐색 트리(Binary Search Tree)

트리(Tree)

 

출처: https://en.wikipedia.org/wiki/Binary_search_tree

 

 

트리는 노드(Node)와 브랜치(Branch)로 구성되어있다. 위 이미지에서 원이 노드, 화살표가 브랜치다. 각 노드들은 링크드 리스트 구조로 연결되어 있으며, 싸이클이 없다. 마지막 데이터에서 처음 데이터로 돌아오지 않는다.

 

 

 

아래 애니메이션을 보면 이진 탐색 트리 구조에서 데이터가 어떻게 삽입되는지 쉽게 이해할 수 있다. 21보다 작으면 왼쪽으로, 크면 오른쪽으로 이동한다. 그리고 다음 노드를 만나서 이 단계를 반복한다. 만약 더 이상 비교할 데이터가 없으면 해당 위치에 데이터가 삽입된다.

 

출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

 

위 애니메이션에서 21은 루트 노드(Root Node)에 해당한다. 이 값을 기준으로 마치 나무의 가지가 뻗어 나가듯이 데이터가 추가된다. 이진 트리에서는 브랜치가 최대 2개이기 때문에 각 노드는 최대 2개의 자식 노드(Child Node)를 가질 수 있으며, 루트 노드를 제외한 노드는 하나의 부모 노드(Parent Node)를 가진다. ex) 14와 28의 부모 노드는 21이다.

 

14와 28처럼 동일한 부모 노드를 가진 노드는 형제 노드 관계이며 Siblings라고 부르기도 한다. 다음으로 15, 19, 30처럼 자식노드가 없는 노드는 잎 노드(leaf Node)라고 부른다. 

 

이진 트리가 뻗어 나가서 브랜치를 확장한 단계를 depth 혹은 level이라고 표현한다. 루트 노드인 21은 level 0에 해당하고, 21의 자식노드인 14와 28은 level 1이다. 다음으로 11, 18, 25, 32는 level 2에 해당한다.

 

 

 

그렇다면 트리의 장점은 뭘까?

Binary Search Tree vs Sorted Array Animated Gif

출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node

배열은 순차적으로 모든 데이터를 확인하며 나아가는 데에 반해서, 이진 탐색 트리는 서치 과정에서 탐색 해야하는 데이터를 줄여 나가기 때문에 데이터 검색 속도에서 더 높은 기댓값을 가진다. (단 트리가 한쪽으로만 가지를 친 최악의 경우면 배열과 다를 게 없다.)

 

 

class Node:
    def __init__(self, value=None):
        self.value = value
        self.left = None
        self.right = None


class Tree:     # Binary Search Tree
    def __init__(self):
        self.head = None

    def insert(self, value):
        if self.head is None:
            self.head = Node(value)
        else:
            node = self.head

            while True:
                if value < node.value:
                    if node.left is None:
                        node.left = Node(value)
                        break
                    else:
                        node = node.left
                else:
                    if node.right is None:
                        node.right = Node(value)
                        break
                    else:
                        node = node.right

    def delete(self, value):
        if self.head is None:
            return False

        node = self.head
        parent = self.head
        check = False

        while node:
            if value == node.value:
                check = True
                break
            elif value < node.value:
                parent = node
                node = node.left
            else:
                parent = node
                node = node.right

        if not check:
            return False

        # Case1 No Child
        if node.left is None and node.right is None:
            if value < parent.value:
                parent.left = None
            else:
                parent.right = None

        # Case2 Have a One Child
        elif node.left and node.right is None:
            if value < parent.value:
                parent.left = node.left
            else:
                parent.right = node.left

        elif node.left is None and node.right:
            if value < parent.value:
                parent.left = node.right
            else:
                parent.right = node.right

        # Case3 Have Two Child
        elif node.left and node.right:
            current, child = node, node.right

            while child.left:
                current, child = child, child.left

            node.value = child.value

            if current != node:
                if child.right:
                    current.left = child.right
                else:
                    current.left = None
            else:
                node.right = child.right

    def search(self, value):
        if self.head is None:
            return False, None

        depth = 0
        node = self.head

        while True:
            if value == node.value:
                return True, depth
            else:
                if value < node.value:
                    node = node.left
                else:
                    node = node.right

                if node is None:
                    return False, None

            depth += 1

    def show(self, node, depth=0):
        if node is None:
            return

        print(node.value, depth)
        self.show(node.left, depth+1)
        self.show(node.right, depth+1)

    def print(self):
        self.show(self.head)


tree = Tree()
tree.insert(5)
tree.insert(7)
tree.insert(1)
tree.insert(2)
tree.insert(8)
tree.insert(3)
tree.insert(4)
tree.insert(6)
tree.insert(9)
tree.print()

result = tree.search(10)
print(result)

print()
tree.delete(7)
tree.print()

2021.12.06. 코드 수정

 

Case 3 모든 케이스 테스트 X..