Best-case behavior is “balanced”: \(\Theta(\log n)\) (like a
BST).
Worst-case behavior: All nodes at the same level (regardless of
what level): Effectively degenerates to a linked list (like a
BST).
Reality: Its behavior is not so dependent on order of inserts as
a BST. Its similar to what BST cost would be if we randomized the
input order. A huge improvement in expected performance!
Programming Principles
All container classes should be general.
Any container class’s initial state should be identical to its
empty state.
