Re: Using Red-Black Trees

[Gene <gene.ressler@gmail.com>]

On Nov 15, 5:46 pm, "Randy Brukardt" <ra...@rrsoftware.com> wrote:
> "Alex Mentis" <f...@invalid.invalid> wrote in message
>
> news:ibm2op$m1i$1@news.eternal-september.org...
> ...
>
> > There's a Red-Black Tree in Ada.Containers?!  Can someone tell me where
> > to find it in the ARM?
>
> It's not explicit. One of the possible implementations of the ordered sets
> and maps is to use a Red-Black tree; presumably this is what GNAT's
> implementation is doing.
>
>                                     Randy.

Indeed, here is a fragment of the GNAT ordered map implementation via
rb trees:

   type Node_Type is limited record
      Parent  : Node_Access;
      Left    : Node_Access;
      Right   : Node_Access;
      Color   : Red_Black_Trees.Color_Type := Red_Black_Trees.Red;
      Key     : Key_Type;
      Element : Element_Type;
   end record;