[python] 이진 탐색 트리 (binary Search tree) - 2. 탐색

📗 이진 트리 (binary Search tree)

🔵 이진 탐색 트리 탐색

[python] 이진 탐색 트리 (binary Search tree) - 1. 클래스 정의, 초기화, 노드 추가

🔺 클래스 정의 및 초기화는 앞에서 다뤘다.

 

 이진 탐색 트리에 찾고자하는 값이 있는지를 확인하는 것이다. 값이 있으면 True, 없으면 False를 반환한다.

맨 위의 이미지를 보면 원하는 값인 27을 찾는 과정이다. 

• 먼저 최상위 노드인 21과 27을 비교한다.
• 27이 노드값보다 크므로 오른쪽으로 이동해서 탐색한다.
• 다음 노드를 보면 28이다. 27이 노드값보다 작으므로 왼쪽으로 이동해서 탐색한다.
• 다음은 25이다. 27이 노드값보다 크므로 오른쪽으로 이동한다.
• 27을 찾았으므로 탐색 종료.

그림 아래의 정렬된 리스트의 순차적인 탐색과 비교해보면 훨씬 빠른걸 볼 수 있다.

다음은 탐색 코드 이다.

class Node:
    def __init__(self, item):

class BinaryTree:
    def __init__(self):

    def add(self, item):

    def __add_node(self, cur, item):

    # 찾기!!
    def search(self, item):
        if self.head.val is None:
            return False
        else:
            return self.__search_node(self.head, item)

    def __search_node(self, cur, item):
        print(cur.val, item)
        if cur.val == item:
            return True
        else:
            if cur.val >= item:
                if cur.left is not None:
                    return self.__search_node(cur.left, item)
                else:
                    return False
            else:
                if cur.right is not None:
                    return self.__search_node(cur.right, item)
                else:
                    return False
                    
                    

---

🔵 전체 코드

# 노드 만들기
#         A(val)
#        /      \
#   B(left)     C(right)
class Node:
    def __init__(self, item):
        self.val = item
        self.left = None
        self.right = None


# 이진트리 만들기
class BinaryTree:
    # 초기값 head는 None
    def __init__(self):
        self.head = Node(None)

        self.preorder_list=[]
        self.inorder_list=[]
        self.postorder_list=[]

    # 값 추가하기 head가 없을 경우
    def add(self, item):
        if self.head.val is None:
            self.head.val = item

        # head가 있으면 왼쪽배치 or 오른쪽배치
        else:
            self.__add_node(self.head, item)

    # head가 있는 경우
    def __add_node(self, cur, item):
        print('부모:', cur.val, '자식:', item)
        # head 값이 크면 왼쪽으로
        if cur.val >= item:
            if cur.left is not None:
                self.__add_node(cur.left, item)
            else:
                cur.left = Node(item)
        # head 값이 작으면 오른쪽으로
        else:
            if cur.right is not None:
                self.__add_node(cur.right, item)
            else:
                cur.right = Node(item)

    # 찾기!!
    def search(self, item):
        if self.head.val is None:
            return False
        else:
            return self.__search_node(self.head, item)

    def __search_node(self, cur, item):
        print(cur.val, item)
        if cur.val == item:
            return True
        else:
            if cur.val >= item:
                if cur.left is not None:
                    return self.__search_node(cur.left, item)
                else:
                    return False
            else:
                if cur.right is not None:
                    return self.__search_node(cur.right, item)
                else:
                    return False


lst = [50, 30, 24, 5, 28, 45, 98, 52, 60]
bt = BinaryTree()
for num in lst:
    bt.add(num)

print(bt.search(60))