On Monday 09 Jan 2006 6:28 pm, Adrian Hey wrote:
That said, it should still do a pretty good job of balancing and the balancing mechanism itself and node size will have little impact on look up times (for example).
..or maybe not. Looking at this code again reminds me of something strange that happened when I tested the RedBlack tree implementation Chris Okasaki sent me a while back. It required precisely twice as many comparisons as the RedBlack code Malcolm Wallace supplied. I'm not sure exactly why, but I suspect it probably had something to do with the use of either guarded equational style code (or maybe if then elses) rather than "case compare x y of.." style code. The FGL implementation seems to do the same thing. So I guess lookup performance might not be too good either, at least for non-trivial comparisons. Regards -- Adrian Hey