nu.kanga.list.mud-dev

8293: [MUD-Dev] Re: Red Black Tree ?

On 02:40 PM 10/9/98 -0600, I personally witnessed T. Alexander Popiel
jumping up to say:
>In message:  <199810092109.PAA07254@darklock.com>
>             Caliban Tiresias Darklock <caliban@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."

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.
--------------------------------------------------------------------------
As the fire burneth a wood, and the flame setteth the mountains on fire; 
So persecute them with thy tempest, and make them afraid with thy storm. 
---------------------------[ Psalms, 83:14-15 ]---------------------------
Caliban Tiresias Darklock     <caliban@darklock.com> | "Hell, you don't   
Darklock Communications   <http://www.darklock.com/> |  know me."         
FREE KEVIN MITNICK!   <http://www.kevinmitnick.com/> |    - Charles Manson  
--------------------------------------------------------------------------
And remember, if you don't kiss Hank's ass he'll kick the shit out of you.
--------------------------------------------------------------------------