2
$\begingroup$

Suppose we have binary search tree with $n$ nodes. For each node $u$ we define weight of $u$ is number of nodes in sub tree of $u$ with $u$. if ratio of weight of each internal node $u$ of right sub tree and left sub tree be at least $0.5$ and at most 2, then what is worst case of searching for a element in such binary search tree?

The answer is $2\log n$.

How it be $2\log n$? I think this tree is weighted binary search tree not AVL tree. But in proving worst case that mentioned get stuck. Any hint be appreciated.

My attempt:

I try to use formula that we use for minimum number of nodes we need to construct a AVL tree, Prove that AVL tree has this kind of property with Fibonacci sequence, but i can't draw any relation between my problem and AVL tree.

$\endgroup$
9
  • $\begingroup$ How is the ratio defined when a node has only one child? $\endgroup$
    – user114966
    Apr 8 at 16:01
  • $\begingroup$ Your binary tree is balanced. This is the meaning of the condition you are given. $\endgroup$ Apr 8 at 16:02
  • $\begingroup$ @Dmitry I don't know about this case, we can ignore it. $\endgroup$ Apr 8 at 16:35
  • $\begingroup$ @YuvalFilmus So how we can show worst case is $2\log n$? $\endgroup$ Apr 8 at 16:36
  • $\begingroup$ Bound the depth of the tree, using the given condition. $\endgroup$ Apr 8 at 17:10
3
$\begingroup$

Show by induction on the height $h$ of the tree that a tree of height $h$ has at least $2^{\frac{h}{2}}$ nodes.

The base case $h=0$ is easy since a tree of height $0$ has $1$ vertex and $1 \ge 2^\frac{0}{2}$.

Suppose that the claim holds up to some $h \ge 0$. Consider a tree $T$ with height $h+1$ rooted in $r$. Let $u$ and $v$ be the children of $r$. Let $n(x)$ and $h(x)$ denote the number of nodes and the height of the subtree of $T$ rooted at $x$, respectvely.

We must have $h(r) = 1 +\max\{h(u), h(v)\}$. Suppose w.l.o.g. that $h(r)=1+h(u)$. Then, regardless of whether $u$ is the left or right child of $r$, we have $\frac{n(v)}{n(u)} \ge \frac{1}{2}$, i.e., $n(v) \ge \frac{n(u)}{2}$.

$$ \begin{align*} n(r) &= 1 + n(u) + n(v) > n(u) + \frac{n(u)}{2} = \frac{3}{2} \cdot n(u) \\ &\ge \frac{3}{2} \cdot 2^{\frac{h(u)}{2}} = \frac{3}{2} \cdot 2^{\frac{h(r)-1}{2}} = \frac{3}{2} \cdot 2^{\frac{h}{2}} > 2^{\frac{1}{2}} \cdot 2^{\frac{h}{2}} = 2^{\frac{h+1}{2}}. \end{align*} $$

This concludes the proofs, and shows that a tree with $n$ nodes has height at most $2 \log n$.

$\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.