[MUD-Dev] Re: Red Black Tree ?

[Caliban Tiresias Darklock]

On 12:28 PM 10/9/98 -0100, I personally witnessed Valerio Santinelli
jumping up to say:
>
>Can anybody explain me what's a red black tree or just point me to a page
>with some docs about it ?

A red-black tree should be defined in any basic algorithm text in the
section on binary trees; they're fundamentally balanced binary trees, with
a few minor differences.

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, and each
node is thought of as being colored red or black... under the restriction
that all leaves are black, two consecutive red nodes are not permitted
along any path from the root, and all leaves of the tree are at the same
"black depth" -- i.e. if you could the number of black nodes from the root
of the tree to any leaf, not counting the leaf itself, the number is the
same. The concepts of red and black are purely a bookkeeping device, and
don't imply anything else about the underlying data; it's just useful in
the process of keeping the tree balanced.

I think of the red-black tree as being sort of a middle ground between the
B-tree (which goes through some rather complex acrobatics to handle trees
stored primarily on disk instead of in memory) and a "simple" binary tree.
I'm personally more partial to top-down splays, which dynamically rearrange
themselves during every search so the most commonly accessed nodes are
closer to the top of the tree. They're a bit more complex, though, and
aren't entirely suited to disk-based systems without some modification. 

My own database design uses a sort of bastard construction which indexes by
hashed values (collision resolution by rehash) through a binary tree, and
operates in a very similar fashion to a stacked hard drive: it's divided
into clusters, which are allocated in noncontiguous chains of DB "pages",
and when reading or writing to the DB all the data passes through a
transparent compression routine. I've probably done several things wrong,
since I refused to read or refer to existing DB code when designing and
writing mine, but it seems to work reasonably well. 
--------------------------------------------------------------------------
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 at 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.
--------------------------------------------------------------------------