BST - 間隔の削除/複数のノードの削除

Question

標準入力で与えられた順序でN個の一意の番号のキーを挿入するはずのバイナリ検索ツリーがあるとしたら、キーを持つすべてのノードを削除します間隔I = [min、max]であり、これらのノードに隣接するすべての接続も含む。これは私に、私が特定の方法で一緒にマージすることになるたくさんの小さな木を与えます。

異なるキーと間隔Iを含むBSTの場合、間隔の削除は2つのフェーズで機能します。最初のフェーズでは、キーがIにあるすべてのノードと、削除されたノードに隣接するすべてのエッジを削除します。結果のグラフをk個の連結成分T1、...、Tkを含むものとする。各コンポーネントはBSTです。ここで、ルートは元のBSTのこのコンポーネントのすべてのノードの中で最小の深さを持つノードです。我々は木のシーケンスTiがソートされ、各iについて、< j、TiのすべてのキーがTjのキーよりも小さくなると仮定する。第2段階では、木材Tiが併合されて1つのBSTが形成される。この操作はMerge（T1、...、Tk）で表されます。その出力は次のように反復して定義されます：

EDIT：ノードを接続するエッジを削除することになります。これは、指定された間隔で区切られています。例2では、​​ノード10と20を接続するエッジが削除されます[13,15]は「それらの間に」あり、こうしてそれらを分ける。

ツリーの空のシーケンスの場合、Merge（）は空のBSTを返します。 木Tを含む1要素シーケンスの場合、Merge（T）= T. 木のシーケンスT1、...、Tk（k> 1）について、A1 < A2 < ... <はシーケンスすべてのツリーT1、...、Tkの和集合に格納されたキーのうち、昇順にソートされたもの。また、m =⌊（1 + k）/2⌋とし、TsをAmを含む木とする。そして、Merge（T1、...、Tk）は3つの木Ts、TL = Merge（T1、...、Ts-1）とTR = Merge（Ts + 1、...、 Tk）。これらのツリーは、以下の2つのリンクを確立することによってマージされる.TLは、Tsの最小キーを格納するノードの左サブツリーとして付加され、TRはTsの最大キーを格納するノードの右サブツリーとして付加される。

これを実行した後、結果として得られるマージツリーの深さDと、深さD-1のノードの数を見つけることです。私のプログラムは、100000ノードのツリーであっても数秒で終了するはずです（第4例）。

私の問題は、これを行う方法や開始する場所についての手がかりがないことです。削除する前に目的のツリーを構築することができましたが、それはそれです。 私はこの問題やアドバイスを解決するプログラムの実装には感謝しています。好ましくは、いくつかのC言語プログラミング言語である。

例：

入力（最初の番号が空のツリーに挿入されるキーの数は、第二の所定の順序で挿入されるユニークキーであり、第三の行はに間隔を意味する2つの数値をcontaints ）削除する：深さD-1で3 3、最初の数は深さDである、ノードの第二の数

入力：

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

プログラムの正しい出力

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

正しい出力：4 3

pictures of the two examples

例3：https://justpaste.it/1du6l 正しい出力：13 6

例4：link 正しい出力：58 9

Answer 1

これは大きな答えです、私は話します詳細については、ソースを調べてください。または、説明のためにコメントで尋ねてください。

グローバル変数：

• vector<Node*> roots：すべての新しい樹木の根を格納します。
• map<Node*,int> smap：
  • inorder：：サイズを見つけるmerge

  機能で簡単にバイナリ検索のためのrootsベクトルのプレフィックス和、各新しいツリー、店舗にとっては大き

• vector<int> prefixですBST（すべての呼び出しはO（N）を組み合わせて呼び出す）
• delInterval：私は、ルートが間隔内にない場合は、両方の子がかもしれないは新しいツリーのルーツになります。最後の2つのifは編集でその特殊なエッジをチェックします。ポストオーダーのすべてのノードでこれを実行します。 （O（N））
• merge：startにあるすべての新しいルートをendにマージしてrootsにマージします。最初に、total（接頭辞の合計がroots、つまりprefix）という新しいツリーのメンバーが見つかりました。 midは、あなたの質問でmを示しています。 indはmid番目のノードを含むルートのインデックスです。これを変数rootで取得します。左/右のサブツリーを再帰的に構築し、左/右の大部分のノードにそれらを追加する。 O（N）の複雑さ。
• traverse：levelマップでは、ツリーの深さごとにノード数を計算します。 （に。logN個）、unordered_mapは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; 
}