We define an AVL binary search tree to be a tree with the binary search tree pro
ID: 3785406 • Letter: W
Question
We define an AVL binary search tree to be a tree with the binary search tree property where, for each node in the tree, the height of its children differs by no more than 1. For this problem, assume we have a team of biologists that keep information about DNA sequences in an AVL binary search tree using the specific weight (an integer) of the structure as the key. The biologists routinely ask questions of the type, “Are there any structures in the tree with specific weight between a and b, 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 exists a key x in the tree such that a x b, and false if no such key exists in the tree. Describe your algorithm in pseudocode and English. What is the time complexity of your algorithm? Explain
Explanation / Answer
Pseudocode:
bool Specific_Search(Node *T)
{
if(T==Null)//reached the depth of the tree and no such key found..then
{
return false;//returning false because no such structure found
}
if(((T->key)>=a) &&((T->key)<=b))//checking key is in between a and b inclusive(a<=x<=b)
{
//if yes //if such key present
return true; //returning true
}
else// T->key is not such/required then we have to move left/right
{
if(b<T->key)//b(max value in range)is less than the current node key..then we have to move left.. because in avl //tree left subtree values are smaller than current node key value
{
return Specific_Search(T->left);//calling left node recursively...
}
else if(a>T->key)//a(min value in range)is greater than the current node key..then we have to move right..
{//because in avl tree right subtree values are greater than current node key value
return Specific_Search(T->right);//calling right node recursively...
}
}
}
//The time complexity of this algorithm is O(log n)
//because at every..(upto finding the correct key..)we are leaving half the nodes(subtree)..
//means at every level, the number of nodes need to check are reduced by half..
// in avl tree from top to depth/upto correct key position, we just check logn node keys only
//hence the complexity would be O(logn)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.