1/2 < c < 1 b = -1/logc d(x) = depth of x 1. We have d(x) > b*log(n) = -log(n) / log(c) Let's assume that there is no u and v, v being the parent, such that w(u) > c*w(v). Then all nodes along the path are such that w(u) <= c*w(v). Then w(u) < w(v)/2. As a result, x < root / (2^d(x)). 2^d(x) < root/x d(x) < log(root) - log(x) d(x) < log(n) - log(x) (0) In turn, c > 1/2 log(c) > -1 1/log(c) < -1 b > 1 b*log(n) > log(n) (1) We know that log(n) >= log(n) - log(x) Thus, using (0) and (1) b*log(n) > d(x) 2. By induction, we'll prove for all n>1, that the height of a tree of size n bounded by $b*\log(n)$ is bounded by $b*\log(n+1)$ after inserting an element. If n = 1, when inserting, the height of the tree is 1. $b*\log(2) > 1 = height$. Now, assume an n such that $\forall k < n$, the height of the tree is bounded by $b*\log(k)$ upon insertion. When inserting, there are two possibilities. Case 1: the height of the tree didn't change. The height of the new tree is bounded by $b*\log(n) < b*\log(n+1)$. Case 2: the height of the tree changed. Then it increased by 1, and $d(x) = h$, with $h$ being the new height of the tree. Subcase 1: we are on a path where $d(x) \le b*\log(n+1)$. d(x) = height of the tree, so it is bounded by $b*\log(n+1)$. Subcase 2: we are on a path where $d(x) > b*\log(n+1)$. We find the first node such that the weight of the subtree containing x is more than double that of its other subtree, and we balance it. Since there is only one node, x, that has a depth equal to the height of the tree, it is certain to get moved, so that the height of the whole tree is the same before insertion and after the balancing operation. As a result, h is (as it was before) bounded by $b*\log(n) < b*\log(n+1)$. We have proved the induction hypothesis in all cases. As a result, we have proved that for all $n>1$, the height of a tree of size n bounded $b*\log(n)$ is bounded $b*\log(n+1)$ after inserting an element. Since the tree is always constructed by inserting elements, the height of the tree is always bounded by $b*\log(n)$, with $n$ the number of elements in the tree. 3. find: O(log(n)) add: O(n) 4.