■ __remove_recursion 메서드

__remove_recursion() 메서드의 전체 코드를 보고 삭제 노드의 세 가지 경우를 예로 들어 하나씩 살펴보겠습니다.

코드 14-5 bst/BST.py ⑤(__remove_recursion() 메서드)

    def _ _remove_recursion(self, cur, target):
        # 탈출 조건 1
        # 대상 데이터가 트리 안에 없을 때
        if cur = = None:
            return None, None
        # 대상 데이터가 노드 데이터보다 작으면
        # 노드의 왼쪽 자식에서 대상 데이터를 가진 노드를 지운다(재귀 함수 호출)
        elif target < cur.data:
            cur.left, rem_node = self.__remove_recursion(cur.left, target)
        # 대상 데이터가 노드 데이터보다 크면
        # 노드의 오른쪽 자식에서 대상 데이터를 가진 노드를 지운다(재귀 함수 호출)
        elif target > cur.data:
            cur.right, rem_node = self.__remove_recursion(cur.right, target)
        # 탈출 조건 2
        # target = = cur.data
        else:
            #1. 리프 노드일 때
            if not cur.left and not cur.right:
                rem_node = cur
                cur = None
            #2-1. 자식 노드가 하나일 때: 왼쪽 자식이 있을 때
            elif not cur.right:
                rem_node = cur
                cur = cur.left
            #2-2. 자식 노드가 하나일 때: 오른쪽 자식이 있을 때
            elif not cur.left:
                rem_node = cur
                cur = cur.right

            #3. 자식 노드가 두 개일 때
            else:
                #4. 대체 노드를 찾는다
                replace = cur.left
                while replace.right:
                    replace = replace.right
                #5. 삭제 노드와 대체 노드의 값을 교환한다
                cur.data, replace.data = replace.data, cur.data
                #6. 대체 노드를 삭제하면서 삭제된 노드를 받아온다
                cur.left, rem_node = self.__remove_recursion(cur.left, replace.data)
        # 삭제 노드가 루트 노드일 경우
        # 루트가 변경될 수 있기 때문에
        # 삭제 후 현재 루트를 반환
        return cur, rem_node

탈출 조건은 대상 데이터가 트리 안에 없거나 대상 데이터를 찾았을 때입니다(#탈출 조건 1, 2). 또한 세 가지 경우의 삭제 조건도 보입니다. 각각 리프 노드일 때(#1), 자식 노드가 하나일 때(#2-1. #2-2), 자식 노드가 두 개일 때(#3)의 코드입니다.