[Gllug] [somewhat OT] Redblack trees

Adrian McMenamin adrian at newgolddream.dyndns.info
Sat Jul 10 16:55:52 UTC 2010


For algorithm gurus...

For amusement I am working on some C++ code to implement a simple
redblack tree (I shouldn't ave to explain here why I find this sort of
thing a worthwhile pursuit on a day when it's generally too hot to go
outside).

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.

Have I missed something here?

-- 
Gllug mailing list  -  Gllug at gllug.org.uk
http://lists.gllug.org.uk/mailman/listinfo/gllug




More information about the GLLUG mailing list