From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-0.9 required=5.0 tests=BAYES_00,FORGED_GMAIL_RCVD,
	FREEMAIL_FROM autolearn=no autolearn_force=no version=3.4.4
X-Google-Thread: 103376,8e7ac81a215f128c
X-Google-NewGroupId: yes
X-Google-Attributes: gida07f3367d7,domainid0,public,usenet
X-Google-Language: ENGLISH,ASCII
Path: 
 g2news2.google.com!postnews.google.com!k11g2000vbf.googlegroups.com!not-for-mail
From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Using Red-Black Trees
Date: Tue, 16 Nov 2010 08:10:09 -0800 (PST)
Organization: http://groups.google.com
Message-ID: 
 <46306fd9-21dc-40df-88e7-fc7e568399a4@k11g2000vbf.googlegroups.com>
References: <2419e829-6f45-4075-9005-b9876beb8aaa@r6g2000vbf.googlegroups.com>
 <ibm2op$m1i$1@news.eternal-september.org> <ibsd7q$nru$1@munin.nbi.dk>
NNTP-Posting-Host: 134.240.241.2
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1289923809 19268 127.0.0.1 (16 Nov 2010 16:10:09
 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Tue, 16 Nov 2010 16:10:09 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: k11g2000vbf.googlegroups.com; posting-host=134.240.241.2;
 posting-account=-BkjswoAAACC3NU8b6V8c50JQ2JBOs04
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/4.0 (compatible; MSIE 8.0; Windows NT 6.0;
 Trident/4.0; SLCC1; .NET CLR 2.0.50727; .NET CLR 3.0.30729; .NET CLR
 3.5.30729; InfoPath.2; .NET4.0C; .NET4.0E),gzip(gfe)
Xref: g2news2.google.com comp.lang.ada:16491
Date: 2010-11-16T08:10:09-08:00
List-Id: <comp.lang.ada>

On Nov 15, 5:46=A0pm, "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?! =A0Can someone tell me whe=
re
> > to find it in the ARM?
>
> It's not explicit. One of the possible implementations of the ordered set=
s
> and maps is to use a Red-Black tree; presumably this is what GNAT's
> implementation is doing.
>
> =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 =A0 R=
andy.

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 :=3D Red_Black_Trees.Red;
      Key     : Key_Type;
      Element : Element_Type;
   end record;