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