I've begun learning about AVL trees. It seems that the assertion with this data structure is that with every insertion/deletion, the only nodes whose height changes are nodes on the path towards the root (from the inserted/deleted node). How exactly is this 'proved'? I've gone through many examples and it would appear to hold true, but I haven't seen a convincing proof/explanation from any of the texts I have read.

  • $\begingroup$ Try proving it by induction (formulate an inductive predicate, then trying to prove it holds for the recursive implementation of the insert procedure). Give that a try, then if you're still stuck, edit your question to show us what you tried and where you got stuck. $\endgroup$ – D.W. Apr 23 '16 at 22:46
  • 1
    $\begingroup$ Is there really anything to prove here? If no node is added to a subtree, then its height will not change, is it? $\endgroup$ – Hendrik Jan Apr 24 '16 at 0:22
  • $\begingroup$ If in algorithm description there is stated that after insertion (after traversing down to insertion point, and inserting) you go up on the path traversed and nowhere else, is there really need to prove that it doesn't change height of nodes it didn't touched (you do not insert anything or delete anything in other subtrees)? $\endgroup$ – Evil Apr 24 '16 at 0:57

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.