AVL Trees
Key Invariant
Balance factor (bf) = height(left) - height(right). Every node must have |bf| <= 1. Height is always <= 1.44 * log2(n), guaranteeing O(log n) operations.
Complexity
| Operation | Time | Space | |-----------|------|-------| | Search / Insert / Delete | O(log n) | O(log n) stack | | Single rotation | O(1) | O(1) | | Get height / balance | O(1) | O(1) |
Rotation Decision Table
| Node bf | Child bf | Case | Fix | |---------|----------|------|-----| | +2 | >= 0
[Description truncada. Veja o README completo no GitHub.]