0
$\begingroup$

What size is the largest AVL tree for which an insertion could trigger a double rotation?

$\endgroup$
4
  • $\begingroup$ Can you give an example of when adding one node can cause several imbalances? Also, I'm not sure what relevance 'multiple imbalances' has to do with double rotations... $\endgroup$
    – JimN
    Nov 7, 2021 at 1:16
  • $\begingroup$ Welcome to COMPUTER SCIENCE @SE. Please clarify in your question whether eventually be unbalanced means change from balanced to heights differ by one, or change from within limits to needs fixing. $\endgroup$
    – greybeard
    Nov 7, 2021 at 6:04
  • 3
    $\begingroup$ Please don't edit your question to remove its content. When you post here, you are licensing your question to the community, for purposes of building up an archive of high-quality questions and answers (see cs.stackexchange.com/help/editing). If you no longer want an answer to your question, and it hasn't been answered yet, you can delete it using the 'delete' button under the question. $\endgroup$
    – D.W.
    Nov 8, 2021 at 0:30
  • $\begingroup$ there is no delete button $\endgroup$
    – jon pierre
    Nov 8, 2021 at 12:58

1 Answer 1

1
$\begingroup$

The insertion of a single element to an AVL-tree might cause unbalance at several nodes on the path from the root to the leaf where the new element was placed.

The tree can then be restored by a rotation at a single node on the path: the lowest node with unbalance. After that rotation the height of the subtree at that node is again the height it had before insertion, so all balance-factors above that point are again what they used to be before insertion.

The rotation that fixes the tree might be a single rotation or a double rotation depending on the position of the subtree that is deepest, as seen from the node where the rotation is performed.

In the example below we will rotate at node 4 to restore the balance caused by the insertion of node 6. (This will be a single rotation, to the left.)

single element inserted causing unbalance at most positions along the insertion path

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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