0
$\begingroup$

Could somebody explain to me why the height of a weight balanced binary tree in $O(\log n)$ in the worst case?

$\endgroup$
  • $\begingroup$ It isn't, if the tree limits the out-degree of nodes to 1. Otherwise, for example in the case of AVL trees, because the number of elements is exponential in the depth, which follows from the respective proofs of that property. $\endgroup$ – G. Bach Sep 22 '13 at 18:22
  • $\begingroup$ I explain it here stackoverflow.com/a/13093274/550393 $\endgroup$ – 2cupsOfTech Apr 10 '14 at 15:48
1
$\begingroup$

What have you tried? Where did you get stuck?

In particular, you're going to want to look at a proof by induction. Does a tree with 1 node have logarithmic height? Then look at a tree with $n$ nodes. When you add another node to a balanced binary tree, which you know to have logarithmic height, what is the worst thing that can happen to the height?

$\endgroup$
0
$\begingroup$

Think of a Weight Balanced Tree (wbt) as a certain instance of a quick sort run. The invariant of the wbt indicates that the 2 halves of the sub-arrays to be sorted recursively are Theta of each other. This means that each tree of execution in quick sort will never be deeper than Theta(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.