[Gllug] [somewhat OT] Redblack trees

[Adrian McMenamin]

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
> >nodes.
> 
> 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
http://lists.gllug.org.uk/mailman/listinfo/gllug