The specifications are as listed in the pdf file. Relevent files are in the .rar file.

The specifications are as listed in the pdf file. Relevent files are in the .rar file.


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.