Binary Search Trees (BST)
Invariant: left subtree < node < right subtree (no duplicates).
Complexity
| Operation | Average | Worst (degenerate) |
|---|---|---|
| Search / Insert / Delete | O(log n) | O(n) |
| Min / Max | O(log n) | O(n) |
| Successor / Predecessor | O(log n) | O(n) |
| Inorder traversal | O(n) | O(n) |
Worst case occurs on sorted input — use AVL or Red-Black tree to guarantee O(log n).
Implementation
from collections impo
[Description truncada. Veja o README completo no GitHub.]