AVL tree such that each insert causes rotation (single or double) Could you give me an example of an AVL tree for which inserting an element at an arbitrary (i.e. every) position causes a rotation (double or single)?

I have tried to come up with an example, but I didn't manage to.
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 &lt; y$, there exists $z \in V$ satisfying $x &lt; z &lt; 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 $&lt; 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 &lt; 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.