3
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ That reminds me of Scapegoat trees that are $\alpha$-height balanced: $\mbox{height}(T)\leq (\log\mbox{size}(T))/(\log (1/\alpha))+1$ where you can choose any $0.5<\alpha<1$. The higher $\alpha$ the less balances, so inserting is faster and lookup slower. $\endgroup$
    – Petr
    Commented May 6, 2013 at 17:38

1 Answer 1

Reset to default
2
$\begingroup$

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:

  1. All branches of height $h$: $n=2^h$
  2. 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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks ,but when you say "All the branches" which branches are you talking about? Are those the root's branches? And why is the conclusion "One branch of height $h$ the others of height $h−s$" $\Rightarrow$ $n=2^{h-s}+s$ is true? Lastly and unfortunately I did not understand how does this answer the second part, sorry but could you elaborate? $\endgroup$
    – Scis
    Commented May 6, 2013 at 16:47
  • $\begingroup$ All branches = all root's branches. If all the branches have size $h-s$ then you have $2^{h-s}$ nodes and to get a branch of size $h$ you have to add $s$ node to one branch, hence a total of $2^{h-s}+s$ nodes. And lastly: sorry it doesn't answer your question :S I don't really know but I don't see why it would not work ... $\endgroup$
    – wece
    Commented May 6, 2013 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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