[Solved]: AVL tree such that each insert causes rotation (single or double)

Short answer: it depends.

The answer depends on what is the set of the possible elements of the AVL tree.

Natural numbers, no duplicates allowed.

Yes, there is an AVL tree requiring a rotation on the next insertion, whatever that is:

      1      /      0   3        /        2   4 

The next insertion has to be a natural $geq 5$ and cause a rotation. Similarly,

      0                 1 

will rotate as soon as any natural (which has to be $geq 2$) is inserted.

Integer numbers, no duplicates allowed.

Yes, there is an AVL tree requiring a rotation on the next insertion:

      0      /     -1   1    /       -2       2 

The next insertion has to be $leq -3$ or $geq 3$.

Rational numbers, real numbers, strings.

No, there is no AVL tree requiring a rotation on the next insertion. We now prove this claim. These sets satisfy the following property, which we now assume. Assumption. Let $V$ be the set of the possible elements of the AVL tree. Given any two $x,y in V$, with $x < y$, there exists $z in V$ satisfying $x < z < y$. Proposition. For every $n$, any AVL tree having height $n$ admits at least one insertion requiring no rotations (a simple insertion). Proof. We proceed by induction on $n$. For $n leq 1$, it is trivial. By the induction hypothesis, assume every AVL tree with height $< n$ admits a simple insertion. Take $T$ to be any tree with height $n$, and name $S,U$ its immediate subtrees. W.l.o.g., assume $height(S) leq height(U) = n – 1 < n$ (otherwise, swap $S,U$). Hence, $S$ admits a simple insertion $p$. Modify $p$ so to ensure that, once inserted into $T$, it is inserted into the $S$ side. This is trivial if $p$ falls “inside” the elements of $S$. If instead it is the new minimum/maximum of $S$, make sure it is larger/smaller than the root of $T$, exploiting our assumption above. Hence, performing an insertion of $p$ into $T$ can not cause any rotation inside the $S$ subtree. Further, it can not cause a rotation around the root of $T$, since this insertion can increase $height(S)$ at most by one, so the AVL invariant $|height(S) – height(T)|leq 1$ still holds. Hence, there is a simple insertion in $T$. QED.

Duplicates allowed.

The above proof also holds when duplicates are allowed. In that case, one can insert a duplicate of the root of $T$ in either side.