如何在伸展树中实现删除函数？节点定位后树重组遇阻

云原生阿岚

2026-8-10

伸展树Remove函数问题修正

原代码存在的问题

语法错误：函数声明行末尾多了分号，会导致编译失败
未处理边界情况：左子树为空时，largest(L)会访问空指针；右子树为空时，R->parent会触发空指针异常
树重组逻辑错误：执行splay(big)后，big已成为左子树的新根，此时应该操作big而非原左子树节点L，原L可能不再是左子树的根节点

修正后的代码

node* remove(int k) {
    node* del = find(k);
    if (del == nullptr) { // 处理待删除节点不存在的情况
        return nullptr;
    }

    node* L = del->left;
    node* R = del->right;

    // 断开待删除节点与左右子树的关联
    if (L != nullptr) {
        L->parent = nullptr;
    }
    if (R != nullptr) {
        R->parent = nullptr;
    }

    delete del;

    // 左子树为空，直接返回右子树作为新根
    if (L == nullptr) {
        return R;
    }

    // 找到左子树的最大节点并伸展为左子树的根
    node* big = largest(L);
    splay(big);

    // 将右子树挂载到big的右节点，并更新父指针
    if (R != nullptr) {
        big->right = R;
        R->parent = big;
    } else {
        big->right = nullptr; // 确保右节点为空时的正确性
    }

    return big;
}