假设我有一个二叉搜索树,在其中我应该按照标准输入给我的顺序插入 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
:将所有位于 的新根合并start
到end
索引中roots
。首先我们找到新树的总成员total
(使用roots
ie 的前缀总和prefix
)。在你的问题中mid
表示m
。ind
是包含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] 删除。
我来说两句