Uma BST simples pode degenerar para uma lista ligada (operações O(n)) se as chaves chegarem em ordem classificada. BSTs auto-balanceadas — como AVL e árvores vermelho-preta — automaticamente executam rotações após inserções/exclusões para manter a altura ~log n, garantindo operações .
Unbalanced (insert 1,2,3,4): Balanced after rotations:
1 2
\ / \
2 1 3
\ \
3 4
height ~ n (BAD) height ~ log n (GOOD)
| Árvore AVL | Árvore vermelho-preta | |
|---|---|---|
| Rigor do balanceamento | estrito (balanceado por altura) | mais solto |
| Buscas | mais rápido (mais curto) | ligeiramente mais lento |
| Inserção/exclusão | mais rotações | menos rotações |
| Melhor para | cargas de trabalho de leitura | cargas de trabalho de escrita |
| Operação | Tempo |
|---|---|
| busca | O(log n) |
| inserção | O(log n) |
| exclusão | O(log n) |
Ambas mantêm o balanceamento via rotações — reestruturações locais O(1) que preservam a ordenação BST enquanto reduzem a altura.
Árvores balanceadas sustentam mapas ordenados e conjuntos em bibliotecas padrão (ex. Java TreeMap, C++ std::map usam árvores vermelho-preta), fornecendo iteração ordenada mais operações logarítmicas garantidas.
São a resposta quando você precisa da ordenação de uma BST e uma garantia de desempenho rígida contra entrada adversária.