[MUD-Dev] Re: Red Black Tree ?

[Ben Greear]

On Fri, 9 Oct 1998, Caliban Tiresias Darklock wrote:

> On 02:40 PM 10/9/98 -0600, I personally witnessed T. Alexander Popiel
> jumping up to say:
> >In message:  <199810092109.PAA07254 at darklock.com>
> >             Caliban Tiresias Darklock <caliban at darklock.com> writes:
> >>
> >>In a red-black tree, data is stored only in the lowest-level nodes
> >>(leaves), other nodes in the tree being used only as an index,
> >
> >*cough*
> >
> >Where did you get this idea?  I routinely store data in the internal
> >nodes of a red-black tree, with the leaves being represented by a
> >single sentinel.  This is the recommended implementation from my
> >algorithms books, too, so I don't think I've unwittingly mutated
> >the algorithm...
> 
> My understanding of red-black trees comes from the Binstock/Rex book
> "Practical Algorithms For Programmers" (1995)... where I find, on page 281:
> "A red-black tree is, at heart, a binary search tree. However, it makes use
> of two new concepts. First, in a red-black tree, data is stored only in the
> *leaves* of the tree. That is, only the nodes without children contain
> actual data. Interior nodes are purely for reference. Second, each node is
> thought of as being colored red or black."

For the record, I have no real understanding of RB Trees...  However, I
implemented one in college...and we most certainly did use the internal
nodes as well.  I can see no reason not to:  You would be wasting half
of your space, and guaranteeing O(log(n)), whereas the other way (internal
storage), your average should be better (Though by a small amount.)

> 
> And that's where it came from. My *formal* algorithmic training comes from
> the Tanenbaum/Augenstein text "Data Structures Using Pascal" (1981), which
> says exactly nothing about red/black trees. This is one of several
> deficiencies that led me to later purchase the Binstock/Rex volume.

Ben Greear (greear at cyberhighway.net)  http://www.primenet.com/~greear 
Author of ScryMUD:  mud.primenet.com 4444
http://www.primenet.com/~greear/ScryMUD/scry.html