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 very interesting. Now that Sedgewick 
updated his slides, it should be straight forward to implement at least 
the extend/put feature, based on the binary search tree classes. But 
such an implementation has the drawback of using a parent attribute in 
the tree nodes, whereas that is not required for left-leaning red-black 
trees. On the other hand I am not sure if there could be a satisfying 
implementation without a parent attribute in the nodes.
I will try to implement them in the next week(s), as soon as I have 
enough time. It will be interesting to see, if it is as simple as 
Sedgewick says. I am skeptic that it is faster due to the smaller code size.