AVL trees python question

[zarrexx]

Got this question on a previous exam in programming algorithms, could someone help me out how to answer this. thanks

 

When restructuring an AVL tree after a node has been added, only one restructuring is required per added node. Why?

[fjdhdhcyfhf]

Because it always gets restructured when height difference if greater than one

[Yamoto42]

By definition, the heights of the two branches of any SUBtree can differ in height by more than one.  That is the key, and why it can be balanced with only a single restructuring.  Trees are naturally recursive structures.  We can categorize root, interior, and leaf nodes, but interior nodes are all roots as well.  This recursive nature propagates upwards as well, meaning while the error effects the tree as a whole, it is only sourced at a single node.  Fixing the (sub)tree rooted at that imbalanced node fixes the source of the error, and thereby the entire tree.

[zarrexx]

Thanks guys