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