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
complexity.

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.
http://www.ffconsultancy.com/?u
.