1
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ You are not right. So let's continue insert to first your tree (in terms of natural numbers). When you insert: 5 (ok, rotation is needed), 6 (ok, rotation is needed), 7 (rotation is not needed). So you are not right. $\endgroup$ – user40545 Dec 19 '15 at 0:24
  • 1
    $\begingroup$ @user40545 This is not what you asked for. You asked about a tree "for which inserting an element at an arbitrary (i.e. every) position causes a rotation". Now you inserted many elements, not just one. If you insert one of 5,6,7,.. in the trees above you do have a rotation, no matter what you insert. After the rotation, there are no guarantees on the resulting tree, but the question did not ask for any. I'd recommend you open a new question, and be clear about wanting to insert "any sequence of elements" without rotations. $\endgroup$ – chi Dec 19 '15 at 8:01
  • $\begingroup$ Ok, I understand, but: Why you assume that we insert element $n\ge 5$ ? So you assume that element always will be inserted in the right side of tree (for each subtree). In my problem we musn't where element will be inserted. Simply, you solved much easier problem. $\endgroup$ – user40545 Dec 19 '15 at 11:56
  • 1
    $\begingroup$ @user40545 If the AVL tree is an AVL tree of natural numbers, and you already inserted $0,\ldots,4$, the next one must be $\geq 5$ -- there are no other natural numbers! If you can insert at any point, e.g. it is an AVL tree of reals / rationals / strings / ..., then we proved below that any tree has a rotation free insertion. $\endgroup$ – chi Dec 19 '15 at 12:05
  • 1
    $\begingroup$ @user40545 That's a good point! I often think about AVL trees implementing a set, hence no duplicates, but it does not have to be so. In such case, the proof above seems to apply, and you can always insert something without rotations, as far as I can see. $\endgroup$ – chi Dec 19 '15 at 12:54
1
$\begingroup$

"Every insert causes rotation" - it cannot happen.

Example: example

If you add 5, there is rotation, but if you add 0, there is no rotation. Balance in AVL tree is {-1; 0; 1} and then if it gets bigger (-2 or 2) it rotates.
This implies that only addition of node on one side will cause rotation.

If I understood your question - you wold like such instance of AVL tree that no matter what you add it will rotate (probably without duplicates) - this is not possible.

I do understand that more formal way would be preffered, and I would love to state formal inductiin for all trees, ommiting instances with less than tree nodes, but there is no instance of such tree that would work for initial inductive step.

In very standard implementation AVL does not support duplicates - for example you use it as backend to associative array, then overwriting is desired effect.
Additional field like $count$ will allow multiplicity, or list to preserve values, but still rotation will not occur, which initially was not the point.

| cite | improve this answer | | | | |
$\endgroup$
  • $\begingroup$ My comment relates to my earlier (wrong) understanding of the question; deleting. It seems you are right, too, my hint is bad. Your idea, that is; you need to give a (formal) reason for why this should be the case for every AVL tree. $\endgroup$ – Raphael Dec 18 '15 at 14:32
  • $\begingroup$ In this situation you should revoke -1 for my post. It occurs that Raphael incorrectly understand problem and he said: "It is not hard" (more humility please). Nevertheless, @EvilJS managed to understand problem. When it comes to my problem: intuitively it is clear that such tree doesn't exists. It is intresting to show it in formal way. $\endgroup$ – user40545 Dec 18 '15 at 15:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.