题目链接

• 利用父节点跟踪避免删除操作使用递归重复找次大值

时间复杂度$O(h)$

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
struct BIT{
    int val;
    BIT *left;
    BIT *right;
    BIT(int _val): val(_val),left(NULL),right(NULL){}
}*root;
void insert(BIT* &node,int x){
    if(!node) node=new BIT(x);
    else if(node->val>x) insert(node->left,x);
    else insert(node->right,x);
}
void remove(BIT* &node,int x){
    if(!node) return;
    if(x<node->val) remove(node->left,x);
    else if(x>node->val) remove(node->right,x);
    else{
        if(!node->left&&!node->right) node=NULL,delete node;
        else if(!node->left) node=node->right;
        else if(!node->right) node=node->left;
        else{
            //找次大节点替换，利用父节点跟踪避免回溯
            auto p=node->left;
            auto pre=node;
            while(p->right) pre=p,p=p->right;
            node->val=p->val;
            if(pre->right==p) pre->right=p->left;
            else node->left=p->left;
            delete p;
        }
    }
}
int get_pre(BIT* node,int x){
    if(!node) return -INF;
    if(node->val>=x) return get_pre(node->left,x);
    return max(node->val,get_pre(node->right,x));
}
int get_suc(BIT* node,int x){
    if(!node) return INF;
    if(node->val<=x) return get_suc(node->right,x);
    return min(node->val,get_suc(node->left,x));
}
int main(){
    int n;
    cin>>n;
    while(n--){
        int opt,x;
        cin>>opt>>x;
        if(opt==1) insert(root,x);
        if(opt==2) remove(root,x);
        if(opt==3) cout<<get_pre(root,x)<<'\n';
        if(opt==4) cout<<get_suc(root,x)<<'\n';
    }
}