Let T be a binary search tree. Suppose we want to include a field v. size, the n
ID: 3799585 • Letter: L
Question
Let T be a binary search tree. Suppose we want to include a field v. size, the number of items stored in the subtree of v, at each node v. Given T, describe an algorithm that will populate all the size fields in T. What is the running time of your algorithm? Now suppose we make modifications to T by inserting or removing items. For each modification i.e., an insertion or a removal describe the modifications that have to be made to the size fields of the nodes in T. How much time will such modifications take? Using the binary search tree 011 Figure 3.4, insert an item with key equal to 52 and show the changes that have to be made on the size fields of the nodes in the tree. Now, remove the item with key equal to 75. Again, show the changes that have to be made 011 the size fields of the nodes in the tree.Explanation / Answer
Question A:
Algorithm to set the size of a node in Tree T. The size of a node is the number of all elements in the subtree of v. This will be sum of all children in left subtree + all children in right subtree + 1 (the node itself). To fill the size of all nodes in T, call this algorithm with the tree's root i.e set_size(T.root). This algorithm is of O(n) since it travels each node of the tree exactly once.
algorithm: set_size(v)
if v=NULL
return
else
size_left=size(v.left_child)
size_right=size(v.right_child)
set v.size = size_left + size_right + 1
end if
Question b:
For insertion and deletion, we need to update parent's size along with subtree whenever a subtree is changed. This will be O(log n), as we only traverse log n nodes for insertion or deletion.
So in insertion algorithm,
we need to make changes, parent.size = parent.size + 1 for a non-NULL parent, as we try to try to find the correct place where the node is to be attached.
In the algorithm for deletion, we need to set parent.size = parent.size - 1 for a non-NULL parent, since we will remove a node
question C: can't be answered as the figure is not attached.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.