What is the minimum sized AVL tree where a deletion causes 2 rotations?

6
votes

It is well known that deletion from an AVL tree may cause several nodes to eventually be unbalanced. My question is, what is the minimum sized AVL tree such that 2 rotations are required (I'm assuming a left-right or right-left rotation is 1 rotation)? I currently have an AVL tree with 12 nodes where deletion would cause 2 rotations. My AVL tree is inserting in this order:

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

If you delete the 10, 9 becomes unbalanced and a rotation occurs. In doing so, 8 becomes unbalanced and another rotation occurs. Is there a smaller tree where 2 rotations are necessary after a deletion?

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

2
algorithmavl-tree
Not that it isn't an interesting question - but if you know there's a tree 12 with some property and you want to find the smallest one, can't you just look for the answer yourself? Ie. generate all possible trees of size <=11 and check them? – jpalecek
I've done a bit of searching online and can't come across a site that addresses this exact problem. I think I can prove that the smallest AVL tree with height 3 has 7 nodes and I want to roll that proof into saying the left subtree of some node must have height of 3 if the right subtree has a height of 1 (after rotating). Anyway, a lot of ideas in my head but none of them seem to be valid proofs. – Greg C
I could certainly create all AVL trees of size 11 and calculate this. I guess my real question is more general than this one. What is the minimum sized AVL tree that causes k rotations? Is there some formula to come up with the minimum size of the AVL tree? It seems like there should be one. – Greg C
I believe 7 nodes (before deletion) are enough, consider this insertion order: 5 6 2 7 1 3 4, and delete 7. – n. 1.8e9-where's-my-share m.
@n.m. Your tree only has 1 rotation after deletion. The 5 is the only unbalanced node and therefore a left-right rotation is required. I consider a left-right rotation to be 1 rotation. Unless you were referencing my claim about an AVL tree with height 3 having 7 nodes at minimum. In that case, yes, I agree that 7 is possible and am fairly certain it's minimum. – Greg C

2 Answers

5
votes

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

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

To see why this is so, first note that rotating an imbalanced AVL tree reduces its height by one because its shorter leg is lengthened at the expense of its longer leg.

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

In such a tree every node is either a leaf or has a balance factor of +1 or -1: if a node had a balance factor of zero this would mean that a node could be removed without triggering a rebalancing. And we know rebalancing makes a tree shorter.

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

For each tree, a removal in the left subtree will, in the worst case, cause rotations which ultimately reduce the height of that subtree by one. This balances the tree as a whole. On the other hand, removing a node from the right subtree may ultimately imbalance the tree resulting in a rotation of the root. Therefore, the right subtrees are of prime interest.

You can verify that Tree (c) and Tree (d) have one rotation upon removal, in the worst case.

Tree (c) appears as a right subtree in Tree (e) and Tree (d) as a right subtree in Tree (f). When a rotation is triggered in Tree (c) or (d) this shortens the trees resulting in a root rotation in Trees (d) and (f). Clearly, the sequence continues.

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

(In the trees below removing the highlighted node will result in a new maximum number of rotations.)

Worst-case AVL trees

1
votes

I am not good at proofs, and I'm sure the below is full of holes, but maybe it will spark something positive.

To effect k rotations on a minimized AVL tree following the deletion of a node, the following conditions must be met:

  • The target node must exist in a 4-node sub-tree.
  • The target node must either be on the short branch, or must be the root of the sub-tree and be replaced by the leaf of the short branch.
  • Each node in the ancestry of the root of the target sub-tree must be slightly out of balance (balance factor of +/-1). That is - when a balance factor of 0 is encountered, the rotation chain will cease.

The height and number of nodes of the minimized tree is calculated with the following equations.

  • Let H(k) = the minimum height of the tree affected by k rotations.

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

  • Let N(h) = the number of nodes in a (min-node) AVL tree 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))

(e.g:)

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

Proof (such as it is)

A deletion can only cause a rotation for trees with 4 or more nodes.

  • A tree of 1 node must have a balance factor of 0.
  • A tree of 2 nodes must have a balance factor of +/-1, and deletion leads to a balanced tree of 1 node.
  • A tree of 3 nodes must have a balance factor of 0. Removal of a node results in a balance factor of +/-1 and no rotation occurs.
  • Therefore, deletion from a tree with fewer than 4 nodes can not result in a rotation.

The smallest sub-tree for which 1 rotation occurs on delete is 4 nodes, which has height of 3. Removal of the node in the short side will result in rotation. Likewise, removal of the root node, using the node on the short side as replacement will cause a rotation. It doesn't matter how the tree is configured:

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

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

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

  .
 / \
.   .

To effect a second rotation, the target tree must have a sibling of height 4, so that the balance factor of the root is +/-1 (and therefore has a height of 5). It doesn't matter if the affected tree is on the right or left of the parent, nor is the layout of the sibling tree important (that is, the H3 child of H4 can be on the left or right, and can be any of the 4 orientations above while the H2 child can be either of the 2 possible orientations - this needs proving).

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

It is clear that the third rotation requires that the grandparent of the affected tree be likewise imbalanced by +/-1, and the fourth requires the great-grandparent be imbalanced by +/-1, and so on.

By definition, the height of a sub-tree is the maximum height of each branch plus one for the root. One sibling must be 1 taller than the other to achieve the +/-1 imbalance in 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.
  • By definition, the number of nodes in a sub-tree is the number of nodes in the left branch plus the number of nodes in the right branch plus 1 for the root.
  • Also be definition, a tree of height 0 must have 0 nodes, and a tree of height 1 must have no branches and thus 1 node.
  • It was shown above that the one branch must be one shorter than the other.

  • Let N(h) = minimum number of nodes required 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

Corollary

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

Delete A from the following tree and observe that the height doesn't change following rotation. Therefore, the balance factor in the parent would not change and no additional rotation would occur.

  B          B           D
 / \          \         / \
A   D    =>    D   =>  B   E  
   / \        / \       \    
  C   E      C   E       C

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

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

Questions

  • What is the position of the target sub-tree? Clearly for k = 1, it is the root, and for k = 2, it is the left if the root's balance factor is -1 otherwise the right. Is there a formula for determining position for k >= 3?
  • What is the maximum nodes a tree can contain to effect k rotations? Is it possible to have an intermediate node in the ancestry that is not rotated, though its parent is?