 |
|
|
|
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 30/01/2012 05:08 PM, Kevin Wampler wrote:
> I don't follow this reasoning, since you only need the resulting tree to
> be a valid BST at the end of the computation, but it can take any
> convenient state when you're adding the individual elements. For
> instance is there some reason why the following algorithm sketch doesn't
> work?
>
> 1) Flatten BSTs into sorted arrays / linked lists O(n+m)
> 2) Merge arrays O(n+m)
> 3) Rebuild BST from sorted array O(m+n)
>
> That should give you O(m+n) time to perform the union, which is better
> than Andrew's suggestion.
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?
(I can kind of see how that would work if the data is in an array;
arrays support random access, so you could just binary chop the array
and keep the results as a BST. I'm trying to figure out if you can do
anything with a linked list, which does /not/ support random access...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Le 31/01/2012 10:23, Invisible a écrit :
> On 30/01/2012 05:08 PM, Kevin Wampler wrote:
>
>> I don't follow this reasoning, since you only need the resulting tree to
>> be a valid BST at the end of the computation, but it can take any
>> convenient state when you're adding the individual elements. For
>> instance is there some reason why the following algorithm sketch doesn't
>> work?
>>
>> 1) Flatten BSTs into sorted arrays / linked lists O(n+m)
>> 2) Merge arrays O(n+m)
>> 3) Rebuild BST from sorted array O(m+n)
>>
>> That should give you O(m+n) time to perform the union, which is better
>> than Andrew's suggestion.
>
> 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?
>
> (I can kind of see how that would work if the data is in an array;
> arrays support random access, so you could just binary chop the array
> and keep the results as a BST. I'm trying to figure out if you can do
> anything with a linked list, which does /not/ support random access...)
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)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
>> 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.
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...)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
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
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 1:23 AM, Invisible wrote:
> 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?
>
> (I can kind of see how that would work if the data is in an array;
> arrays support random access, so you could just binary chop the array
> and keep the results as a BST. I'm trying to figure out if you can do
> anything with a linked list, which does /not/ support random access...)
Although I haven't done it myself, I believe if you actually do the
complexity analysis you'll find that the lack of random access doesn't
change the complexity of the obvious recursive algorithm except by a
constant factor.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
Kevin Wampler <wam### [at] u washingtonedu> wrote:
> 1) Flatten BSTs into sorted arrays / linked lists O(n+m)
> 2) Merge arrays O(n+m)
> 3) Rebuild BST from sorted array O(m+n)
If there's a way to build a BST from a sorted array on linear time,
you are right. There probably is. It saves the need for rebalancing
after each insertion.
Since elements in a BST usually have pointers to each other anyways,
and since merging two linked lists can be done without requiring any
additional memory, this whole operation might be possible using O(1)
memory. (Although building a BST from a linked list might require
O(log n) memory.)
--
- Warp
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 7:49 AM, Kevin Wampler wrote:
>
> Although I haven't done it myself, I believe if you actually do the
> complexity analysis you'll find that the lack of random access doesn't
> change the complexity of the obvious recursive algorithm except by a
> constant factor.
Ok, I actually looked at it and the obvious algorithm does take O(n
log(n)) on a linked list. But you I think you can modify it prettily
easily to run in O(n) by treating the linked list as a list of trees of
size 1, and iteratively running through the list and forming larger
trees from the smaller ones. There's probably some fiddily details to
get balancing just right while ensuring combining the sub-trees takes
O(1) though, but I think it'll all work out.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 8:29 AM, Warp wrote:
>
> Since elements in a BST usually have pointers to each other anyways,
> and since merging two linked lists can be done without requiring any
> additional memory, this whole operation might be possible using O(1)
> memory.
I have the same intuition, although I don't care enough to code it up
work out the details.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 1/31/2012 8:43, Kevin Wampler wrote:
> I have the same intuition, although I don't care enough to code it up work
> out the details.
I tried that on math tests a couple times. It didn't fly. :-)
--
Darren New, San Diego CA, USA (PST)
People tell me I am the counter-example.
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
| |
|
|
On 02/02/2012 03:07 AM, Darren New wrote:
> On 1/31/2012 8:43, Kevin Wampler wrote:
>> I have the same intuition, although I don't care enough to code it up
>> work out the details.
>
> I tried that on math tests a couple times. It didn't fly. :-)
Huh. It worked for Pierre de Fermat. :-P
But I have to say I'm relieved. Sometimes I worry that education has
sunk to the level where that kind of thing might be OK. Like when I paid
for university tuition only to have some professor of computer science
tell me that "float supports numbers up to about 2^38 which is, oh, far
more than the number of atoms in the entire universe".
(Pro tip: Number of atoms in 12g of carbon = 2^77 or so. The number of
atoms in the /entire universe/ is clearly much, much larger.)
Post a reply to this message
|
|
| |
| |
|
|
|
|
| |
|
|
