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.

| cite | improve this answer | |
  • $\begingroup$ ie. at some stage the root would have to be rotated into the left sub-tree? $\endgroup$ – rtheunissen May 1 '19 at 19:32
  • $\begingroup$ Do red-black trees rebalance in amortized constant time? cs.stackexchange.com/a/52664/45572 $\endgroup$ – rtheunissen May 1 '19 at 19:41
  • $\begingroup$ @rtheunissen My point was not about the root, but that if you insert enough elements, a significant portion of those will have to end up in the left sub-tree, for balance. Assuming each atom operation in the rebalancing is local (e.g. the depth of each node does not change by more than 1) that wouldn't be possible with constant rebalancing time. $\endgroup$ – Ariel May 2 '19 at 9:59
  • $\begingroup$ @rtheunissen If you consider a set of operations starting from an empty tree, and the insertion location is known (e.g. min/max) then yeah, the ammortized cost is constant. $\endgroup$ – Ariel May 2 '19 at 10:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.