treebinary-search-treenodesavl-tree

What does the worst-case scenario for the 'Delete' operation of an AVL tree look like in practice?

I found this stack overflow answer: https://stackoverflow.com/a/28846533/10061169, which indicates that the AVL tree 'Delete' operation can have O(log(N)) rotations. I'm currently trying to find proof for this statement by constructing an example. I found this: https://cs.stackexchange.com/questions/128245/worst-case-for-avl-tree-balancing-after-deletion. However, when deleting node '19', in the respective example, then 2 rotations will be performed. This is not even close to Log(N). Log(N) of the example, would be Log(20) = 4.3.

I did some more investigation myself on how to build an AVL tree which will give O(log(n)) rotations when deleting a single node. This is the structure I found:

AVL Tree

Deleting node '25' would cause the AVL tree to perform the following rotations:

  1. Left rotate
  2. Right rotate
  3. Left rotate
  4. Right rotate

Taking log(n), gives log(12) = 3.6, which (if rounded up) aligns with 4 rotations. This proofs the statement made in the stack overflow answer: https://stackoverflow.com/a/28846533/10061169.

Is this what the worst-case scenario for the 'Delete' operation of an AVL tree looks like in practise? Or is there more to be discovered?

Solution

  • The referenced answer correctly identifies a worst case.

    You write that:

    ...2 rotations will be performed. This is not even close to Log(N). Log(N) of the example, would be Log(20) = 4.3.

    But Big O cannot be compared like that. Big O is about asymptotic complexity, and so O(logš¯‘›) = O(logš¯‘› / 10) = O(1000 logš¯‘›).

    You have identified another example where the two rebalancing operations are both double rotations. But the factor 2 is irrelevant for asymptotic complexity. Again, O(logš¯‘›) is O(2logš¯‘›) is O(logš¯‘› / 2).