🔍 이진 탐색 트리 구현

🗒️ 문제 설명

첫 번째 인수 lst를 이용하여 이진 탐색 트리를 생성하고, 두 번째 인수 search_lst에 있는 각 노드를 이진 탐색 트리에서 찾을 수 있는지 확인하여 True 또는 False를 담은 리스트 result를 반환하는 함수 solution()을 작성하세요.

제약 조건

• lst의 노드는 정수로 이루어져 있으며 1,000,000개를 초과하지 않습니다.
• 이진 탐색 트리의 삽입과 탐색 기능을 구현해야 합니다.
• search_lst의 길이는 10 이하입니다.

입출력의 예

lst	search_lst	result
[5, 3, 8, 4, 2, 1, 7, 10]	[1, 2, 5, 6]	[True, True, True, False]
[1, 3, 5, 7, 9]	[2, 4, 6, 8, 10]	[False, False, False, False, False]

---

💻 정답 코드

# ➊ 노드 클래스 정의
class Node:
  # ➋ 노드 클래스 생성자
  def __init__(self, key):
    self.left = None
    self.right = None
    self.val = key

# ➌ 이진 탐색 트리 클래스
class BST:
  # ➍ 초기에 아무 노드도 없는 상태
  def __init__(self):
    self.root = None
  # ➎ 루트 노드부터 시작해서 이진 탐색 트리 규칙에 맞는 위치에 새 노드 삽입
  def insert(self, key):
    # 루트 노드가 없는 경우 새로운 노드를 루트 노드로 추가
    if not self.root:
      self.root = Node(key)
    else:
      curr = self.root
      while True:
        # 삽입하려는 값이 현재 노드의 값보다 작은 경우 왼쪽 자식 노드로 이동
        if key < curr.val:
          if curr.left:
            curr = curr.left
          else:
            # 현재 노드의 왼쪽 자식 노드가 없는 경우 새로운 노드 추가
            curr.left = Node(key)
            break
        else:
          # 삽입하려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
          if curr.right:
            curr = curr.right
          else:
            # 현재 노드의 오른쪽 자식 노드가 없는 경우 새로운 노드 추가
            curr.right = Node(key)
            break
  # ➏ 이진 탐색 규칙에 따라 특정값이 있는지 확인(루트 노드부터 시작)
  def search(self, key):
    curr = self.root
    # 현재 노드가 존재하고, 찾으려는 값과 현재 노드의 값이 같지 않은 경우 반복
    while curr and curr.val != key:
      # 찾으려는 값이 현재 노드의 값보다 작은 경우 왼쪽 자식 노드로 이동
      if key < curr.val:
        curr = curr.left
      else:
        # 찾으려는 값이 현재 노드의 값보다 큰 경우 오른쪽 자식 노드로 이동
        curr = curr.right
    return curr
# ➐ lst에 있는 데이터를 활용해서 이진 탐색 트리 생성, search_lst 원소 탐색
def solution(lst, search_lst):
  bst = BST()
  # 리스트의 각 요소를 이용하여 이진 탐색 트리 생성
  for key in lst:
    bst.insert(key)
  result = []
  # 검색 리스트의 각 요소를 이진 탐색 트리에서 검색하고, 검색 결과를 리스트에 추가
  for search_val in search_lst:
    if bst.search(search_val):
      result.append(True)
    else:
      result.append(False)
  return result
  
  
# TEST 코드 입니다. 주석을 풀고 실행시켜보세요
# print(solution([5, 3, 8, 4, 2, 1, 7, 10], [1, 2, 5, 6])) # [True, True, True, False]
# print(solution([1, 3, 5, 7, 9], [2, 4, 6, 8, 10])) # [False, False, False, False, False] 

✅ 코드 설명

• ➊ 노드 클래스 정의:

  • Node 클래스는 이진 탐색 트리에서 사용할 노드를 생성하는 클래스이다.

• ➋ 노드 클래스 생성자:

  • __init__() 메서드에서는 노드의 왼쪽 자식 노드와 오른쪽 자식 노드를 None으로 초기화하며 노드의 값을 설정한다.

• ➌ 이진 탐색 트리 클래스:

  • BTS 클래스는 이진 탐색 트리를 생성하는 클래스이다.
  • 이진 탐색 트리를 연결 리스트Linked List로 구현한다.

• ➍ 초기에 아무 노드도 없는 상태:

  • __init__() 메서드에서는 루트 노드를 None으로 초기화한다.

• ➎ insert() 메서드:

  • insert() 메서드에서는 새 노드를 삽입한다.
  • 루트 노드부터 시작하여 규칙에 맞도록 노드를 삽입한다.

• ➏ search() 메서드:

  • search() 메서드에서는 이진 탐색 트리에서 값을 찾는다.
  • 루트 노드부터 시작하여 찾으려는 노드를 찾을 때까지 이동한다.
  • 노드를 찾으면 해당 노드를 반환하고, 찾지 못하면 None을 반환한다.

• ➐ solution() 함수:

  • solution() 함수는 lst와 search_lst를 인수로 받는다.
  • lst의 각 요소를 이용하여 이진 탐색 트리를 생성한다.
  • search_lst의 각 요소를 이진 탐색 트리에서 검색한다.
  • 최종적으로 검색 결과를 리스트에 추가한다.

⌛ 시간 복잡도 분석

시간 복잡도: O(N²)

N은 노드의 개수이고, M은 search_lst의 길이이다. 최악의 경우 이진 탐색 트리의 삽입 및 탐색 연산 시간 복잡도는 O(N)이다. 이후 lst의 길이만큼 삽입하고, search_lst의 길이만큼 탐색하므로 시간 복잡도는 O(N * (N + M))이다. 이때 N이 M보다 훨씬 크므로 M은 무시할 수 있다. 따라서 최종 시간 복잡도는 O(N²)이다.