한빛미디어

안녕하세요.
뇌자극 알고리즙 책 잘 보고 있습니다.

책에 있는 BinarySearchTree 예제 프로그램을 다른 값을 넣어서 테스트해보는 중에 죽는 문제를 발견하였습니다.

예제에 특정 노드 삭제에서 98을 삭제하고 있는데 삭제하는 값을 424로 바꿀 경우 문제 발생합니다.

디버깅을 해보니 하기 코드에 "//문제되는 부분" 커멘트에서 Removed 에 Tree 포인터값을 대입하는데 현재 Tree의 포인터값은 예제 기준으로 424, 즉 삭제되는 노드입니다. 문제는 후에 저 노드의 포인터 값이 그대로 리턴되어 free 되어 버리므로 대입한 최소값(760) 노드가 삭제되고 하위 노드인 317 도 삭제됩니다.

따라서 9918 노드의 좌측 leaf 는 쓰레기 값을 가지게 되어 BST_InorderPrintTree 함수를 수행하다 죽게 됩니다.
하기 코드에 "//수정한 부분" 커멘트에서 실제로 삭제되는 최소값 노드를 리턴하도록 수정하였더니 문제가 수정되었습니다.
이렇게 수정을 해도 되는지 확인 부탁드립니다.

감사합니다.


BSTNode* BST_RemoveNode(BSTNode* Tree, BSTNode* Parent, ElementType Target)
{
        BSTNode* Removed = NULL;

        if (Tree == NULL)
                return NULL;

        if (Tree->Data > Target)
                Removed = BST_RemoveNode(Tree->Left, Tree, Target);
        else if (Tree->Data < Target)
                Removed = BST_RemoveNode(Tree->Right, Tree, Target);
        else
        {
                Removed = Tree;    //문제되는 부분

                if (Tree->Left == NULL && Tree->Right == NULL)
                {
                        if (Parent->Left == Tree)
                                Parent->Left = NULL;
                        else
                                Parent->Right = NULL;
                }
                else
                {
                        if (Tree->Left != NULL && Tree->Right != NULL)
                        {
                                BSTNode* MinNode = BST_SearchMinNode(Tree->Right);
                                MinNode = BST_RemoveNode(Tree, NULL, MinNode->Data);
                                Tree->Data = MinNode->Data;
                                Removed = MinNode;    // 수정한 부분
                        }
                        else
                        {
                                BSTNode* Temp = NULL;
                                if (Tree->Left != NULL)
                                        Temp = Tree->Left;
                                else
                                        Temp = Tree->Right;

                                if (Parent->Left == Tree)
                                        Parent->Left = Temp;
                                else
                                        Parent->Right = Temp;
                        }
                }
        }

        return Removed;
}