From: David B. Held (dheld_at_[hidden])
Date: 2001-06-03 21:19:46
From: John E. Potter <jpotter_at_[hidden]>
>On Sun, 3 Jun 2001 dheld_at_[hidden] wrote:
>You are missing the average case.
Ah, yes. I didn't do a very thorough analysis, I see. ;) Thanks for
clearing that up.
>> However, one of the rotate operations requires knowing the
>> size of a right subtree.
>I think you missed something there.
Apparently, I did. Looking back at my final code, I see that the
rotates don't really need the size after all. Your analysis was
quite correct, and to my suprise, corresponds to my
modification. That makes me feel better, because I never liked
having the size in there in the first place. I wrote a dirty little
__rbi_iverify() method to check whether the indexes and sizes
are correct. This method does depend on the size, but not
critically. It just means that I have to be a little more clever in
how it is written. ;) Thanks for the tip.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk