please help Problem 4. (25 points) Describe what additional information to store
ID: 3741442 • Letter: P
Question
please help
Problem 4. (25 points) Describe what additional information to store with each node in a binary search tree so that in addition to tree-search, tree-minimum, tree-maximum, tree-insert, and tree-remove also the following operation could be implemented to run in time O(d), where d is the depth of the tree on which it is executed count(T,k)-returns the number of elements of a tree T with the key smaller than k Describe the modifications and provide an informal pseudocode for the procedure count Describe how to modify insert and delete operations so that when a sequence of insert, delete and count operations is used executed, count still works correctly Assume that the keys of all nodes in the tree are different.Explanation / Answer
Please find my answer.
1) The additional information that should be stored is the number of elements in the left subtree. The idea is that as all the elements in left subtree have value less than the parent. We can skip traversing it if we already their count.
2) The count operation looks like this
int count(root,k)
{
if(root==NULL)
{
return 0;
}
else if(root->val==k)
{
return root->leftnum;
}
else if(root->val<k)
{
return root->leftnum+count(root->right,k);
}
else if(root->val>k)
{
return count(root->left,k);
}
}
3) The insert and delete have to modified only slightly.
a) While doing an insert we check if the element has to be added in the left or right subtree. So if a new element is added in the left subtree then we just increase its leftnum.
b) While deleting we actually delete a leaf element. The steps in the process are
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.