<!-- MHonArc v2.4.4 -->
<!--X-Subject: [MUD-Dev] Re: Red Black Tree ? -->
<!--X-From-R13: Qnyvona Fverfvnf Rnexybpx <pnyvonaNqnexybpx.pbz> -->
<!--X-Date: Fri, 9 Oct 1998 14:10:49 -0700 -->
<!--X-Message-Id: 199810092109.PAA07254#darklock,com -->
<!--X-Content-Type: text/plain -->
<!--X-Reference: 199809251503.IAA02560#cashew,snugharbor.com.snugharbor.com -->
<!--X-Reference: 361E2BAC.E9C9C8FE#mediacom,it -->
<!--X-Head-End-->
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<html>
<head>
<title>MUD-Dev message, [MUD-Dev] Re: Red Black Tree ?</title>
<!-- meta name="robots" content="noindex,nofollow" -->
<link rev="made" href="mailto:caliban#darklock,com">
</head>
<body background="/backgrounds/paperback.gif" bgcolor="#ffffff"
text="#000000" link="#0000FF" alink="#FF0000" vlink="#006000">
<font size="+4" color="#804040">
<strong><em>MUD-Dev<br>mailing list archive</em></strong>
</font>
<br>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
<br clear=all><hr>
<!--X-Body-Begin-->
<!--X-User-Header-->
<!--X-User-Header-End-->
<!--X-TopPNI-->
Date:
[ <a href="msg00140.html">Previous</a>
| <a href="msg00142.html">Next</a>
]
Thread:
[ <a href="msg00136.html">Previous</a>
| <a href="msg00142.html">Next</a>
]
Index:
[ <A HREF="author.html#00141">Author</A>
| <A HREF="#00141">Date</A>
| <A HREF="thread.html#00141">Thread</A>
]
<!--X-TopPNI-End-->
<!--X-MsgBody-->
<!--X-Subject-Header-Begin-->
<H1>[MUD-Dev] Re: Red Black Tree ?</H1>
<HR>
<!--X-Subject-Header-End-->
<!--X-Head-of-Message-->
<UL>
<LI><em>To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
<LI><em>Subject</em>: [MUD-Dev] Re: Red Black Tree ?</LI>
<LI><em>From</em>: Caliban Tiresias Darklock <<A HREF="mailto:caliban#darklock,com">caliban#darklock,com</A>></LI>
<LI><em>Date</em>: Fri, 09 Oct 1998 14:07:11 -0700</LI>
<LI><em>Reply-To</em>: <A HREF="mailto:mud-dev#kanga,nu">mud-dev#kanga,nu</A></LI>
</UL>
<!--X-Head-of-Message-End-->
<!--X-Head-Body-Sep-Begin-->
<HR>
<!--X-Head-Body-Sep-End-->
<!--X-Body-of-Message-->
<PRE>
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#darklock,com> | "Hell, you don't
Darklock Communications <<A HREF="http://www.darklock.com/">http://www.darklock.com/</A>> | know me."
FREE KEVIN MITNICK! <<A HREF="http://www.kevinmitnick.com/">http://www.kevinmitnick.com/</A>> | - Charles Manson
--------------------------------------------------------------------------
And remember, if you don't kiss Hank's ass he'll kick the shit out of you.
--------------------------------------------------------------------------
</PRE>
<!--X-Body-of-Message-End-->
<!--X-MsgBody-End-->
<!--X-Follow-Ups-->
<HR>
<ul compact><li><strong>Follow-Ups</strong>:
<ul>
<li><strong><A NAME="00142" HREF="msg00142.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>
<ul compact><li><em>From:</em> "T. Alexander Popiel" <popiel#snugharbor,com></li></ul>
</UL></LI></UL>
<!--X-Follow-Ups-End-->
<!--X-References-->
<UL><LI><STRONG>References</STRONG>:
<UL>
<LI><STRONG><A NAME="00135" HREF="msg00135.html">[MUD-Dev] Re: Red Black Tree ?</A></STRONG>
<UL><LI><EM>From:</EM> Valerio Santinelli <tanis#mediacom,it></LI></UL></LI>
</UL></LI></UL>
<!--X-References-End-->
<!--X-BotPNI-->
<UL>
<LI>Prev by Date:
<STRONG><A HREF="msg00140.html">[MUD-Dev] Re: Current Projects</A></STRONG>
</LI>
<LI>Next by Date:
<STRONG><A HREF="msg00142.html">[MUD-Dev] Re: Red Black Tree ?</A></STRONG>
</LI>
<LI>Prev by thread:
<STRONG><A HREF="msg00136.html">[MUD-Dev] Re: Red Black Tree ?</A></STRONG>
</LI>
<LI>Next by thread:
<STRONG><A HREF="msg00142.html">[MUD-Dev] Re: Red Black Tree ?</A></STRONG>
</LI>
<LI>Index(es):
<UL>
<LI><A HREF="index.html#00141"><STRONG>Date</STRONG></A></LI>
<LI><A HREF="thread.html#00141"><STRONG>Thread</STRONG></A></LI>
</UL>
</LI>
</UL>
<!--X-BotPNI-End-->
<!--X-User-Footer-->
<!--X-User-Footer-End-->
<ul><li>Thread context:
<BLOCKQUOTE><UL>
<LI><STRONG>[MUD-Dev] Re: Laws of Online World Design</STRONG>, <EM>(continued)</EM>
<ul compact>
<LI><strong><A NAME="00162" HREF="msg00162.html">[MUD-Dev] Re: Laws of Online World Design</A></strong>,
J C Lawrence <a href="mailto:claw#under,engr.sgi.com">claw#under,engr.sgi.com</a>, Tue 13 Oct 1998, 02:45 GMT
</LI>
<LI><strong><A NAME="00173" HREF="msg00173.html">[MUD-Dev] Re: Laws of Online World Design</A></strong>,
Hans-Henrik Staerfeldt <a href="mailto:hhs#cbs,dtu.dk">hhs#cbs,dtu.dk</a>, Tue 13 Oct 1998, 11:28 GMT
</LI>
</ul>
</LI>
<LI><strong><A NAME="00135" HREF="msg00135.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>,
Valerio Santinelli <a href="mailto:tanis#mediacom,it">tanis#mediacom,it</a>, Fri 09 Oct 1998, 15:29 GMT
<UL>
<LI><strong><A NAME="00136" HREF="msg00136.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>,
T. Alexander Popiel <a href="mailto:popiel#snugharbor,com">popiel#snugharbor,com</a>, Fri 09 Oct 1998, 18:08 GMT
</LI>
<LI><strong><A NAME="00141" HREF="msg00141.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>,
Caliban Tiresias Darklock <a href="mailto:caliban#darklock,com">caliban#darklock,com</a>, Fri 09 Oct 1998, 21:10 GMT
<UL>
<LI><strong><A NAME="00142" HREF="msg00142.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>,
T. Alexander Popiel <a href="mailto:popiel#snugharbor,com">popiel#snugharbor,com</a>, Fri 09 Oct 1998, 21:42 GMT
<UL>
<LI><strong><A NAME="00143" HREF="msg00143.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>,
Caliban Tiresias Darklock <a href="mailto:caliban#darklock,com">caliban#darklock,com</a>, Fri 09 Oct 1998, 23:06 GMT
<UL>
<LI><strong><A NAME="00144" HREF="msg00144.html">[MUD-Dev] Re: Red Black Tree ?</A></strong>,
Ben Greear <a href="mailto:greear#cyberhighway,net">greear#cyberhighway,net</a>, Sat 10 Oct 1998, 06:55 GMT
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
</UL>
</LI>
<LI><strong><A NAME="00134" HREF="msg00134.html">[MUD-Dev] Re: Marion's Tailor Problem</A></strong>,
Koster, Raph <a href="mailto:rkoster#origin,ea.com">rkoster#origin,ea.com</a>, Fri 09 Oct 1998, 14:59 GMT
</LI>
</UL></BLOCKQUOTE>
</ul>
<hr>
<center>
[ <a href="../">Other Periods</a>
| <a href="../../">Other mailing lists</a>
| <a href="/search.php3">Search</a>
]
</center>
<hr>
</body>
</html>
