implementing trees in STL

[C++ Shark]

Hi,

which stl class is good for creating search trees? I am looking for
something flexible, that allows me to search for a required state (of
matrices, graphs, etc.) quickly.

thanks in advance,
Craig.

[Gianni Mariani]

C++ Shark wrote:

Hi,

which stl class is good for creating search trees? I am looking for
something flexible, that allows me to search for a required state (of
matrices, graphs, etc.) quickly.

Check out

std::map and std::multimap.

[Kevin Goodsell]

Gianni Mariani wrote:

C++ Shark wrote:

Hi,

which stl class is good for creating search trees? I am looking for
something flexible, that allows me to search for a required state (of
matrices, graphs, etc.) quickly.

Check out

std::map and std::multimap.

Those are not really good for *creating* search trees, but they are
probably implemented *using* search trees (or possibly skip-lists -- I'd
be interested to know if any implementations have used skip-lists
instead of balanced search trees).

For creating search trees, I don't see any particular part of the
standard library that would be very useful. It's the kind of thing that
is usually done in a class.

-Kevin
--
My email address is valid, but changes periodically.
To contact me please use the address from a recent posting.

[Jerry Coffin]

In article <U3*****************@newsread3.news.pas.earthlink. net>,
us*********************@neverbox.com says...

[ ... ]

Those are not really good for *creating* search trees, but they are
probably implemented *using* search trees (or possibly skip-lists -- I'd
be interested to know if any implementations have used skip-lists
instead of balanced search trees).

I've yet to see any based around skip lists -- the range of variation
I've seen so far has been from Red/Black trees to AVL trees.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Gianni Mariani]

Jerry Coffin wrote:
....

I've yet to see any based around skip lists -- the range of variation
I've seen so far has been from Red/Black trees to AVL trees.

What's a skip list ?

[Jerry Coffin]

In article <bk********@dispatch.concentric.net>, gi*******@mariani.ws
says...

Jerry Coffin wrote:
...

I've yet to see any based around skip lists -- the range of variation
I've seen so far has been from Red/Black trees to AVL trees.

What's a skip list ?

The inventor's original paper from the Communications of the ACM is
available here:

ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf

Shortcomings: the C++ standard requires logarithmic complexity for
std::map, std::multimap, std::set and set::multiset in the worst case,
and while skip lists provide good expected complexity, IIRC their worst
case is linear.

--
Later,
Jerry.

The universe is a figment of its own imagination.

[Frank Schmitt]

Gianni Mariani <gi*******@mariani.ws> writes:

Jerry Coffin wrote:
...

I've yet to see any based around skip lists -- the range of
variation I've seen so far has been from Red/Black trees to AVL
trees.

What's a skip list ?

It's a list where some of the nodes contain additional pointers to
nodes farther away - every 2nd node points 2 nodes away, every 4th
node points 4 nodes away etc. - every Nth node has an additional
pointer N nodes away (called a pointer of order N).
In a perfect skip list, searching is always O(log n), but insertion
and deletion are O(N) - so you can use randomized skip lists, where
the probability that a given node gets a pointer of order N is
1/2^N - in worst case, this leads to an ordinary list, but in
average, it's as good as a perfect skip list.

for further reading, see
W. Pugh, Skip lists: A probabilistic alternative to balanced trees.
In Proc. Workshop of Algorithms and Data Structures, p. 437-449,
1989, Lecture Notes in Computer Science 382

W. Pugh, Skip lists: A probabilistic alternative to balanced trees.
Comm. ACM, 33(6):668-676, 1990
HTH & kind regards
frank

--
Frank Schmitt
4SC AG phone: [phone]
e-mail: frankNO DOT SPAMschmitt AT 4sc DOT com