Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > only get the minimum but *also* the maximum element in O(1) time. 

> This needs a pointer from the root directly to the smallest leaf and 
> largest leaf, doesn't it?  Not to dispute; I'm just trying to understand 
> how it's a constant-time operation. O(lg N) is easy to understand.

  Yes, you obviously require a pointer to the first and last nodes, but
these pointers can be kept updated at no extra cost (in other words,
keeping these pointers doesn't change the computational complexity of
any of the operations, and are very lightweight to keep updated).

  Even without the pointers getting the min and max values is O(log n).
With a heap getting the max value is an O(n) operation.

> And by "three pointers" you're including a pointer to the parent, yes? 

  Right. (AFAIK self-balancing binary trees require the parent pointer
at each node, and they also make things like traversing the tree using
iterators much easier.)

> What's the flag? the red/black flag?

  Yes. Keeping the tree balanced requires some ancillary data besides
the pointers.

-- 
                                                          - Warp

Post a reply to this message