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
.



Relevant Pages

  • Re: Red-black trees?
    ... fixed size arrays, so indexing is O. ... your complexity? ... I'm surprised you haven't come across this in real applications: ...
    (comp.programming)
  • Re: Red-black trees?
    ... fixed size arrays, so indexing is O. ... your complexity? ... I'm surprised you haven't come across this in real applications: ...
    (comp.programming)
  • Re: Subscript and other optimizations was Re: 77 Levels
    ... arrays) was known at that time. ... indexing must have been rejected as inappropriate for COBOL. ... procedure division -- something not applicable to FORTRAN ... Consider that 'move 0 to numeric-field' ...
    (comp.lang.cobol)
  • Re: Safe subset of C?
    ... so no raw C arrays. ... > Heuristic tools increase in complexity without bounds and they never ... > but C requires cast from void pointer to structure pointer. ... Downcasting can be performed safely with the proper instrumentation. ...
    (comp.lang.c)
  • Re: boolean variable in expression
    ... Thanks Alan. ... really wanted to avoid setting up arrays and then indexing into them. ... Array indexing is the obvious workaround to this limitation. ... >The Basic code reveals all the horrors which Delphi's strongly typed ...
    (alt.comp.lang.borland-delphi)