이진 탐색 트리 구현

 

주석 포함 코드 

 

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:  
                        # 존재시 딱 현 위치 내려주는 것 까지만 하면됨.
                        # leaf노드 까지 가기위해서 이 작업을 하는 것임
                        curr = curr.left
                    else:
                        #leaf노드 도달 시 노드를 지정해줌 
                        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
                


def solution(lst, search_lst):
    # 이진 탐색 트리 생성
    # search_lst의 각 노드를 이진 탐색트리에서 찾을 수 있는지 여부 반환 리스트 반환
    result = []

    bst = BST() # 객체 생성

    for key in lst:
        bst.insert(key) # bst객체가 insert메서드 호출 
    
    for search in search_lst:
        if bst.search(search):
            result.append(True)
        else:
            result.append(False)


    print(result)

    return result

 

 

 

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 1:
                if curr.val > key:
                    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
        print('curr', curr)
        while curr and curr.val != key:
            if curr.val > key:
                curr = curr.left
            else:
                curr = curr.right

        return curr 
            


def solution(lst, search_lst):
    bst = BST()

    for key in lst:
        bst.insert(key)
    
    result = []
    for searchVal in search_lst:
        if bst.search(searchVal):
            result.append(True)
        else:
            result.append(False)

    return result