이진 탐색 트리에 노드 삽입하기

영상에서 이진 탐색 트리(BST)가 무엇인지와 주요 연산을 구현하는 방법을 배웠어요.

이 연습 문제에서는 BST에 노드를 삽입하는 함수를 구현해 보겠습니다.

코드를 테스트하려면 아래 트리를 사용할 수 있어요:

Graphical representation of a binary search tree.

노드에는 책 제목이 들어 있으며, 알파벳 순서에 따라 BST를 구성합니다.

이 트리는 bst 변수에 미리 불러와져 있어요:

bst = CreateTree()

노드가 올바르게 삽입되었는지 다음 코드로 확인할 수 있어요:

bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))

이 연습은 강의의 일부입니다

Python으로 배우는 자료구조와 알고리즘

강의 보기

연습 안내

BST가 비어 있는지 확인하세요.
삽입할 데이터가 현재 노드의 데이터보다 작은지 확인하세요.
삽입할 데이터가 현재 노드의 데이터보다 큰지 확인하세요.

실습형 인터랙티브 연습

이 예제를 이 샘플 코드를 완성하여 풀어보세요.

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

  def insert(self, data):
    new_node = TreeNode(data)
    # Check if the BST is empty
    if ____ == None:
      self.root = new_node
      return
    else:
      current_node = self.root
      while True:
        # Check if the data to insert is smaller than the current node's data
        if ____ < ____:
          if current_node.left_child == None:
            current_node.left_child = new_node
            return 
          else:
            current_node = current_node.left_child
        # Check if the data to insert is greater than the current node's data
        elif ____ > ____:
          if current_node.right_child == None:
            current_node.right_child = new_node
            return
          else:
            current_node = current_node.right_child

bst = CreateTree()
bst.insert("Pride and Prejudice")
print(search(bst, "Pride and Prejudice"))

코드 편집 및 실행