Alpha And The Rebuild

A scapegoat tree rebuilds the subtree at $x$ whenever $\max(|T_{left}|, |T_{right}|) > \alpha \cdot |T_x|$ , with $\alpha$ around $0.7$ . Rebuilding costs $\Theta(|T_x|)$ . How is insert still $O(\log n)$ ?

A node can only become a scapegoat after $\Omega(|T_x|)$ insertions have pushed it out of balance, and each insertion deposits $O(1)$ credit along its search path. Insert is $O(1)$ amortized.

A node can only become a scapegoat after $\Omega(|T_x|)$ insertions have pushed it out of balance, and each insertion deposits $O(\log n)$ credit along its search path. Insert is $O(\log n)$ amortized.

A node can become a scapegoat after $O(\log |T_x|)$ insertions have pushed it out of balance, and each insertion deposits $O(\log n)$ credit along its search path. Insert is $O(\log n)$ amortized.

A node can only become a scapegoat after $\Omega(|T_x|)$ insertions have pushed it out of balance, and each rebuild is spread over the next $|T_x|$ operations. Insert is $O(\log n)$ worst case.