By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
449,081 Members | 862 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 449,081 IT Pros & Developers. It's quick & easy.

implementing trees in STL

P: n/a
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.
Jul 19 '05 #1
Share this Question
Share on Google+
6 Replies


P: n/a
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.

Jul 19 '05 #2

P: n/a
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.

Jul 19 '05 #3

P: n/a
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.
Jul 19 '05 #4

P: n/a
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 ?

Jul 19 '05 #5

P: n/a
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.
Jul 19 '05 #6

P: n/a
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: +49 89 700763-0
e-mail: frankNO DOT SPAMschmitt AT 4sc DOT com
Jul 19 '05 #7

This discussion thread is closed

Replies have been disabled for this discussion.