On 19/07/2010 18:21, Andrei Alexandrescu wrote:
I also suggest you read up on "left-leaning red-black trees" for a
recent alternative approach that simplifies the code a fair amount.
A few month ago (12-15) I have also made that suggestion to Steve.
Meanwhile I am not that sure that LL RB Trees do offer significant
complexity reduction... . R. Sedgewick's original implementation in Java
is not bullet proofed.
Don't get me wrong LL RBTree have a certain appeal but read your self.
--In case that you don't want to use this link :
http://t-t-travails.blogspot.com/2008/04/left-leaning-red-black-trees-are-hard.html
--Here a quote <
Last Monday, I started implementing left-leaning red-black trees,
expecting to spend perhaps 15 hours on the project. I'm here more than
60 hours of work later to tell you that left-leaning red-black trees are
hard to implement, and contrary to Sedgewick's claims, their
implementation appears to require approximately the same amount of code
and complexity as standard red-black trees.
>
Meanwhile I am convinced that Skiplists are more interesting as RBTree
alternative data-structure. Besidet QT folks are using the skiplist
algo. for their MAP implementation.
@Andrei, hope you have noticed that Steve's dcollections allow the
replacement of the underlaying data-structute. ;)
So IMHO let's spend some time in implementing the skiplist data-structure.
Finally > I would like to see std.datastructures. for core
tree,list,graphs etc structures..
A+.
Bjoern
