2
$\begingroup$

Prove or disprove for each of the following two properties, whether a family of trees that satisfy the property is balanced.

If you disprove, the counterexample should consist of an infinite sequence of trees in the family rather than just a single tree, because the property is asymptotic.

A. There is a constant $c$ so that for each node of the tree, the difference in height between the two sub-trees is at most $c$.

B. There is constant $c$ so that the average height of each node in the tree is at most $c \log n$.

Now I proved A using induction, and I know how to disprove B using a single example, but I don't know how to do so using infinitely many examples.

$\endgroup$
11
  • 1
    $\begingroup$ What do you mean by "example"? Does it rule out all values of $c$? $\endgroup$ Commented Jun 10, 2019 at 17:51
  • $\begingroup$ counter example in order to disprove B @YuvalFilmus $\endgroup$
    – Gil
    Commented Jun 10, 2019 at 17:53
  • $\begingroup$ Does it rule out all values of $c$? Perhaps you can add it to your question. $\endgroup$ Commented Jun 10, 2019 at 17:53
  • $\begingroup$ yes it does, in the instructions they say if its disproving then it should be infinite series of trees $\endgroup$
    – Gil
    Commented Jun 10, 2019 at 17:54
  • $\begingroup$ I doubt that a single example can disprove the claim for all values of $c$, and this is why I would appreciate seeing it. Otherwise I'm afraid I won't be able to help you. $\endgroup$ Commented Jun 10, 2019 at 17:58

1 Answer 1

2
$\begingroup$

This is an interesting question. How do we define a family of binary trees is balanced?

A generalized definition of balanced binary trees

One of the most general definitions is that the height of a tree $T$ in the family is $O(\log n)$, where $n$ is the number of nodes in $T$. In other words, there is a constant $c$ such that the height of each tree $T$ in the family is no more than $c\log n$. We call such a family of binary trees balanced. Each tree in the family is called balanced (with respect to the family).

For example, the family of AVL trees is balanced. The family of red-black tree is balanced. For any given $0\lt \alpha\lt1$, $\alpha$-weight-balanced trees are balanced. A family of finitely many trees is balanced.

The family of all degenerated trees is not balanced.

$c$-height-balanced trees are balanced

Let $c$ be a constant. Let $T$ be a binary tree such that for each node of it, the difference in height between the two sub-trees is at most $c$. We call $T$ $c$-height-balanced. The family of $c$-height-balanced trees is balanced, which you have probably proved.

$O(\log n)$-average-height trees may not be balanced.

Let us call a family of trees that satisfies the condition (B) $O(\log n)$-average-height family of trees. Here is an example of an $O(\log n)$-average-height family of trees that is not balanced.

Let us start from a perfect binary tree with node $1,2, \cdots, 2^m-1$, where the children of node $i$ are node $2i$ and $2i+1$. Add node $2^m, 2^m+1, \cdots, 2^m+m^2-m$ to the tree so that the right child of node $j$ is node $j+1$ for all $j\ge 2^m-1$. Denote the tree thus obtained by $T_m$. The number of nodes in $T_m$ is $n=2^m+m^2-m$.

The rightmost nodes of $T_m$, $$2^1-1, 2^2-1, \cdots, 2^m-1, 2^m, 2^m+1, \cdots, 2^m+m^2-m$$ form a linear tree with $m+ m^2-m = m^2$ nodes.

The sum of heights of all nodes is

$$\begin{aligned} \sum_{1\le i\le 2^m+m^2-m} h(i) &= \sum_{1\le j\le m-1}\sum_{2^j\le i\le 2^{j+1}-2} h(i) + \sum_{0\le j\le m-1}h(2^{j+1}-1)+ \sum_{2^m\le i\le 2^m+m^2-m} h(i) \\ &= \sum_{1\le j\le m-1}(2^j-1)(m-1-j) + \sum_{1\le k\le m^2}(k-1) \\ &\lt m\sum_{1\le j\le m-1}(2^j-1) + \sum_{1\le k\le m^2}m^2\\ &\lt m2^m + (m^2)^2\\ &\lt 10m2^m\\ &\le 10mn.\\ \end{aligned}$$

So the average height of each node is not greater than $10m \le 10\log_2 n.$

However, the height of node $2^m+m^2-m$ is $m^2-1=\Theta((\log n)^2)$. So the $O(\log n)$-average-height family of trees $T_1, T_2, \cdots$ is not balanced.

Exercises

Exercises 1. Show that the height of a tree $T$ in a given balanced family of binary trees is, in fact, $\Theta(\log n)$.

Exercises 2. Construct an $O(\log n)$-average-height family of trees such that the height of a tree $T$ is $\Omega(\sqrt {n})$.

Exercises 3. Let $F$ be a family of binary trees such that the ratio between the heights of two subtrees with the same parent node is bounded for all parent nodes of all trees. In other words, there is a constant $c$ such that for every $T$ in $F$, for every node $v$ of $T$, the ratio between the heights of two subtrees of $v$ is at most $c$. In order to avoid dividing by zero, if any subtree of $v$ is empty, the height of that empty subtree is redefined as 1/2. We call $F$ height-ratio-bounded. Is a height-ratio-bounded family balanced?

$\endgroup$
3
  • $\begingroup$ yes, by the definition of binary tree - which must be balanced. $\endgroup$
    – Gil
    Commented Jun 11, 2019 at 6:51
  • $\begingroup$ also where that 10m came from? $\endgroup$
    – Gil
    Commented Jun 11, 2019 at 8:07
  • 1
    $\begingroup$ A series of wrong editing, now corrected. $\endgroup$
    – John L.
    Commented Jun 11, 2019 at 12:15

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.