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

Problem Detail: 

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.

Asked By : user40545

Answered By : chi

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/50882

3.2K people like this

 Download Related Notes/Documents