data sctructures

classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

data sctructures

Gustavo Rios
i saw openbsd uses red-black trees inside. I could not figure it out a
motivation for not using AVL, SPL or even something based on
http://user.it.uu.se/~arnea/abs/simp.html.

I could not figure what would it be the best/average/worst cost, i.e.,
O(f(n)) for those method above.

Thanks a lot for your time and cooperation.

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Otto Moerbeek
On Wed, 8 Feb 2006, Gustavo Rios wrote:

> i saw openbsd uses red-black trees inside. I could not figure it out a
> motivation for not using AVL, SPL or even something based on
> http://user.it.uu.se/~arnea/abs/simp.html.
>
> I could not figure what would it be the best/average/worst cost, i.e.,
> O(f(n)) for those method above.
>
> Thanks a lot for your time and cooperation.

Why would red-black trees not be a good choice?

For dictionaries, red-black trees are considered pretty much the best
algorithm. See for example Sedgewick "Algorithms in C", third ed,
especially the conclusions in paragraph 13.6.

        -Otto

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Gustavo Rios
2006/2/8, Otto Moerbeek <[hidden email]>:

>
>
> On Wed, 8 Feb 2006, Gustavo Rios wrote:
>
> > i saw openbsd uses red-black trees inside. I could not figure it out a
> > motivation for not using AVL, SPL or even something based on
> > http://user.it.uu.se/~arnea/abs/simp.html.
> >
> > I could not figure what would it be the best/average/worst cost, i.e.,
> > O(f(n)) for those method above.
> >
> > Thanks a lot for your time and cooperation.
>
> Why would red-black trees not be a good choice?

I just wanted to know which would it be the best choice, and why?
For instance, i don't know the best/average/worst case for the method supplied.
I don't have a simple source of reference where i could see these
metrics, prefereable on the internet.

> For dictionaries, red-black trees are considered pretty much the best
> algorithm. See for example Sedgewick "Algorithms in C", third ed,
> especially the conclusions in paragraph 13.6.
>
>         -Otto

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Ted Unangst-2
On 2/8/06, Gustavo Rios <[hidden email]> wrote:
> I just wanted to know which would it be the best choice, and why?
> For instance, i don't know the best/average/worst case for the method supplied.
> I don't have a simple source of reference where i could see these
> metrics, prefereable on the internet.

what is your working set?  what is the access pattern?

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Claudio Jeker
In reply to this post by Gustavo Rios
On Wed, Feb 08, 2006 at 06:47:15PM -0200, Gustavo Rios wrote:

> 2006/2/8, Otto Moerbeek <[hidden email]>:
> >
> >
> > On Wed, 8 Feb 2006, Gustavo Rios wrote:
> >
> > > i saw openbsd uses red-black trees inside. I could not figure it out a
> > > motivation for not using AVL, SPL or even something based on
> > > http://user.it.uu.se/~arnea/abs/simp.html.
> > >
> > > I could not figure what would it be the best/average/worst cost, i.e.,
> > > O(f(n)) for those method above.
> > >
> > > Thanks a lot for your time and cooperation.
> >
> > Why would red-black trees not be a good choice?
>
> I just wanted to know which would it be the best choice, and why?
> For instance, i don't know the best/average/worst case for the method supplied.
> I don't have a simple source of reference where i could see these
> metrics, prefereable on the internet.
>

http://en.wikipedia.org/wiki/Red-black_tree is a good starting point.
RB trees have a equal properties to AVL trees and are available in
tree(3).

--
:wq Claudio

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Gustavo Rios
Don't get me wrong, i am very confident with openbsd.

Although i am very confident using the openbsd native support for my
needs, all of them have some thing i dislike.

First: i would really enjoy worst case O(log2 n), none of the method i
know so far make such garantee. Another problem is about memory usage:
They all requires 3 pointer (left/right node and the element pointer)
plus space for thing like left/right subtree weight, color, etc.

I could see a paradise for the following scenario: worst case
search/delete/insert in O(log2 N) and space requirement O(3N).

Is that possible? Any suggestions?

Thanks once more.

2006/2/8, Claudio Jeker <[hidden email]>:

