Height of AVL tree with balance condition of 2

Question

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.

Answer 1

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.

Answer 2

We can solve this mathematically as :

Defining Worst Case

Now, in any Binary Tree, time complexity of searching is $O(h)$ where $h$ is height of the Binary Tree.
Now, for worst case, we want to find Maximum Height.

In case of simple Binary Search Tree with no Balancing Factor Condition on Nodes, this maximum height can be $n$ or $n+1$ (depending on convention whether height of single node tree will be 1 or 0) where $n$ is number of nodes.

Thus, we can say that given number of nodes, worst case is maximum height.

Interestingly, we can also say that given height of a tree, the worst case is minimum nodes. As even for such minimum number of nodes, we might have to traverse down the tree of height $h$, which we also have to do for maximum number of nodes.

Thus, the intuition should be clear that Given Height of Tree, the worst case is minimum number of nodes.

Applying this Concept on GIVEN Tree

1. Let us try to construct Given Tree of Height $H$ such that number of nodes in the tree is minimum.

Here we will exploit the fact that Binary Tree is a Recursive Data Structure (A Binary Tree can be defined in terms of Binary Tree)

2. We will use the notation $N_H$ to denote Minimum Number of Nodes in Given Tree of height $H$

3. We will create a Root Node
   

4. To Left (or Right) of Root, add a subtree of height H-1 (exploiting Recursive Property). So that number of nodes in entire tree is minimum, the number of node in Left (or Right) subtree should also be minimum. Thus $N_H$ is a function of $N_{H-1}$

5. Do we need to add anything to Right (or Left)?
   Yes! Because there is restriction of Balancing Factor on Nodes.
   We need to add subtree on Right (or Left). What should be it's height?

   $H?$

   No, then height of entire tree will become $H+1$

   $H-1?$

   Permitted! since Balancing Factor of Root will become $0$

   $H-2?$

   Permitted! since Balancing Factor of Root will be $1$

   $H-3?$

   Permitted! since Balancing Factor of Root will be $2$

   $H-4?$

   Not Permitted! since Balancing Factor of Root will become $3$

   We want minimum number of nodes, so out of H-1, H-2 and H-3, we will choose $H-3$. So that number of nodes in entire tree is minimum, the number of node in Right (or Left) subtree should also be minimum. Thus $N_{H}$ is also a function of $N_{H-3}$

6. Thus, to construct Given Tree of Height $H$ such that number of nodes in the tree is minimum, we can have LEFT subtree as Given Tree of Height $H-1$ such that number of nodes is minimum and can have RIGHT subtree as Given Tree of Height $H-3$ such that number of nodes in it is also minimum, and can add one root node. Our tree will look like
   

   Thus, we can form Recurrence Relation as

   $$N_{H} = N_{H-1} + N_{H-3}+ 1$$
   with base condition as $$N_{0} = 1$$ $$N_{1} = 2$$ $$N_{2} = 3$$

To create BST of height 0, we need to add one node. Throughout the answer we will use this convention

7. Now, this Recurrence Relation is Difficult to Solve. But courtesy to this answer, we can conclude that $$N_{H} \gt (\sqrt2)^H$$

8. Now, let $n$ be the number of nodes in the Given Tree Then, $$n \geq N_H$$ $$n \geq (\sqrt2)^H$$ $$\log_{\sqrt2} n \geq H$$
   $$H \leq \log_{\sqrt2} n$$ $$H \leq 2\log_{2} n$$

Therefore, $H=O(\log(n))$
Or $O(H) = O(\log(n))$

Thus, Worst Case Time Complexity for Searching in this Given Tree will be $O(\log(n))$

Hence, Proved Mathematically!