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
void add( node* &t, int x ); is correct insertion to AVL, and
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.