8. 이제 원소 삭제가 구현되어 있는 함수를 살펴보겠습니다. 특정 노드를 삭제하면, 해당 노드의 부모 노드 포인터를 조정해야 합니다. 그래서 삭제 구현 함수는 부모 노드 포인터가 새로 가리켜야 할 노드의 주소를 반환하도록 설정했습니다. 함수 이름을 deleteValue()로 설정한 것은 delete는 C++ 표준에 정의되어 있는 키워드이기 때문입니다.
void deleteValue(int value)
{
root = delete_impl(root, value);
}
private:
node* delete_impl(node* start, int value)
{
if (!start)
return NULL;
if (value < start->data)
start->left = delete_impl(start->left, value);
else if (value > start->data)
start->right = delete_impl(start->right, value);
else
{
if (!start->left) // 자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우
{
auto tmp = start->right;
delete start;
return tmp;
}
if (!start->right) // 오른쪽 자식 노드만 없는 경우
{
auto tmp = start->left;
delete start;
return tmp;
}
// 자식 노드가 둘 다 있는 경우
auto succNode = successor(start);
start->data = succNode->data;
// 오른쪽 서브 트리에서 후속(successor)을 찾아 삭제
start->right = delete_impl(start->right, succNode->data)
}
return start;
}
};