Re: Using Red-Black Trees

[Stephane Carrez <Stephane.Carrez@gmail.com>]

Hi!

On 11/13/2010 02:10 PM, Alex Mentis wrote:
> Bj�rn wrote:
> 
>> I need a self-balancing binary search tree (for a Bentley/Ottmann
>> implementation), such as the red-black tree that is now part of
>> Ada.Containers. I need basic operations like insert/remove, next/prev
>> and find. However, the GNAT implementation of this data structure
>> seems a bit scary to me and I'm not really sure how to instantiate the
>> generics and what operations to use. Would someone be able to provide
>> some example of usage? And yes, I'am aware of that a lot of the other
>> container implementations uses this structure. I was hoping for
>> something a bit more boiled down.
>>
>> Regards,
>> Bj�rn
> 
> There's a Red-Black Tree in Ada.Containers?!  Can someone tell me where
> to find it in the ARM?

GNAT uses the Red-Black tree for the implementation of ordered maps and sets.

You should use Ada.Containers.Ordered_Maps instead.  Instantiation is similar
to the Hashed_Maps but you should need to specify the comparison operator "<".

See http://www.adaic.org/standards/05rm/html/RM-A-18-6.html
(Likewise for the Indefinite_Ordered_* packages)

Stephane