Árvores de auto-equilíbrio são estruturas de dados usadas na ciência da computação para manter dados ordenados de forma eficiente. O fator de equilíbrio é uma métrica chave que ajuda a determinar se uma árvore permanece equilibrada após inserções ou deleções. Entender como calcular esse fator é essencial para engenheiros que projetam algoritmos otimizados.

O que é o fator de equilíbrio?

O fator de equilíbrio de um nó em uma árvore de auto-equilíbrio é a diferença entre as alturas de suas subárvores esquerda e direita. Indica se o nó é equilibrado, com peso esquerdo ou com peso direito. Um fator de equilíbrio de 0, 1 ou - 1 tipicamente significa um nó equilibrado.

Calculando o Fator de Equilíbrio

Para calcular o fator de equilíbrio, meça a altura da subárvore esquerda e subtraia a altura da subárvore direita. A altura de uma subárvore é o número de arestas no caminho mais longo do nó para uma folha. A fórmula é:

Fator de equilíbrio = Altura (Subárvore esquerda) - Altura (Subárvore direita)

Aplicação em Operações em Árvore

Durante a inserção ou exclusão, recalcular o fator de equilíbrio ajuda a determinar se as rotações são necessárias para manter o equilíbrio de árvores. Se o fator de equilíbrio exceder 1 ou cair abaixo de -1, a árvore realiza rotações para restaurar o equilíbrio, garantindo operações eficientes de busca, inserção e exclusão.

Árvores comuns de auto-equilíbrio

  • Árvore AVL
  • Árvore Negra- Vermelha
  • Árvore de Desenho
  • Treap