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
|