On 11 Sep 2000 16:39:05 -0400, Ron Parker wrote:
>On 11 Sep 2000 09:40:08 -0400, Warp wrote:
>>  What is the amortized O()-time for ++ then?
>
>amortized time is still O(log(n)) in that case, unless I missed something.

You are missing something: The iterator doesn't have to start at the
root of the tree (assuming the map is implemented as a tree)
to find the next item, so the the search time is generally much
faster than log(n).

In fact, for a splay tree, it only has to follow one pointer.

For a binary tree where each node has a pointer to its parent, it is
a bit more complicated: In 50% of the cases, the current node will be
the left leaf, so two pointer operations (up, right down) are needed.
In 25 % it is the right leaf of a node on the left of its parent, so 4
operations (up, up, right, left) are needed, etc:

1/2 *2 + 1/4 * 4 + 1/8 * 6 + 1/16 * 8 ...

works out to exactly 4, which is also O(1).

Oops, I just noticed that only my leave nodes have data, but I'm too
lazy to calculate this now for a normal binary tree, and it should even
be better, anyway.

Note that a binary tree without "up" pointers doesn't have any way
to get from one node to the next, so the iterator will have to do
additional bookkeeping in this case.

	hp

-- 
   _  | Peter J. Holzer    | Nicht an Tueren mangelt es,
|_|_) | Sysadmin WSR       | sondern an der Einrichtung (aka Content).
| |   | hjp### [at] wsracat      |    -- Ale### [at] univieacat
__/   | http://www.hjp.at/ |       zum Thema Portale in at.linux

Post a reply to this message