complexity of turning a sorted array to a 2-4 B tree

What is the complixety of turning a sorted 开发者_如何学编程array of size n to a legal 2-4 B tree?

What would it be if the array wasn't sorted.

I believe that the first answer should be O(logn) (As many splits that we'll have to do) and the second answer should be O(nlogn+logn)=O(nlogn), because of the sorting.

Thank you.

---

You can definitely convert a sorted array into a 2-4 tree in O(n) time. See Ralf Hinze's Constructing Red-Black Trees for details. His algorithms are written in terms of red-black trees, but red-black trees are essentially the same as 2-4 trees (a black node with two black children is a 2 node, a black node with one red child is a 3 node, and a black node with two red children is a 4 node).

And, yes, if the array is unsorted, you are going to be stuck with O(n log n) time (unless you know something special about the data that lets you sort it in better than O(n log n) time).

---

Well, if you're doing something to n items, it seems likely that you'll need to spend at least O(n) time doing stuff.

The first thing that I'd think of would be spinning through all n items and inserting each into the tree. Since insertion is O(log n), that's O(n * log n) time...but it completely ignores whether or not your n items are sorted.

If your n items are sorted, you can probably build a binary search tree in O(n) time. And I bet a similar thing could work for a 2-4 B tree.

---

The trick to convert an ordered list into any kind of tree is as follows:

1. Given a number of elements N, write a function (i.e. shape(N)) that is capable of determining how many elements should go in every subtree (for instance, for an AVL tree, shape(6) -> [2, 3] as one element goes into the node).

2. Write a (recursive) function that takes N elements from the beginning of the list and returns a subtree containing those elements and a pointer to the sublist containing the remaining elements.