Question

Does (2, 4) tree storing a set of entries will always have the same structure regardless of the order in which the entries are inserted?

Answer 1

Answer:

No. One property of a (2, 4) tree is that all external nodes are at the same depth. The multi-way search tree of the example does not adhere to this property. Your classmate claims that a (2,4) tree storing a set of entries will always have the same structure, regardless of the order in which the entries are inserted.

..

Answer 2

Answer:

Here is a sketch of an algorithm:

For each input number, determine to which interval it belongs, and update corresponding sum: S[int_log(x)] += x.

Compute prefix sum for array S: foreach i: C[i] = C[i-1] + S[i].

Filter array C to keep only entries with values lower than next power of 2