Quite a while ago, I proposed a linear time algorithm to construct trees from sorted lists. The algorithm relied on the segregation of data and internal nodes. This meant that for a list of $latex n$ data items, $latex 2n-1$ nodes were allocated (but only $latex n$ contained data; the $latex n-1$ others just contained pointers.
While segregating structure and data makes sense in some cases (say, the index resides in memory but the leaves/data reside on disk), I found the solution somewhat unsatisfactory (but not unacceptable). So I gave the problem a little more thinking and I arrived at an algorithm that produces a tree with optimal average depth, with data in every node, in linear time and using at most $latex \Theta(\lg n)$ extra memory.
View original post 663 more words