From: Rene Rivera (grafik.list_at_[hidden])
Date: 2004-03-18 11:28:51
David B. Held wrote:
> "Rene Rivera" <grafik.list_at_[hidden]> wrote in message
>>I look at the implementation and it doesn't do what a rank tree does.
>>It does make it easier to base a rank tree implementation against it.
>>The part that is missing is keeping track of the rank of nodes as the
>>tree changes, the constant time op, that lets one have the logN ops
>>later on. [ Unless I missed something -- So correct me at will ;-) ]
> Hmm...are you sure? Did you look at the rotate_right() and rotate_left()
> functions? The "indexes" wouldn't be correct if you didn't adjust them
> on insert/delete. Essentially, what I call "index" is probably what you
> call "rank".
No I wasn't sure, hence why I said I may have missed something ;-) Yes you are
correct it does have the functionality. It still took me a while to find the
exact place even with your hint above, IndexedNode rotate* and update*, that
has the count.
> does. You might want to take a closer look at that if you haven't
> already. I probably will soon so I can give it a thorough review.
Will do :-)
-- -- Grafik - Don't Assume Anything -- Redshift Software, Inc. - http://redshift-software.com -- rrivera/acm.org - grafik/redshift-software.com - 102708583/icq
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk