이번에는 search를 살펴볼까요? search는 insert를 이해했다면 쉽게 이해할 수 있습니다. 코드만 간단하게 살펴보고 넘어가겠습니다.

코드 8-5

    def search(self, target):
        cur = self.root
        while cur:
            if cur.key == target:
                return cur
            elif cur.key > target:
                cur = cur.left
            elif cur.key < target:
                cur = cur.right
        return cur

코드 8-5는 search 메서드입니다. target이 있다면 cur를 루트부터 아래로 쭉 훑으면서 비교하여 target을 찾습니다. 이때 cur의 키와 target을 한 번 비교해서 자식으로 내려갈 때마다 다른 쪽 서브 트리의 모든 노드는 비교할 필요가 없어집니다. 이진 탐색과 같은 알고리즘입니다.

삽입, 탐색과 달리 BST의 삭제는 조금 어렵습니다. 삭제하려는 노드가 리프 노드인지, 자식이 하나만 있는 노드인지, 자식이 둘인지 나누어서 삭제해야 하기 때문입니다. 먼저 코드를 보겠습니다.