0
$\begingroup$

If you were to define an altered AVL tree where the balance factor (the difference between the height of the left and right subtree) of a node must be less than or equal to the depth of the node (in absolute value), would it be balanced (h is in O(log n))? How would you prove so?

$\endgroup$

2 Answers 2

0
$\begingroup$

This is not a complete answer, but some ideas about it.

For convenience purposes, I will use the convention I talked about in the comments:

  • the depth of a node $x$ is the number of nodes between the root of the tree and the node $x$. That means that the depth of the root is $1$ (and not $0$);
  • the height of a tree is the maximal depth of one of its nodes.

For $h$ a positive integer, and $k$ a non-negative integer, denote $T_{h,k}$ the set of binary trees $t$ such that for each internal node $N(l, r)$ of depth $p$, the balance factor is less than $p + k$, meaning: $$|h(l) - h(r)|\leqslant p + k$$

Denote $n_{h, k}$ the minimal size of a tree of $T_{h,k}$. It is somewhat clear that $n_{h,k}$ is an increasing function in $h$ (if the height increases, so does the minimal size) and decreasing in $k$ (if we allow bigger balance factors, the tree is more unbalanced, and thus contains less nodes).

If $h \leqslant k + 1$, that means that there is no restriction on balance, and if that's the case, then $n_{h,k} = h$.

In the general case, if $t\in T_{h,k}$, then one of its children is in $T_{h-1, k + 1}$ (the height decreases by one, and the balance factor increases by one, because the depth of all nodes in the child is increased by one in $t$). To minimize $n_{h,k}$, the other child must be chosen of the minimal possible height, which is $h - 2 - k$. We get:

$$n_{h,k} = 1 + n_{h - 1, k + 1} + n_{h - 2 - k, k + 1}$$

What you would like to know is if $n_{h, 0}$ is exponential in $h$. Now I don't know how to solve this induction, but I made some tests in Python, because those values can be easily computed using dynamic programming.

The following curves show the values of $n_{h,0}$ and $\log n_{h,0}$ respectivelly. The first curve gives the impression that the growth is indeed exponential, however the second curve has a slower growth than a linear function, so that may not be the case. Still, any tree of size $\leqslant 3\times 10^{23}$ will have a height smaller than $1000$, so that could be considered balanced.

enter image description here

$\endgroup$
0
$\begingroup$

Trees you are asking for do not exist in general. Consider a tree with two nodes. Regardless of how you arrange them, one must be the root. Then absolute value of the balance factor of the root is $1$ but the root's depth is $0$.

$\endgroup$
5
  • $\begingroup$ Some conventions define the depth of the root as $1$, not $0$. Maybe OP is considering an implementation with this offset? $\endgroup$
    – Nathaniel
    Commented Jul 7, 2023 at 13:32
  • $\begingroup$ This type of modified AVL tree doesn't exist for 2 nodes. Is that a problem? $\endgroup$
    – Remeraze
    Commented Jul 7, 2023 at 14:20
  • $\begingroup$ This property makes no sense. The left and right subtrees of a node must have a $\endgroup$
    – user16034
    Commented Jul 7, 2023 at 15:04
  • $\begingroup$ @Remeraze, unless you consider the definition I am talking about, this type of tree doesn't exist for any even number of nodes. This is not necessarily a problem to prove some properties, but it would be annoying to use as a BST. $\endgroup$
    – Nathaniel
    Commented Jul 7, 2023 at 15:19
  • $\begingroup$ Oh, I don't intend to use this for any practical application. This is just a thought experiment. $\endgroup$
    – Remeraze
    Commented Jul 7, 2023 at 15:31

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.