从BST中提取节点，保留假节点

Question

我正在编写一个带有双向迭代器的 STL Conrainer BST。为了呈现 .end() 我有“假节点”，这是树的最右边的儿子。我在提取时遇到问题：每当我的代码到达“假节点”时，它就会错误地工作。我在节点中做了一个标志，以便将其标记为假节点，但我只是不知道如何检查这种情况。我尝试放置几个“if”语句，但它们不起作用。有人可以帮我吗？ 这是我的代码：

node_type* ExtractHelper(node_type* root, Key key) {
        if (root == nullptr) {
            return root;
        } else if (key < root->value) {
            root->left = ExtractHelper(root->left, key);
        } else if (key > root->value) {
            root->right = ExtractHelper(root->right, key);
        } else {
            if (root->left == nullptr) {
                value_type* temp = root->right;
                DeleteNode(root);
                if (temp) {
                    temp->parent = root->parent;
                }
                return temp;
            } else if (root->right == nullptr) {
                value_type* temp = root->left;
                DeleteNode(root);
                if (temp) {
                    temp->parent = root->parent;
                }
                return temp;
            }
            value_type* temp = GetLeftest(root->right);
            root->value = temp->value;
            root->right = ExtractHelper(root->right, temp->value);
        }
        return root;
    }

我尝试写这样的东西：

if (temp) {
    temp->parent = cur->parent;
    temp->right = cur->right;
    cur->right->parent = temp
}

但这不起作用。所以我实际上正在等待一些修改的建议。谢谢:)

Answer 1

您可以通过构造来避免此问题，方法是确保

end()

返回一个永远不会成为任何 BST 一部分的节点：

static node_type _end;
node_type* end() const { return &_end; }
node_type* end() { return &_end; }