I need answers to these 6 questions. i need detailed info on about the sequence
ID: 3889785 • Letter: I
Question
I need answers to these 6 questions. i need detailed info on about the sequence of nodes. not the result of the function. PLEASE do NOT answer this if you do not know floor and ceiling in a BST and are good in algorithms. i have posted this question a few times and get no good answers. please read the question !!! thanks :)
Give the sequence of nodes examined when the methods in BST are used to compute each of the following quantities for the tree drawn below: a. floorC"Q" .select (5) c ceilingC"Q") d. rank ("J") e. sizeC"D", "T") f. keysC"D", "T")Explanation / Answer
void findFloorCeil(Node* root, Node* &floor, Node* &ceil, int key)
{
// base case
if(root == nullptr)
return;
// if node with key's value is found, both floor and ceil is equal
// to the current node
if (root->data == key)
{
floor = root;
ceil = root;
}
// if given key is less than the root node, recuse for left subtree
else if (key < root->data)
{
// update ceil to current node before recursing in left subtree
ceil = root;
findFloorCeil(root->left, floor, ceil, key);
}
// if given key is more than the root node, recuse for right subtree
else
{
// update floor to current node before recursing in right subtree
floor = root;
findFloorCeil(root->right, floor, ceil, key);
}
}
1.Above algorithm is fairly simple to understand applying it on given tree with floor("Q"):
2.Select(k) basically means finding k'th smallest element in the BST.We can find that out by doing in order traversal of the tree storing that in an array and returning k'th location element.
4.rank("J") . If the given key is equal to the key at the root, we return the number of keys t in the left subtree; if the given key is less than the key at the root, we return the rank of the key in the left subtree; and if the given key is larger than the key at the root, we return t plus one (to count the key at the root) plus the rank of the key in the right subtree.In our case:
6. keys("D","T") . Gives us keys between given two keys.step:
1) If value of root’s key is greater than k1, then recursively call in left subtree.
2) If value of root’s key is in range, then print the root’s key.
3) If value of root’s key is smaller than k2, then recursively call in right subtree.
void Print(struct node *root, int k1, int k2)
{
/* base case */
if ( NULL == root )
return;
/* Since the desired o/p is sorted, recurse for left subtree first
If root->data is greater than k1, then only we can get o/p keys
in left subtree */
if ( k1 < root->data )
Print(root->left, k1, k2);
/* if root's data lies in range, then prints root's data */
if ( k1 <= root->data && k2 >= root->data )
printf("%d ", root->data );
/* If root->data is smaller than k2, then only we can get o/p keys
in right subtree */
if ( k2 > root->data )
Print(root->right, k1, k2);
}
In our case:
e.size("D","T") it is just length of output of keys().
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.