c++ - 二叉搜索树懒删除

Question

我想在我的代码中实现延迟删除。我添加了一个布尔值来跟踪节点何时“删除”/标记为已删除。我不确定要实际更改哪些方法。这是我的删除和插入方法。我尝试了删除，但没有尝试插入。我确信插入方法必须进行大量检查。请指教。

template<class Comparable>
bool search_tree<Comparable>::remove(treeNode<Comparable> * &root,
        const Comparable &x) {
    if (root == NULL)
        return false;

    if (x < root->data)
        return remove(root->lftChild, x);
    if (root->data < x)
        return remove(root->rtChild, x);

    root->deleted = true;
    return true;
}

template<class Comparable>
bool search_tree<Comparable>::insert(treeNode<Comparable> * &root,
        const Comparable &x) {
    if (root == NULL) {
        root = new treeNode<Comparable>(x, NULL, NULL);
        return true;
    } else if (x < root->data)
        return insert(root->lftChild, x);
    else if (root->data < x)
        return insert(root->rtChild, x);

    return false;
}

Answer 1

您的插入函数应该按原样工作，除非 x 等于已删除的项目，否则它将不会被插入。如果 x 等于 root->data，您需要确保 deleted 为 false。

而且您的删除功能看起来应该可以正常工作。