[prev] 26 [next]

Randomized BST Insertion

Effects of order of insertion on BST shape:
  • best case: keys inserted in pre-order
    (median key first, 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(log2N)
BST ADT typically has no control over order keys supplied.

Can the algorithm itself introduce some randomness?

Exercise: check the best/worst/average cases in TreeLab