What is a minimum size AVL tree in which removal causes 2 turns?

Question

It is well known that deletion from the AVL tree can lead to an imbalance of several nodes. My question is, what is the AVL tree of minimum size, such that 2 rotations are required (I assume that the left-right or left-right rotation is 1 revolution)? I currently have a 12-node AVL tree where removal will result in 2 revolutions. The AVL tree is inserted in the following order:

8, 5, 9, 3, 6, 11, 2, 4, 7, 10, 12, 1.

If you remove 10, 9 becomes unbalanced and a rotation occurs. In this case, 8 becomes unbalanced and another rotation occurs. Is there a smaller tree where 2 rotations are required after removal?

After reading jpalecek's comment, my real question is: given some constant k, what is the minimum AVL tree having k rotations after 1 deletion?

Answer 1

A tree of four nodes requires one turn in the worst case. The worst case of the number of deletions increases with each term in the list: 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, ...

This is Sloane A027941 and is a Fibonacci type sequence that can be generated using N(i)=1+N(i-1)+N(i-2) for i>=2, N(1)=2, N(0)=1 .

To understand why this is so, first notice that rotating an unbalanced AVL tree reduces its height by one, because its shorter leg lengthens due to its longer leg.

When a node is removed from the AVL tree, the AVL algorithm checks all remote node ancestors for potential rebalancing. Therefore, to answer your question, we need to define trees with a minimum number of nodes for a given height.

In such a tree, each node is either a leaf or has a balance factor of +1 or -1: if a node has a balance factor of zero, this means that a node can be deleted without causing rebalancing. And we know that rebalancing makes the tree shorter.

Below I show a set of the worst trees. You can see that after the first two trees in the sequence, each tree is built by connecting the two previous trees. You can also see that each node in each tree is either a leaf or has a non-zero balance factor. Therefore, each tree has a maximum height for its number of nodes.

For each tree, deletion in the left subtree will in the worst case cause rotation, which will ultimately reduce the height of this subtree by one. This balances the tree as a whole. On the other hand, removing a node from the right subtree can ultimately lead to an imbalance in the tree, leading to rotation of the root. Therefore, the right subtrees are of great interest.

You can verify that tree (c) and tree (d) have the same rotation when removed, in the worst case.

Tree (c) appears as the right subtree in Tree (e) and Tree (d) as the right subtree in Tree (f). When the rotation starts in the tree (c) or (d), it cuts the trees, which leads to the rotation of the root in the trees (d) and (f). Obviously, the sequence continues.

If you count the number of nodes in the trees, this matches my original statement and completes the proof.

(In the tree below, deleting the selected node will result in a new maximum speed.)

Answer 2

I'm not very good with evidence, and I'm sure there are holes down there, but maybe it will cause something positive.

To perform k spins on a minimized AVL tree after removing a node, the following conditions must be met:

• The node target must exist in the 4-node subtree.
• The node target must either be on a short branch, or it must be the root of a subtree and be replaced by a leaf of a short branch.
• Each node in the pedigree of the root of the target subtree should be slightly out of balance (balance ratio +/- 1). That is, when a balance factor of 0 occurs, the rotation chain terminates.

The height and number of nodes of a collapsed tree are calculated using the following equations.

• Let H (k) = the minimum height of the tree subjected to k rotation.

   H(k) = 2k + 1, k > 0 

• Let N (h) = the number of nodes in the AVL tree of height h (min-node) of height h.

   N(0) = 0 N(1) = 1 N(h) = N(h-1) + N(h-2) + 1, h > 1 

• Let F (k) = the minimum number of nodes in the tree affected by k rotations.

   F(k) = N(H(k)) 

(eg:)

 k = 1, H(k) = 4, N(4) = 7 k = 2, H(k) = 6, N(6) = 20 

Proof (such as it is)

Minimum height

Removing can cause rotation only for trees with 4 or more nodes.

• The 1 node tree must have a balance factor of 0.
• A tree of two nodes should have a balance factor of +/- 1, and deletion leads to a balanced tree of 1 node.
• A tree of three nodes must have a balance factor of 0. Removing a node leads to a balance factor of +/- 1 and no rotation occurs.
• Therefore, removal from a tree with less than 4 knots cannot lead to rotation.

The smallest subtree for which 1 rotation occurs when deleting is 4 nodes with a height of 3. Removing the node on the short side will rotate. Similarly, removing the root of a node using node on the short side as a replacement will result in rotation. It doesn't matter how the tree is configured:

  BB Removal of A or replacement of B with A / \ / \ results in rotation. No rotation occurs ACAD on removal of C or D, or on replacement \ / of B with C. DCCC Removal of D or replacement of C with D / \ / \ results in rotation. No rotation occurs BDAD on removal of A or B, or on replacement / \ of C with B. AB 

Removing a 4 node from a tree results in a balanced tree with a height of 2.

  . / \ . . 

To perform the second rotation, the target tree must have a brother of height 4, so that the root balance coefficient is +/- 1 (and therefore has a height of 5). It does not matter whether the affected tree is located to the right or left of the parent, as well as the layout of the brother's tree (that is, the H3 child from H4 can be left or right and can be any of the 4 orientations above, while the child H2 can be one of two possible orientations - this requires confirmation).

  _._ _._ / \ / \ (H4) . . (H4) / \ / \ . . . . \ \ . . 

It is understood that the third rotation requires that the grandparents of the affected tree are also unbalanced by +/- 1, and the fourth requires that the great-grandmother be unbalanced by +/- 1, etc.

By definition, the height of a subtree is the maximum height of each branch, plus one for the root. One brother must be 1 above the other in order to achieve an imbalance of +/- 1 at the root.

 H(1) = 3 (as observed above) H(k) = 1 + max(H(k - 1), H(k - 1) + 1)) = 1 + H(k - 1) + 1 = H(k - 1) + 2 ... Inductive proof leading to H(k) = 2k + 1 eludes me. 

Minimum nodes

• By definition, the number of nodes in a subtree is the number of nodes in the left branch plus the number of nodes in the right branch plus 1 for the root.
• There should also be a definition, a tree of height 0 should have 0 nodes, and a tree of height 1 should not have branches and, therefore, 1 node.
• It was shown above that one branch should be one short than the other.

• Let N (h) = the minimum number of nodes needed to create a tree of height h:

   N(0) = 0 N(1) = 1 // the number of nodes in the two subtrees plus the root N(h) = N(h-1) + N(h-2) + 1 

Consequence

• The minimum number of nodes is not necessarily the maximum in large trees. To wit:

Remove A from the next tree and note that the height does not change after rotation. Therefore, the balance ratio in the parent would not change and no additional rotation would occur.

  BBD / \ \ / \ AD => D => BE / \ / \ \ CECEC 

However, in the case k = 2, it does not matter if H (4) is minimized here - the second rotation will still take place.

  _._ _._ / \ / \ (H4) . . (H4) / \ / \ . . . . \ \ . . 

Questions

• What is the position of the target subtree? It is clear that for k = 1 it is the root, and for k = 2 it is the left if the root balance coefficient is -1 otherwise it is right. Is there a formula for determining the position for k> = 3?
• What are the maximum nodes a tree can contain to cause k rotations? Is it possible to have an intermediate node in a pedigree that does not rotate, although its parent?