Problem 2: Finding the Median in a 2-3-4 Tree
This problem looks at an addition to the 2-3-4 tree of a new function findMedian .
There are four written parts and one programming part for this problem.
For a set of inputs in sorted order, the median value is the element with values both above
and below it.
n + 1 2
n
Part A
For the �rst part, assume the 2-3-4 tree is unmodi�ed, write pseudocode in written-problem.txt
for an algorithm which can �nd the median value.
Part B
For the second part, assume you are now allowed to keep track of the number of descendants during
insertion, write pseudocode in written-problem.txt to update the number of descendants of a
particular node. You may assume other nodes have been updated already.
Part C
For the third part, write pseudocode in written-problem.txt for an e�cient algorithm for
determining the median.
Part D
For the fourth part, determine and justify the complexity of your e�cient approach in Part C in
written-problem.txt .
Part E
For the �nal part, a modi�ed version of the 2-3-4 tree from the workshop solutions has been
provided. Your task is to modify the existing insertTree function to implement your Part B
algorithm and to implement the findMedian function according to your Part C approach. Your
program should construct a 2-3-4 tree for a given set of numbers given on stdin , and output the
median value and the level (starting from the root as level 0) which this value was found on in the 2-
3-4 tree.
You may assume for simplicity that the number of elements inserted into the tree is always odd.