파이썬 코딩테스트 스터디 6주차 #3 - 이진 탐색 트리 구현

 

첫 번째 인수 lst를 이용하여 이진 탐색 트리를 생성하고, 

두 번째 인수 search_list에 있는 각 노드를 이진 캄색 트리에서 찾을 수 있는지 확인하여

True 또는 False를 담은 리스트 result를 반환하는 함수 

solution()작성 하세요.

 

제약 조건

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

입출력 예

lst	search_lst	answer
[5,3,8,3,2,1,7,10]	[1,2,5,6]
[1,3,5,7,9]	[2,4,6,8,10]

 

 

문제 분석하고 풀기

 

이진 탐색 트리 재점검

• 검색하려는 값과 현재 노드 비교, 같으면 검색 완료
• 검색하려는 값이 현재 노드의 값보다 작으면, 왼쪽 서브 트리로 이동
• 검색하려는 값이 현재 노드의 값보다 크면, 오른쪽 서브 트리로 이동

 

1. Node 클래스 선언

class Node:
   def __init__(self,key) :
      self.left = None
      self.right = None
      self.val = key

 

 

2. 이진 트리 생성

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

 

 

3. 이진 탐색 시작

 

#꼭대기부터 찾기 위해 root노드를 curr(현재노드)로 지정

curr = self.root 

def search(self,key):
   curr = self.root
   
   while curr and curr.val !=key:
      if key < curr.val:
         curr = curr.left
      else:
         curr = curr.right
   #만일 없으면 None을 return
   return curr

 

 

4. solution 구현부

def solution(lst,search_lst) :
   bst = BST()  #클래스 생성
   
   for key in lst:
      bst.insert(key)
   result =[]
   
   for search_val in search_lst:
      #찾는 값이 없을 경우 None을 리턴하기 때문에
      if bst.search(search_val):
         result.append(True)
      else :
         result.append(False)
   return result

 

 

 

♬ 자료 출처 - 책

코딩 테스트 합격자 되기 - 파이썬 편

 

 

 

이 포스팅의 모든 내용은 해당 책의 내용을 바탕으로 하고 있습니다. 

감사합니다.