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.]