[Gllug] [somewhat OT] Redblack trees
adrian at newgolddream.dyndns.info
Tue Jul 13 23:14:54 UTC 2010
On Mon, 2010-07-12 at 17:21 +0100, David Damerell wrote:
> On Saturday, 10 Jul 2010, Adrian McMenamin wrote:
> >I am using the wikipedia entry -
> >http://en.wikipedia.org/wiki/Red-black_tree - on this as a guide to
> >getting it right - and it generally seems ok.
> >But working on insertion I am puzzled by the example given on the
> >wikipedia entry for "case 5" which clearly - to me - to create a tree
> >which breaks what the article describes as "property 5" - that all paths
> >from a node to its leaves should pass through the same number of black
> Note that in the diagram there, 1-2-3 have small black circles above
> them but 4-5 do not; 1-2-3 are subtrees with black nodes at their
> heads, but 4-5 are subtrees not known to have black nodes at their
> heads (because they descend from black node U).
> In fact, I think the article is a bit confused, full stop. There's a
> missing section between the properties and the algorithms which should
> explain how it's all meant to work.
I finally managed to write some code that works - the wikipedia article
was less than helpful in the end
Gllug mailing list - Gllug at gllug.org.uk
More information about the GLLUG