StudyData Structure

트리 순회(Tree traversal)

순회

  • 재방문을 허용하지 않고 트리를 구성하는 모든 노드에 다해서 반드시 한번씩 방문하는 것
  • Queue 계열의 알고리즘
    • BFS(Breadth First Search) : 너비 우선 탐색
    • 레벨 순서 순회(levelorder traversal)
      • root를 시작으로 다음 레벨 왼쪽부터 방문
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        30
        31
        32
        33
        34
        35
        36
        37
        38
        39
        40
        41
        42
        43
        # python Queue module 이용
        from queue import Queue

        # traversal(순회)
        # 재방문없이 어떤 자료구조의 모든 데이터(노드)를 방문하는 것
        class TreeNode:
            def __init__(self, data):
                self.data = data
                self.left = None
                self.right = None

        def levelorder(cur):
            q = Queue()

            q.put(cur)

            while not q.empty():
                cur = q.get()
                print(cur.data, end = " ")

                if cur.left:
                    q.put(cur.left)
                if cur.right:
                    q.put(cur.right)


        if __name__ == "__main__":
            n1 = TreeNode(1)
            n2 = TreeNode(2)
            n3 = TreeNode(3)
            n4 = TreeNode(4)
            n5 = TreeNode(5)
            n6 = TreeNode(6)
            n7 = TreeNode(7)

            n1.left = n2
            n1.right = n3
            n2.left = n4
            n2.right = n5
            n3.left = n6
            n3.right = n7

            levelorder(n1)

BST(Binary Search Tree)

  • insert, search, delete 모두 O(log(n))
  • 최악의 경우 모두 O(n)
  • 데이터가 정렬되어 있다.
  • insert를 할 때 반드시 empty node에 들어가게 되어있다.
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    class TreeNode:
        def __init__(self, key=None):
            self.__key = key
            self.__left = None
            self.__right = None

        # getter
        @property
        def key(self):
            return self.__key

        # setter
        @key.setter
        def key(self, key):
            self.__key = key

        @property
        def left(self):
            return self.__left

        @left.setter
        def left(self, left):
            self.__left = left

        @property
        def right(self):
            return self.__right

        @right.setter
        def right(self, right):
            self.__right = right

    class BST:
        def __init__(self):
            self.__root = None

        @property
        def root(self):
            return self.__root

        def preorder(self, cur):
            if not cur:
                return

            print(cur.key, end = " ")
            self.preorder(cur.left)
            self.preorder(cur.right)
        
        def insert(self, key):
            new_node = TreeNode(key)

            cur = self.__root

            if not cur:
                self.__root = new_node
                return
            
            while True:
                parent = cur
                if key < cur.key:
                    cur = cur.left
                    if not cur:
                        parent.left = new_node
                        return
                else:
                    cur = cur.right
                    if not cur:
                        parent.right = new_node
                        return
        
        def search(self, target):
            # 함수를 구현할 때는 예외사항을 모두 생각하면 만들어야 한다.
            # root가 존재하지 않을 경우, cur가 None이므로 while 문이 돌지 않고 바로 빠져나가게 된다.
            cur = self.__root

            while cur:
                if cur.key == target:
                    return cur
                
                elif cur.key > target:
                    cur = cur.left

                else:
                    cur = cur.right
                
            return None
        
        # 1. 리프 노드일 때
        # 2. 자식이 하나일 때 - 왼쪽, 오른쪽
        # 3. 자식이 둘일 때
        def delete(self, target):
            self.__root = self.__delete_recursion(self.__root, target)

        # 재귀 함수
        # 자료구조에서 데이터를 빼고 반환하지 않는다. --> delelte
        # 자료구조에서 데이터를 빼고 사용자에게 반환해준다. --> remove
        def __delete_recursion(self, cur, target):
            # base case
            if not cur:
                return None
            elif target < cur.key:
                cur.left = self.__delete_recursion(cur.left, target)
            elif target > cur.key:
                cur.right = self.__delete_recursion(cur.right, target)
            # target == cur.key
            else:
                # 1. 삭제 노드가 리프 노드인 경우
                if not cur.left and not cur.right:
                    cur = None

                # 2. 삭제 노드의 자식이 하나일 때
                # 왼쪽 자식이 있는 경우
                elif not cur.right:
                    cur = cur.left

                # 오른쪽 자식이 있는 경우
                elif not cur.left:
                    cur = cur.right

                # 3. 삭제 노드의 자식이 둘일 때
                # - 왼쪽 서브 트리에서 가장 큰 수
                # - 오른쪽 서브 트리에서 가장 작은 수
                else:
                    # 대체 노드를 찾는다
                    rep = cur.left
                    while rep.right:
                        rep = rep.right
                    # 삭제 노드와 대체 노드의 키를 교환
                    cur.key, rep.key = rep.key, cur.key

                    cur.left = self.__delete_recursion(cur.left, rep.key)

            return cur

    # test code
    if __name__ == "__main__":
        bst = BST()

        bst.insert(6)
        bst.insert(3)
        bst.insert(8)
        bst.insert(2)
        bst.insert(4)
        bst.insert(10)
        bst.insert(9)
        bst.insert(11)

        bst.preorder(bst.root)
        print()
        bst.insert(5)
        bst.preorder(bst.root)

        print()

        ret = bst.search(13)
        if ret:
            print(f"{ret.key} is found.")
        else:
            print("No such data.")

        # 삭제노드가 리프 노드일 때
        # bst.delete(9)
        # bst.delete(8)
        bst.delete(6)

        bst.preorder(bst.root)
Share