|
 |
On 29 Feb 2000 08:15:51 -0500, Nieminen Juha wrote:
>Ron Parker <ron### [at] povray org> wrote:
>: Actually, I have an associative array (of sorts) that I've written here
>: that has an O(1) increment, not amortized. It's a threaded 2-3 tree.
>: Indexing is still, of course, O(log n), as are insertion and deletion.
>
> How can the increment of the iterator be O(1) non-amortized with a tree?
>Unless you have next-pointers in each node making the container also a
>linked list... (well that _is_ a solution but it takes a little bit more
>memory).
That's the "threaded" part. It's actually a doubly-linked list. Memory is
cheaper than processor time in this application.
--
These are my opinions. I do NOT speak for the POV-Team.
The superpatch: http://www2.fwi.com/~parkerr/superpatch/
My other stuff: http://www2.fwi.com/~parkerr/traces.html
Post a reply to this message
|
|
