Le 31/01/2012 14:11, Invisible a écrit :
>>> Question: If you have a bunch of data in sorted order, how do you build
>>> a BST from that faster than O(n log n) times?
>>
>> Use a model BST, filled with 1 to n+m. (or whatever please you, you just
>> need n+m values)
>>
>> Then run in order through the BST, and replace each element with the top
>> of the list that you remove. (it's not the BST traditional replace
>> (which might rebalance), just a basic substitution)
> 
> By "in order", I presume you mean from smallest to greatest, rather than
> (say) from the top of the tree to the bottom?
> 
> Seems to me you need to know the size of the tree before hand.
> 
> Notice that if we have two arbitrary sets S and T, then
> 
>   |S| min |T| <= |S union T| <= |S| + |T|
> 
> In other words, we don't know the size of the result set until we
> actually construct it.

Which is the size of the list, so no problem there.

> 
> Is there some way to build the resulting tree incrementally, if you
> don't know what its final size should be? (I'm guessing "no", if only
> because the result tree needs to be balanced...)

Make a few study on balanced tree of various size, see if you can get
some pattern based on the number of nodes.

For instance, let N be the number of nodes.
If N = 2x+1, the top level is one node giving access to x on each side.

Which means we know the form for half the number of node (when odd).

5 ?  might as well be:

      3
     / \
    2   4
   /     \
  1       5

or

       3
     /   \
    1     5
     \   /
      2 4

or

       4
      / \
     2   5
    / \
   1   3


I let you think how to deal with even number...
-- 
Software is like dirt - it costs time and money to change it and move it
around.<br/><br/>


Just because you can't see it, it doesn't weigh anything,
and you can't drill a hole in it and stick a rivet into it doesn't mean
it's free.

Post a reply to this message