• best case (for at-leaf insertion): keys inserted in pre-order
  (median key first, then median of lower half, median of upper half, etc.)
• worst case: keys inserted in ascending/descending order
• average case: keys inserted in random order  ⇒ O(log₂ n)

Can the algorithm itself introduce some randomness?

In the hope that this randomness helps to balance the tree …