Итеративное удаление узла из дерева двоичного поиска

Question

Некоторое время над этим работал. В случае, когда есть два дочерних узла, возникает ошибка сегментации. Я не знаю, как решить проблему. Я почти уверен, что другие случаи верны, но в настоящее время я борюсь со случаем, когда удаляемый узел имеет 2 дочерних узла.

bool BinarySearchTree::remove(BinarySearchTree::TaskItem val) {
    if(!exists(val))
        return false;
    else{
        TaskItem* cur = root;
        TaskItem* parent = nullptr;

        if(size == 1){ // only one node in tree
            delete cur;
            root = nullptr;
            size--;
            return true;
        }
        else if(*cur == val && (!cur->right || !cur->left)){// root node is target, with one child node
            if(!cur->right){
                root = cur->left;
                delete cur;
            }
            else{
                root = cur->right;
                delete cur;
            }
            size--;
            return true;
        }

        while(!(*cur==val)){
            if(val.priority < cur->priority){
                parent = cur;
                cur = cur->left;
            }
            else{
                parent = cur;
                cur = cur->right;
            }
        }

        if(!cur->right && !cur->left){ // no child nodes
            if(parent->right == cur){
                parent->right = nullptr;
                delete cur;
            }
            else{
                parent->left = nullptr;
                delete cur;
            }
        }
        else if(cur->right && cur->left){ // 2 child nodes
            TaskItem* success = cur->right;
            TaskItem* par_success = cur;

            while(!success->left){
                par_success = success;
                success = success->left;
            }
            cur->priority = success->priority;
            cur->description = success->description;
            if(par_success->left == success){
                par_success->left = nullptr;
            }
            else{
                par_success->right = nullptr;
            }
            delete success;
        }
        else{// one child node
            if(!cur->right){ // child node on the left
                if(parent->right == cur){
                    parent->right = cur->left;
                    delete cur;
                }
                else{
                    parent->left = cur->left;
                    delete cur;
                }
            }
            if(!cur->left){
                if(parent->right == cur){
                    parent->right = cur->right;
                    delete cur;
                }
                else{
                    parent->left = cur->right;
                    delete cur;
                }
            }
        }
        size--;
        return true;
    }
}

Answer 1

Вы разыменовываете указатели без проверки null:

        while(!(*cur==val)){
            if(val.priority < cur->priority){
                parent = cur;
                cur = cur->left;
            }
            else{
                parent = cur;
                cur = cur->right;
            }
        }

Если cur->left или cur->right равны null (я полагаю, это указатели), доступ к ним в *cur будет segfault .

Здесь:

        else if(cur->right && cur->left){ // 2 child nodes
            TaskItem* success = cur->right;
            TaskItem* par_success = cur;

            while(!success->left){
                par_success = success;
                success = success->left;
            }

Вы напрямую обращаетесь к указателю null. Если cur->right->left (success->left) равно null, вы получите доступ к указателю null в следующей итерации.