Re: Red-black trees?



Richard Harter wrote:
On Thu, 20 Nov 2008 00:55:19 +0000, Jon Harrop
<jon@xxxxxxxxxxxxxxxxx> wrote:
If my previous interpretation was correct then this is just an array of
fixed size arrays, so indexing is O(1). Where does the log come from in
your complexity?

The problem I was thinking of was the resizing of the array while
maintaining a "no long pauses" policy. In a real application
there isn't a problem; it's only when you consider a hypothetical
machine with an infinite memory that the issue arises.

I'm surprised you haven't come across this in real applications: it is not
uncommon.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?u
.