# Which binary search trees have constant time rebalancing time at min/max?

Given that I'm already at either the min or the max node of a binary search tree, which balanced variant would require only constant time bottom-up rebalancing after an update (add new min/max, or remove current)?

Consider a constant set of $$k$$ insertions done directly at the max node, and the left and right sub-trees of the root node ($$L$$, $$R$$). If each rebalancing operation required only constant time, then only $$O(\frac{log(n)}{k})$$ of the inserted elements could be in $$L$$, since the maximal element is a leaf and the tree is balanced.
While this simple analysis is incorrect for non-constant $$k$$, the intuition still holds - if rebalancing after max (/min) insertion was always constant, repeated max (/min) insertions would cause $$R$$ (/$$L$$) to grow larger, and the tree could not be balanced.