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

彼得·克鲁帕

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

给定一个包含不同键的 BST 和区间 I,区间删除分两个阶段进行。在第一阶段,它删除所有键在 I 中的节点以及与删除节点相邻的所有边。让结果图包含 k 个连通分量 T1,...,Tk。每个组件都是一个 BST,其中根是原始 BST 中该组件的所有节点中深度最小的节点。我们假设树 Ti 的序列经过排序,使得对于每个 i < j,Ti 中的所有键都小于 Tj 中的键。在第二阶段,树 Ti 合并在一起形成一个 BST。我们用 Merge(T1,...,Tk) 表示这个操作。其输出循环定义如下:

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

对于空的树序列,Merge() 给出一个空的 BST。对于包含树 T 的单元素序列,Merge(T) = T。对于树 T1,...,Tk 的序列,其中 k > 1,让 A1< A2< ... < An 是键的序列存储在所有树 T1,...,Tk 的联合中,按升序排序。此外,让 m = ⌊(1+k)/2⌋ 并且让 Ts 是包含 Am 的树。然后,Merge(T1,...,Tk) 给出通过合并三棵树 Ts 创建的树 T,TL = Merge(T1,...,Ts-1) 和 TR = Merge(Ts+1,..., TK)。通过建立以下两个链接来合并这些树:附加 TL 作为存储 Ts 最小键的节点的左子树,附加 TR 作为存储 Ts 最大键的节点的右子树。

完成此操作后,我的任务是找到生成的合并树的深度 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

沙赫里亚尔汗

这是一个很大的答案,我将在高级别讨论。请查看来源以获取详细信息,或在评论中询问以进行澄清。

全局变量

  • vector<Node*> roots :存储所有新树的根。
  • map<Node*,int> smap :对于每棵树,存储它的大小
  • vector<int> prefix:roots向量的前缀和,便于二分查找merge

功能

  • inorder : 查找 BST 的大小(所有调用组合为 O(N))
  • delInterval: 主题是,如果根不在区间内,它的两个孩子都可能是新树的根。最后两个if检查您编辑中的特殊边缘。对每个节点执行此操作,后序。(上))
  • merge:将所有位于 的新根合并startend索引中roots首先我们找到新树的总成员total(使用rootsie 的前缀总和prefix)。在你的问题中mid表示mind是包含mid第 -th 个节点的根的索引,我们在root变量中检索它现在递归构建左/右子树并将它们添加到最左/最右节点。O(N) 复杂度。
  • traverse: 在level地图中,计算每个深度树的节点数。(O(N.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;
}

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章