nodesavl-treetree-balancing

balance AVL tree before or after node deletion?


This exercise asks the student to delete a node from an AVL tree. In this case, this requires some balancing, since the difference between deepest and shallowest depth is > 1. But should the balancing occur before or after the deletion? Or does it not matter?

image of AVL tree in question


Solution

  • Essentially you want to delete as you would from a BST. Then calculate your depth factor (how long each path of the tree is) and do rotations as you normally would with inserts depending on which paths are unbalanced. So to answer your question you do the rotations after you delete.