I was experimenting with a WAVL Tree code I wrote. One thing I noticed is that on average, there was much less rebalancing actions after delete than after insert. In fact, average rebalances after insert were about 2.5 per insert, and 1.8 per delete. This results were consistent, even when we inserted and deleted in completely random order. What possible explanation could there be? Thanks!

  • $\begingroup$ Well, you're performing different operations. It's not so surprising that they have different complexity. Try estimating heuristically (but from the code!) the average number of rebalancing actions after an insert and a delete. $\endgroup$ Commented May 31, 2017 at 18:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.