Re: Red-black trees?

Ben Pfaff wrote:
CBFalconer <cbfalconer@xxxxxxxxx> writes:
You are misunderstanding the O notation, which doesn't get
altered by the occasional slower operation.

No, you are confusing worst-case complexity with amortized

Actually the best- and (ensemble) average-case complexities of his insertion
function may also be O(n) the same as the worst case because the resizes
occur at the same sizes regardless of the transaction history.

Dr Jon D Harrop, Flying Frog Consultancy Ltd.