2.5remove( ) 메서드

구현하기 가장 까다로운 remove() 메서드의 알고리즘과 코드를 구현해 보겠습니다. remove() 메서드는 재귀 함수를 사용해 구현하려 합니다.

먼저 지우려는 대상 데이터를 찾습니다. 다음으로 삭제 노드의 상태에 따라 세 가지 경우로 나누어 지웁니다.

1| 삭제 노드가 리프 노드일 때

2| 삭제 노드의 자식 노드가 하나일 때

3| 삭제 노드의 자식 노드가 두 개일 때

우선 유저 프로그래머가 사용할 remove() 메서드의 코드를 볼까요?

코드 14-4 bst/BST.py ④(remove() 메서드)

    def remove(self, target):
        # 루트 노드의 변경 가능성이 있으므로
        # 루트를 업데이트해야 한다
        self.root, removed_node = self.__remove_recursion(self.root, target)
        # 삭제된 노드의 자식 노드를 None으로 만든다
        removed_node.left = removed_node.right = None

        return removed_node