no handwriting please Answer the following questions: (a) A team of biologists k
ID: 3813526 • Letter: N
Question
no handwriting please
Answer the following questions: (a) A team of biologists keeps information about DNA structures in an AVL tree using as key the specific weight (an integer) of a structure. The biologists routinely ask questions of the type: "Are there any structures in the tree with specific weights between a and b (both inclusive)", and they hope to get an answer as soon as possible. Design an efficient algorithm that given integers a and b returns true if there is a key x in the tree such that a lessthanorequalto x lessthanorequalto b, and returns false if no such key exits. Describe your algorithm in pseudo-code. (b) What (and why) is the time complexity of the algorithm?Explanation / Answer
Void inorder(int key,node * root, int data,int &N)
{
if(root==null)
return;
inorder(key,root->left,&data);
data[*N++]=root->key:
inorder(key,root->lright,&data);
}
int binarysearch(int *data,int key,int f, int l)
{
if(f>l) return -1;
int mid= (f+l)/2;
if(data[mid]>key)
binarysearch(data,key,f,mid-1);
else
binarysearch(data,key,mid+1,l);
}
int iskeypresent(int key,node *root,int &data, int a, int b)
{
if(root==NULL)return 0;
int N=-1;
inorder(key,root,data,&N);
if(N<2) return 0;
int mid1= binarysearch(data,a,0,&N);
if(mid1<0 || mid1==N) return 0;
else
int mid2= binarysearch(data,b,0,&N);
if(mid2<0 || mid2==0) return 0;
return 1
}
Complexity O(NlogN) where N is size of dataset
Inorder traversal takes O(N) & it calls binary search log(N) so O(NlogN)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.