BST operations are , but depends on insertion order:
- Insert : balanced tree,
- Insert : right-skewed,
In the worst case, BST operations become .
No better than a linked list. Self-balancing BSTs solve this by automatically adjusting structure after insertions and deletions:
- AVL trees: strictly balanced (heights of subtrees differ by at most 1)
- Red-Black trees: relaxed balance (guarantees )
- Splay trees: move recently accessed nodes to root
Most languages use Red-Black trees for their ordered map/set implementations.