실습과제

이번에는 이진 탐색 트리의 색다른 메서드를 구현해 볼 것이다.

이진 탐색 트리에서 가장 작은 Node를 찾아주는 메소드다.

정적 메소드 find_min는 파라미터로 node를 받는다.

node를 뿌리로 갖는 부분 트리 안에서 가장 작은 Node를 리턴해준다.

이게 무슨 말인지 조금 헷갈리실 수 있다.

예를 들어서 이런 이진 탐색 트리가 있다고 합시다.

그럼 find_min 메소드의 파라미터로 root Node를 리턴해주면 트리 전체에서 가장 작은 Node가 리턴되는 것이다.

여기서는 1이 저장된 Node 이다.

5가 저장된 Node 를 find_min 메소드의 파라미터로 넘기면 이 노란색 박스 안에 있는 부분 트리 안에서 가장 작은 Node, 그러니까 이번에도 1이 저장된 Node가 리턴된다.

하나만 더 보자.

14가 저장된 Node를 find_min 메소드의 파라미터로 넘기면 이 빨간색 박스 안에 있는 부분 트리 안에서 가장 작은 Node 12가 리턴된다.

주어진 Node를 뿌리로 갖는 부분 트리에서 가장 작은 Node를 리턴해주는 정적 메소드 find_min을 써보라!

출력 예시

2
8

답

class Node:
    """이진 탐색 트리 노드 클래스"""
    def __init__(self, data):
        self.data = data
        self.parent = None
        self.right_child = None
        self.left_child = None

def print_inorder(node):
    """주어진 노드를 in-order로 출력해주는 함수"""
    if node is not None:
        print_inorder(node.left_child)
        print(node.data)
        print_inorder(node.right_child)

class BinarySearchTree:
    """이진 탐색 트리 클래스"""
    def __init__(self):
        self.root = None

    @staticmethod
    def find_min(node):
		    """(부분)이진 탐색 트리의 가장 작은 노드 리턴"""
		    # 코드를 쓰세요
		    temp = node  # 도우미 변수. 파라미터 node로 초기화
		
		    # temp가 node를 뿌리로 갖는 부분 트리에서 가장 작은 노드일 때까지 왼쪽 자식 노드로 간다
		    while temp.left_child is not None:
		        temp = temp.left_child      
		
		    return temp

    def search(self, data):
        """이진 탐색 트리 탐색 메소드, 찾는 데이터를 갖는 노드가 없으면 None을 리턴한다"""
        temp = self.root  # 탐색용 변수, root 노드로 초기화
    
        # 원하는 데이터를 갖는 노드를 찾을 때까지 돈다
        while temp is not None:
            # 원하는 데이터를 갖는 노드를 찾으면 리턴
            if data == temp.data:
                return temp
            # 원하는 데이터가 노드의 데이터보다 크면 오른쪽 자식 노드로 간다
            if data > temp.data:
                temp = temp.right_child
            # 원하는 데이터가 노드의 데이터보다 작으면 왼쪽 자식 노드로 간다
            else:
                temp = temp.left_child
    
        return None # 원하는 데이터가 트리에 없으면 None 리턴

    def insert(self, data):
        """이진 탐색 트리 삽입 메소드"""
        new_node = Node(data)  # 삽입할 데이터를 갖는 노드 생성

        # 트리가 비었으면 새로운 노드를 root 노드로 만든다
        if self.root is None:
            self.root = new_node
            return

        # 코드를 쓰세요
        temp = self.root  # 저장하려는 위치를 찾기 위해 사용할 변수. root 노드로 초기화한다

        # 원하는 위치를 찾아간다
        while temp is not None:
            if data > temp.data:  # 삽입하려는 데이터가 현재 노드 데이터보다 크다면
                # 오른쪽 자식이 없으면 새로운 노드를 현재 노드 오른쪽 자식으로 만듦
                if temp.right_child is None:
                    new_node.parent = temp
                    temp.right_child = new_node
                    return
                # 오른쪽 자식이 있으면 오른쪽 자식으로 간다
                else:
                    temp = temp.right_child
            else:  # 삽입하려는 데이터가 현재 노드 데이터보다 작다면
                # 왼쪽 자식이 없으면 새로운 노드를 현재 노드 왼쪽 자식으로 만듦
                if temp.left_child is None:
                    new_node.parent = temp
                    temp.left_child = new_node
                    return
                # 왼쪽 자식이 있다면 왼쪽 자식으로 간다
                else:
                    temp = temp.left_child
            

    def print_sorted_tree(self):
        """이진 탐색 트리 내의 데이터를 정렬된 순서로 출력해주는 메소드"""
        print_inorder(self.root)  # root 노드를 in-order로 출력한다

# 빈 이진 탐색 트리 생성
bst = BinarySearchTree()

# 데이터 삽입
bst.insert(7)
bst.insert(11)
bst.insert(9)
bst.insert(17)
bst.insert(8)
bst.insert(5)
bst.insert(19)
bst.insert(3)
bst.insert(2)
bst.insert(4)
bst.insert(14)

print(bst.find_min(bst.root).data)  # 전체 이진 탐색 트리에서 가장 작은 노드
print(bst.find_min(bst.root.right_child).data)  # root 노드의 오른쪽 부분 트리에서 가장 작은 노드