BST-间隔删除/多节点删除

Question

假设我有一个二元搜索树，其中我应该按照标准输入中给定的顺序插入N个唯一编号的键，然后我要删除所有键间隔为I=[最小，最大]的节点，以及与这些节点相邻的所有连接。这给了我很多较小的树，我要以一种特殊的方式将它们合并在一起。更精确地描述问题：

给定包含不同键的BST和间隔I，间隔删除分两个阶段进行。在第一阶段，它将删除关键帧位于I中的所有节点以及与已删除节点相邻的所有边。让生成的图包含k个连通分量T1，。。。，Tk。每个组件都是一个BST，其中根是原始BST中该组件所有节点中深度最小的节点。我们假设树序列Ti被排序，以便对于每个i

编辑：我还应该删除连接节点的任何边，这些边由给定的间隔分隔，这意味着在示例2中连接节点10和20的边被删除，因为间隔[13,15]是“在它们之间”，因此将它们分开。

对于树的空序列，Merge（）给出一个空BST。对于包含树T的单元素序列，Merge（T）=T。对于树的序列T1，。。。，Tk，其中k

完成此操作后，我的任务是找到生成的合并树的深度D和深度D-1中的节点数。即使对于100000个节点的树，我的程序也应该在几秒钟内完成（第4个示例）。

我的问题是我不知道如何做到这一点，甚至不知道从哪里开始。我设法在删除之前构建了所需的树，但仅此而已。如果能实现一个程序来解决这个问题或任何建议，我将不胜感激。最好是用某种C语言编程的。

示例：

输入（第一个数字是要插入空树中的键数，第二个是要按给定顺序插入的唯一键，第三行包含两个数字，表示要删除的间隔）：

13    
10 5 8 6 9 7 20 15 22 13 17 16 18  
8 16

程序的正确输出：3 3，第一个数字是深度D，深度D-1的第二个节点数

输入：

13
10 5 8 6 9 7 20 15 22 13 17 16 18
13 15

正确输出：<代码>4 3

两个示例的图片

示例3：https://justpaste.it/1du6l正确输出：<代码>13 6

示例4：链接正确输出：<代码>58 9

Answer 1

这是一个重要的答案，我将在高层进行讨论。请检查来源以了解详细信息，或询问评论以获得澄清。

全局变量：

• <代码>向量

功能：

• 顺序：查找BST的大小（所有调用组合为O（N））

现在代码（不要惊慌！！！）：

#include <bits/stdc++.h>
using namespace std;

int N = 12;

struct Node
{
    Node* parent=NULL,*left=NULL,*right = NULL;
    int value;
    Node(int x,Node* par=NULL) {value = x;parent = par;}
};

void insert(Node* root,int x){
    if(x<root->value){
        if(root->left) insert(root->left,x);
        else root->left = new Node(x,root);
    }
    else{
        if(root->right) insert(root->right,x);
        else root->right = new Node(x,root);
    }
}

int inorder(Node* root){
    if(root==NULL) return 0;
    int l = inorder(root->left);
    return l+1+inorder(root->right);
}

vector<Node*> roots;
map<Node*,int> smap;
vector<int> prefix;

Node* delInterval(Node* root,int x,int y){
    if(root==NULL) return NULL;
    root->left = delInterval(root->left,x,y);
    root->right = delInterval(root->right,x,y);
    if(root->value<=y && root->value>=x){
        if(root->left) roots.push_back(root->left);
        if(root->right) roots.push_back(root->right);
        return NULL;
    }
    if(root->value<x && root->right && root->right->value>y) {
        roots.push_back(root->right);
        root->right = NULL;
    }
    if(root->value>y && root->left && root->left->value<x) {
        roots.push_back(root->left);
        root->left = NULL;
    }
    return root;

}
Node* merge(int start,int end){
    if(start>end) return NULL;
    if(start==end) return roots[start];
    int total = prefix[end] - (start>0?prefix[start-1]:0);//make sure u get this line
    int mid = (total+1)/2 + (start>0?prefix[start-1]:0); //or this won't make sense
    int ind = lower_bound(prefix.begin(),prefix.end(),mid) - prefix.begin();
    Node* root = roots[ind];
    Node* TL = merge(start,ind-1);
    Node* TR = merge(ind+1,end);
    Node* temp = root;
    while(temp->left) temp = temp->left;
    temp->left = TL;
    temp = root;
    while(temp->right) temp = temp->right;
    temp->right = TR;
    return root;
}

void traverse(Node* root,int depth,map<int, int>& level){
    if(!root) return;
    level[depth]++;
    traverse(root->left,depth+1,level);
    traverse(root->right,depth+1,level);
}

int main(){
    srand(time(NULL));
    cin>>N;
    int* arr = new int[N],start,end;
    for(int i=0;i<N;i++) cin>>arr[i];
    cin>>start>>end;

    Node* tree = new Node(arr[0]); //Building initial tree
    for(int i=1;i<N;i++) {insert(tree,arr[i]);}

    Node* x = delInterval(tree,start,end); //deleting the interval
    if(x) roots.push_back(x);

    //sort the disconnected roots, and find their size
    sort(roots.begin(),roots.end(),[](Node* r,Node* v){return r->value<v->value;}); 
    for(auto& r:roots) {smap[r] = inorder(r);}

    prefix.resize(roots.size()); //prefix sum root sizes, to cheaply find 'root' in merge
    prefix[0] = smap[roots[0]];
    for(int i=1;i<roots.size();i++) prefix[i]= smap[roots[i]]+prefix[i-1];

    Node* root = merge(0,roots.size()-1); //merge all trees
    map<int, int> level; //key=depth, value = no of nodes in depth
    traverse(root,0,level); //find number of nodes in each depth

    int depth = level.rbegin()->first; //access last element's key i.e total depth
    int at_depth_1 = level[depth-1]; //no of nodes before
    cout<<depth<<" "<<at_depth_1<<endl; //hoorray

    return 0;
}