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.