David B. Held wrote:
"Rene Rivera" <grafik.list@redshift-software.com> wrote in message news:4058C84D.2000008@redshift-software.com...
[...] 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