|
![](/i/fill.gif) |
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] wsr ac at | -- Ale### [at] univie ac at
__/ | http://www.hjp.at/ | zum Thema Portale in at.linux
Post a reply to this message
|
![](/i/fill.gif) |