c++ - 二分探索木の遅延削除

Question

コードに遅延削除を実装したいと考えています。ノードがいつ「削除」されたか、または削除済みとしてマークされたかを追跡するために、ブール値を追加しました。実際に変更する方法がわかりません。これが私の削除と挿入の方法です。削除しようとしましたが、挿入はしませんでした。insert メソッドが多くのチェックを行う必要があることは確かです。お知らせ下さい。

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;
}