Changing AVL's balance factor to some other $s>2 \in \mathbb{N}$

Given we change the rule to:


$-s \ \ \leq$ height(left-subtree) - height(right-subtree) $\leq \ \ s$

I was wandering whether it's possible and how would it affect the trees' height, would it still be logarithmic?

Would the exact same balancing techniques work? (if we took those methods from a normal AVL and try to convert our modified AVL to a normal AVL running from down to top or to down).

I've tired drawing some schematics in order to find out what would be the minimal number of nodes $m$ for some tree $T$ with height $h$ like we did with a regular AVL but I had a real hard time formalizing it.

If the maximal branch is of height $h$ then you know that all the other branches have at least height $h-s$.

Lets consider $n$ the number of nodes in the two extreme case:

• All branches of height $h$: $n=2^h$

• One branch of height $h$ the others of height $h-s$: then $n=2^{h-s}+s$

Hence $ 2^{h-s}+s=\frac{2^h}{2^s}\leq n\leq 2^h$ since $s$ is a constant the height is still logarithmic in the number of nodes.

I think this answer your other questions too.

StackExchange Computer Science Q#11832, answer score: 2