1
$\begingroup$

After performing operations (e.g. insertion/deletion of a node - rotations) on an AVL tree, is the result fully determined by the order of insertion on the initial tree, or do multiple solutions exists that satisfy all AVL properties?

$\endgroup$
  • $\begingroup$ When you say "operation", do you include only the type of operation (e.g., insert vs delete), or also the specific value that was inserted/deleted? $\endgroup$ – D.W. Jul 11 '16 at 6:28
1
$\begingroup$

In standard way the order of operations determines the tree shape - there are no ambiguous choices during insertion / deletion or rebalancing so it is unique.

There are more possible trees if you consider some additional operations that do not violate AVL properties like introducing stricter balance or rotating -1 to +1, please remember that this operations are non-standard and changing -1 to +1 serves only one purpose - to show different existing trees with AVL properties.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.