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.
3
-
$\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, 2016 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 JanApr 24, 2016 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$– EvilApr 24, 2016 at 0:57
Add a comment
|