# Weighted binary search tree

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.

• How is the ratio defined when a node has only one child?
– user114966
Apr 8 at 16:01
• Your binary tree is balanced. This is the meaning of the condition you are given. Apr 8 at 16:02
• @YuvalFilmus So how we can show worst case is $2\log n$? Apr 8 at 16:36
• Bound the depth of the tree, using the given condition. Apr 8 at 17:10

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