Re: [gobo-eiffel-develop] Binary search tree

[Daniel T. <dan...@gm...>]

Colin Paul Adams wrote:
> Daniel,
>
> Mark Howard (ECMA committee member and boss of Eric, Franck and myself
> at AXA Rosenberg) has expressed an interest in Sedgewick's recently
> introduced left-leaning red-black trees. You might want to add these
> too  (I googled and found quite a few hits, so I think there is
> sufficient information available).
>   
Left-leaning red-black trees are now implemented. It was surprising that 
they are slower than red-black and avl trees. In some random benchmarks 
avl and red-black trees show nearly the same performance, whereas plain 
binary search trees are a few percents slower. Left-leaning red-black 
trees are at least 50% slower than avl and red-black trees. The 
benchmark tests only put and delete.
I have to finish the test cases and check a few classes again. It should 
be possible to publish the code this week.