[자료구조] 이진 검색 트리

class Node:
    def __init__(self, key, value, left: None, right: None):
        self.key = key  # 키
        self.value = value  # 값
        self.left = left  # 왼쪽 포인터
        self.right = right  # 오른쪽 포인터


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def search(self, key):
        p = self.root
        while True:
            if p is None:
                return None
            if key == p.key:
                return p.value
            elif key < p.key:
                p = p.left
            else:
                p = p.right

    # key, value 인 node 삽입
    def add(self, key, value):
        def add_node(node, key, value):
            if key == node.key:
                return False  # 이미 존재하는 key 값이라면 삽입 취소
            elif key < node.key:
                if node.left is None:
                    node.left = Node(key, value, None, None)
                else:
                    add_node(node.left, key, value)
            else:
                if node.right is None:
                    node.right = Node(key, value, None, None)
                else:
                    add_node(node.right, key, value)
            return True

        if self.root is None:
            self.root = Node(key, value, None, None)
            return True
        else:
            return add_node(self.root, key, value)

    def remove(self, key):
        """키가 key 인 node 를 삭제"""
        p = self.root  # 스캔 중인 node
        parent = None  # 스캔 중인 node 의 부모 node
        is_left_true = True  # 제거되는 node 가 부모의 left node 라면 True 상태

        # 삭제할 node 탐색
        while True:
            if p is None:
                return False
            if key == p.key:
                break  # 삭제할 node 의 위치 찾았음
            else:
                parent = p  # 가지를 내려가기전에 부모 설정
                if key < p.key:
                    is_left_true = True  # 왼쪽 자식 node 로 내려가기 때문에
                    p = p.left
                else:
                    is_left_true = False
                    p = p.right
        # 자식 노드가 없거나 한 개
        if p.left is None:
            if p is self.root:
                self.root = p.right
            elif is_left_true:
                parent.left = p.right
            else:
                parent.right = p.right
        elif p.right is None:
            if p is self.root:
                self.root = p.left
            elif is_left_true:
                parent.left = p.left
            else:
                parent.right = p.left
        # 자식 노드가 두 개
        else:
            parent = p
            left = p.left
            is_left_child = True
            while left.right is not None:
                parent = left
                left = left.right
                is_left_child = False
            p.key = left.key
            p.value = left.value
            if is_left_child:
                parent.left = left.left  # 이 경우는 삭제할 node 의 자식이 양옆으로 두 개만 있는 상태에만 해당한다.
            else:
                parent.right = left.left
        return True

    def dump(self, reverse=False):
        """ 중위순회를 통한 오름차순 출력 """
        def print_subtree(node):
            if node is not None:
                print_subtree(node.left)
                print(f'{node.key} {node.value}')
                print_subtree(node.right)

        """ 중위순회를 통한 내림차순 출력 """
        def print_subtree_rev(node):
            if node is not None:
                print_subtree_rev(node.right)
                print(f'{node.key} {node.value}')
                print_subtree_rev(node.left)

        print_subtree_rev(self.root) if reverse else print_subtree(self.root)

    # 전위순회
    def preorder(self):
        def print_subtree(node):
            if node is not None:
                print(f'{node.key} {node.value}')
                print_subtree(node.left)
                print_subtree(node.right)
        print_subtree(self.root)

    # 후위순회
    def postorder(self):
        def print_subtree(node):
            if node is not None:
                print_subtree(node.left)
                print_subtree(node.right)
                print(f'{node.key} {node.value}')
        print_subtree(self.root)

    # 키 최소값
    def min_key(self):
        if self.root is None:
            return None
        p = self.root
        while p.left is not None:
            p = p.left
        return p.key

    # 키 최대값
    def max_key(self):
        if self.root is None:
            return None
        p = self.root
        while p.right is not None:
            p = p.right
        return p.key


arr = [[100, 7], [80, 4], [110, 2], [76, 6], [77, 9], [81, 1], [85, 8], [83, 5], [120, 3]]
t = BinarySearchTree()
for x, y in arr:
    t.add(x, y)
print(t.preorder())
print(t.postorder())