The tree height can also increase during rebalance, not just shrink.
This can happen if update_key needs to split a parent branch page.