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$ – Yuval Filmus May 31 '17 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.