WBT Height

$$Height(T)\le \frac{\log (weight(T))}{\log (\frac{4}{3})}$$

Proof

1. With IH as $\forall k\in \mathbb{N},0\le k\le n,Height(T^{\prime })\le \frac{\log (k+1)}{\log (4/3)}$ where $size(T^{\prime })=k$
2. Then, $size(T)+1$
3. $=n+1$ (where $n=size(T)$)
4. $=l+r+1+1$
5. $\ge \frac{r+1}{3}+r+1$ as $l+1\ge \frac{r+1}{3}$ by WBT condition
6. $=(r+1)\ast 4/3$
7. $⟹r+1\le \frac{n+1}{4/3}$
8. WLOG, assume $Height(T.left)<Height(T.right)$
9. Thus, $height(T)=height(T.right)+1$ by defn of height
10. $l=size(T.left)$
11. $r=size(T.right)$
12. $height(T.right)+1\le \frac{\log (r+1)}{\log (4/3)}+1$
13. $\le \frac{\log \left(\frac{n+1}{4/3}\right)}{\log (4/3)}+1$
14. $=\frac{\log (n+1)}{\log (4/3)}$