Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
I am wondering if there is an algorithm that, given a sorted array, allows you to build a binary search tree in linear time?
I am facing a problem where I have about 8 million elements in a file that need to be loaded into a BST so O(n) would be vastly preferable to O(n log n) if it's possible.
I think the best way is to make a recursive algorithm. You could divide your input in half (approx), and keep out the central element. Then you recursively build a tree with the left subarray which will be the left child of the central element, and equivalently the tree resulting from the right subarray will be the right child.
By induction you can prove that the resulting tree is balanced since you are building trees of the same size at each side (+/- 1 node). Also is easy to prove that the result is a binary search tree, by construction.
With respect to the complexity, every node in the recursive execution tree takes constant time. Since you have a number of nodes proportional to the number of elements in your input, then the algorithm is O(n).
Although this is not exactly the question you asked, you can also build balanced trees from ordered data in an online manner. That is to say, you could walk your array from left-to-right building up partial results, and if some asked you to stop after k items you could finish building the tree in log k time (with the total time being O(k), and the extra storage required O(log k).
To state this another way, you could read the data from a pipe and create the tree (via auxilliary structures) without first putting it all in an array first (thereby avoiding the O(n) storage required for the array). Algorithms to do this for red-black trees can be found hidden in the SML NJ library implementation of red-black sets. The theoretical underpinnings can be found in Okasaki's Purely Functional Data Structures.
I have found a similar algorithm for AVL (height-balanced) trees, but I have not (yet) published it, as I don't know whether it is part of the published literature for AVL trees.
