1
$\begingroup$

The maximum height of an AVL tree with a balance condition of 1 is 1.44log(n). So the worst case height is O(logn). However, if the balance condition was hypothetically 2 (meaning that the allowed imbalance condition between two child nodes would be 2), how could I find the maximum height of such a tree. Would I need to solve some kind of recurrence relation or fibonacci sequence. Is there an easier way of figuring out the maximum height of a tree with a balance condition of 2 by using what we already know? Thanks.

$\endgroup$
0
$\begingroup$

Let $T_h$ denote the minimal number of nodes that a standard AVL tree of height $h$ could have.

If $h>0$, then there's the root and two subtrees. One of the subtrees must have height $h-1$. The other must have height at least $h-2$, otherwise it's not a valid AVL tree. So we have the recurrence:

$$T_h = T_{h-1} + T_{h-2} + 1$$

And we can throw in $T_0 = 0$ and $T_1 = 1$ for obvious reasons.

The easy way to solve the recurrence is to denote $F_h = T_h + 1$. Then:

$$\begin{align*}F_0 & = 1 \\ F_1 & = 2 \\ F_h & = F_{h-1} + F_{h-2}\end{align*}$$

That is, they're Fibonacci numbers with the sequence offset by 3.

Since:

$$F_h \approx \frac{1}{\sqrt{5}} \left( \frac{1 + \sqrt{5}}{2} \right)^{h+3}$$

Inverting this, we get:

$$h \approx \frac{1}{\log \left( \frac{1 + \sqrt{5}}{2} \right)} \log \left( T_h \right) + 3$$

And that is where the 1.44 comes from.

So what you need is to solve the recurrence:

$$U_h = U_{h-1} + U_{h-3} + 1$$

with suitable initial conditions.

If you can't think of a clever way to do this, you can do it the not-clever-but-always-works way by observing that:

$$\begin{bmatrix} U_h \\ U_{h-1} \\ U_{h-2} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix} \begin{bmatrix} U_{h-1} \\ U_{h-2} \\ U_{h-3} \\ 1\end{bmatrix}$$

Therefore:

$$\begin{bmatrix} U_{h+2} \\ U_{h+1} \\ U_{h} \\ 1\end{bmatrix} = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}^{h} \begin{bmatrix} U_{2} \\ U_{1} \\ U_{0} \\ 1\end{bmatrix}$$

Next, perform eigendecomposition on the matrix. Let:

$$M = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1\end{bmatrix}$$

Suppose you can find a matrix $Q$ and a diagonal matrix $\Lambda$ such that $M = Q \Lambda Q^{-1}$. Then:

$$M^h = Q \Lambda^h Q^{-1}$$

Taking the power of a diagonal matrix is trivial, and this should give you a closed form. You will then need to find an approximate inverse to solve your problem.

$\endgroup$

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.