Hello!

I'm sure, you heard about AVL trees.

Let consider node v of the tree. Let denote "big rotation" our behavior in case v.l.h ≥ v.r.h + 2 and v.l.r.h = v.l.l.h + 1. And denote "small rotation" our behavior in case v.l.h ≥ v.r.h + 2 and v.l.r.h = v.l.l.h - 1. Of course, big rotation is just two small rotations.

Let consider almost-AVL-tree, which in both cases does small rotation.

My question: is there any test-data, that almost-AVL-tree has height at least "height of correct-AVL-tree plus 3"? Or almost-AVL-tree always works correctly and never has height more than ? =)

Here you may find code in C++, where
function void add( node* &t, int x ); is correct insertion to AVL, and
function void add_slow( node* &t, int x ); does small rotation in both cases.

P.S. Neither by hands, nor using programming, I can obtain difference of heights more than two.

UPD: Somebody had troubles with downloading/reading the code, so not pastebin, short version