[Gllug] [somewhat OT] Redblack trees

[David Damerell]

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.

-- 
David Damerell <damerell at chiark.greenend.org.uk> Distortion Field!
Today is Leicesterday, Presuary.
Tomorrow will be Brieday, Presuary.
-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug