Gli alberi autobilancianti sono strutture di dati utilizzate in informatica per mantenere i dati ordinati in modo efficiente. Il fattore di equilibrio è una metrica chiave che aiuta a determinare se un albero rimane equilibrato dopo inserimenti o cancellazioni. Capire come calcolare questo fattore è essenziale per gli ingegneri che progettano algoritmi ottimizzati.

Qual è il fattore di equilibrio?

Il fattore di equilibrio di un nodo in un albero autobilanciante è la differenza tra le altezze dei suoi sottotre di sinistra e di destra. Indica se il nodo è equilibrato, di sinistra-pesante, o di destra-pesante. Un fattore di equilibrio di 0, 1, o -1 significa tipicamente un nodo equilibrato.

Calcolo del fattore di equilibrio

Per calcolare il fattore di equilibrio, misurare l'altezza del sottotetto sinistro e sottrarre l'altezza del sottotreo destro. L'altezza di un sottotreo è il numero di bordi sul percorso più lungo dal nodo a una foglia. La formula è:

Fattore di bilanciamento = Altezza (Sottotreno di sinistra) - Altezza (Sottotreno destro)

Applicazione nelle operazioni sugli alberi

Durante l'inserimento o la cancellazione, il ricalcolo del fattore di equilibrio aiuta a determinare se le rotazioni sono necessarie per mantenere l'equilibrio dell'albero. Se il fattore di equilibrio supera 1 o scende sotto -1, l'albero effettua rotazioni per ripristinare l'equilibrio, garantendo una ricerca efficiente, l'inserimento e l'eliminazione delle operazioni.

Alberi comuni di auto-finanziamento

  • Albero AVL
  • Albero rosso-nero
  • Splay Tree
  • Treap