Describe what additional information to store with each node in a binary search
ID: 3762155 • Letter: D
Question
Describe what additional information to store with each node in a binary search tree so that in addition to search, insert, and delete also the following operation could be implemented to run in time O(h), where h is the height of the tree on which it is executed:
count(T, k) - return the number of elements in a tree T with the key smaller than k.
Describe the modifications and provide an informal pseudocode (not a code!!) for the procdeure count.
Describe how to modify insert and delete operations so that when a sequence of insert, delete and count operations is used, count still works correctly.
Assume that all nodes stored in the tree have different keys.
Explanation / 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