> On Wed, Feb 08, 2006 at 06:47:15PM -0200, Gustavo Rios wrote:
> > 2006/2/8, Otto Moerbeek <[hidden email]>:
> > >
> > >
> > > On Wed, 8 Feb 2006, Gustavo Rios wrote:
> > >
> > > > i saw openbsd uses red-black trees inside. I could not figure it out a
> > > > motivation for not using AVL, SPL or even something based on
> > > > http://user.it.uu.se/~arnea/abs/simp.html.
> > > >
> > > > I could not figure what would it be the best/average/worst cost, i.e.,
> > > > O(f(n)) for those method above.
> > > >
> > > > Thanks a lot for your time and cooperation.
> > >
> > > Why would red-black trees not be a good choice?
> >
> > I just wanted to know which would it be the best choice, and why?
> > For instance, i don't know the best/average/worst case for the method supplied.
> > I don't have a simple source of reference where i could see these
> > metrics, prefereable on the internet.
> >
>
> http://en.wikipedia.org/wiki/Red-black_tree is a good starting point.
> RB trees have a equal properties to AVL trees and are available in
> tree(3).
>
> --
> :wq Claudio

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Claudio Jeker
On Wed, Feb 08, 2006 at 09:34:02PM -0200, Gustavo Rios wrote:

> Don't get me wrong, i am very confident with openbsd.
>
> Although i am very confident using the openbsd native support for my
> needs, all of them have some thing i dislike.
>
> First: i would really enjoy worst case O(log2 n), none of the method i
> know so far make such garantee. Another problem is about memory usage:
> They all requires 3 pointer (left/right node and the element pointer)
> plus space for thing like left/right subtree weight, color, etc.
>

Have you actually looked at the link I posted?
"...it can search, insert, and delete in O(log n) time, where n is the
number of elements in the tree." log here is the log of base 2.

> I could see a paradise for the following scenario: worst case
> search/delete/insert in O(log2 N) and space requirement O(3N).
>
> Is that possible? Any suggestions?
>

There is a good reason why there are three pointers -- stack usage.
tree(3) is doing non recursive tree operations to keep the stack usage low
-- stack space is very limited in kernel space. You could go recursive to
save the parent pointer. Oh and your space requirement is wrong.
Btw. I doubt that you can find a algorithm that does search/delete/insert
in O(log2 N) without an additional state/depth stored on a per node basis.

--
:wq Claudio

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Otto Moerbeek
In reply to this post by Gustavo Rios
On Wed, 8 Feb 2006, Gustavo Rios wrote:

> 2006/2/8, Otto Moerbeek <[hidden email]>:
> >
> >
> > On Wed, 8 Feb 2006, Gustavo Rios wrote:
> >
> > > i saw openbsd uses red-black trees inside. I could not figure it out a
> > > motivation for not using AVL, SPL or even something based on
> > > http://user.it.uu.se/~arnea/abs/simp.html.
> > >
> > > I could not figure what would it be the best/average/worst cost, i.e.,
> > > O(f(n)) for those method above.
> > >
> > > Thanks a lot for your time and cooperation.
> >
> > Why would red-black trees not be a good choice?
>
> I just wanted to know which would it be the best choice, and why?
> For instance, i don't know the best/average/worst case for the method supplied.
> I don't have a simple source of reference where i could see these
> metrics, prefereable on the internet.

I don't think you searched very good. Wikipedia has entries on all of
the well known balanced tree alghorithms.

        -Otto
       
>
> > For dictionaries, red-black trees are considered pretty much the best
> > algorithm. See for example Sedgewick "Algorithms in C", third ed,
> > especially the conclusions in paragraph 13.6.
> >
> >         -Otto

Reply | Threaded
Open this post in threaded view
|

Re: data sctructures

Otto Moerbeek
In reply to this post by Gustavo Rios
On Wed, 8 Feb 2006, Gustavo Rios wrote:

> Don't get me wrong, i am very confident with openbsd.
>
> Although i am very confident using the openbsd native support for my
> needs, all of them have some thing i dislike.
>
> First: i would really enjoy worst case O(log2 n), none of the method i
> know so far make such garantee. Another problem is about memory usage:
> They all requires 3 pointer (left/right node and the element pointer)
> plus space for thing like left/right subtree weight, color, etc.
>
> I could see a paradise for the following scenario: worst case
> search/delete/insert in O(log2 N) and space requirement O(3N).
>
> Is that possible? Any suggestions?

From a complexity theory point of view, you are talking nonsense,
since O(3n) equals O(n). I doubt there exists a balanced tree
algorithm that does not need some extra data per node. Of course you
can build an ordinary tree and balance it without extra data per node,
but that's gonna cost you extra time.

At least r-b trees guarantee O(log n) worst case for all operations.
The other algorithms are pretty good as well, though I cannot remember
the exact complexity characteristics.

Oh, if there is an upper bound on the number of entries, a hash table
is also good for dictionaries. But they wast space as well.

        -Otto