Sorted Array to 2-4+ Tree in Linear Time

Question

I need help with the following question:

Describe an algorithm that given a sorted array of size n builds a 2-4+ tree that contains the same keys as the array. The algorithm should run in time O(n).

I already know how to build a red black tree from a sorted array in linear time (because the amortized time of the function that fixes the tree after insert is O(1)).

However, I don't see how this trick helps me with 2-4+ trees: Does it have anything to do with the amortized fixing time after insert with these trees ? (and I don't know what it is...)

Or am I completely wrong ?

By the way, I can't use the trick that we've seen in class of constructing a 2-4 tree from a red black tree in O(n), it must be a straightforward array to 2-4+ tree algorithm.

Thanks in advance

Answer 1

There is a close connection between red/black trees and 2-3-4 B-trees. In fact, the two are isometries of one another, meaning that any 2-3-4 B-tree can be encoded as a red-black tree and vice-versa. This older question discusses the details.

Using this connection, you should be able to adapt the algorithm for building a ree-black tree in linear time to instead construct a 2-3-4 B-tree in linear ime. You could either build the red-black tree and then iterate over it to determine the structure of the B-tree you want to construct, or could try changing the algorithm to directly build the B-tree.

Hope this helps!