AVL Tree Which Has 11 Nodes and Answers Requirements

Question

I am trying to find an AVL tree composed of 11 nodes, such that it answers the following requirements:

1. We can remove any 2 nodes (one after the other) and the tree's height will remain unchanged.
2. We can add any 1 node and the tree's height will remain unchanged.

Note: When we delete a node and insert a node to the tree we balance it using rotations (RR, LL, RL, LR).

Find an AVL tree which answers the requirements in the question.

Answer 1

It could be this tree:

          ____6____
         /         \
        3           9
       / \         / \
      2   4       8   10
     /     \     /     \
    1       5   7       11
    

This tree's left and right sub trees have the same shape. They consist of two "legs" each, four legs in total.

Deletions

Whichever node is first deleted, it will result in one of the four legs getting shorter. This will not result in a rotation. For instance, if the root value is deleted, 7 will take its place, shortening the the 9-8-7 leg to just 9-8.

When a second node is deleted, either it shortens a different leg and no rotation is needed, or the same leg (as in the previous deletion) is shortened again: in that case a single rotation will resolve the imbalance.

Either way, there will be at least two legs of the original tree that were not shortened by the two deletions, and so the tree's height remains the same whichever two nodes are deleted.

Insertion

If the new node gets a parent that is not a leaf (i.e. its parent is either 2, 4, 8 or 10), then no rotation happens and the tree's height is not affected.

Otherwise the new node is inserted below one of the four leaves, making one "leg" longer. This will trigger a single or double rotation, which restores the original height of the tree.