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]

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]

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

 

[Jerry Coffin]

[ ... ]

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.

 

[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]

Jerry Coffin wrote:
...

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.

 

[Frank Schmitt]

Jerry Coffin wrote:
...

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