Alberi bilanciati AVL

Cosa sono gli alberi AVL?

Gli alberi AVL sono alberi binari di ricerca auto-bilanciati, dove la differenza di altezza tra i sottoalberi sinistro e destro è al massimo 1.

Proprietà principale degli alberi AVL?

La proprietà principale è che per ogni nodo, l'altezza dei sottoalberi sinistro e destro differisce al massimo di 1.

Vero o falso: Gli alberi AVL possono diventare sbilanciati.

Falso. Gli alberi AVL sono progettati per rimanere bilanciati dopo ogni operazione di inserimento o cancellazione.

Cosa rappresenta il fattore di bilanciamento?

Il fattore di bilanciamento è la differenza tra l'altezza del sottoalbero sinistro e quello destro. Può assumere valori -1, 0 o +1.

Cosa succede se il fattore di bilanciamento è 2?

Se il fattore di bilanciamento è 2, l'albero è sbilanciato e deve essere ruotato per ripristinare l'equilibrio.

Fattore di bilanciamento: +1, 0, -1 significano...

- +1: alto a sinistra - 0: bilanciato - -1: alto a destra

Esempio di rotazione a sinistra?

In un nodo con fattore di bilanciamento +2, se il sottoalbero sinistro ha un fattore di bilanciamento +1 o 0, si utilizza la rotazione a sinistra.

Cosa sono le rotazioni composte?

Le rotazioni composte sono combinazioni di rotazioni a sinistra e a destra per riequilibrare l'albero dopo un'inserzione o cancellazione.

Differenza tra alberi AVL e alberi rossi-neri?

Gli alberi AVL garantiscono un bilanciamento più rigoroso, mentre gli alberi rossi-neri sono più flessibili ma meno bilanciati.

Come calcolare l'altezza di un albero AVL?

L'altezza di un albero AVL è calcolata come il numero massimo di nodi lungo il percorso dalla radice a una foglia.

Cosa significa che un albero è auto-bilanciato?

Significa che dopo ogni operazione (inserimento, cancellazione), l'albero mantiene il suo fattore di bilanciamento entro i limiti definiti.

Cosa sono i nodi foglia in un albero AVL?

I nodi foglia sono nodi senza figli. In un albero AVL, un nodo foglia ha un'altezza di 0.

Cos'è l'inserimento in un albero AVL?

L'inserimento in un albero AVL è un'operazione che aggiunge un nuovo nodo mantenendo l'equilibrio dell'albero. Dopo l'inserimento, l'albero potrebbe richiedere rotazioni per ristabilire le proprietà AVL.

Qual è il fattore di bilanciamento?

Il fattore di bilanciamento è la differenza tra l'altezza del sottoalbero sinistro e quella del sottoalbero destro. Deve essere -1, 0 o 1 per mantenere l'albero AVL bilanciato.

Quando si utilizza una rotazione a sinistra?

Si utilizza una rotazione a sinistra quando un inserimento nel sottoalbero destro causa uno sbilanciamento a destra. Questa rotazione riequilibra l'albero.

Cosa succede durante la cancellazione?

La cancellazione di un nodo potrebbe creare uno sbilanciamento. Dopo la rimozione, è necessario controllare e ripristinare l'equilibrio dell'albero tramite rotazioni.

Rotazione destra + sinistra: che cosa?

Questa è una rotazione doppia, usata quando un nodo è inserito nel sottoalbero sinistro di un nodo destro. Consiste in una rotazione a destra seguita da una rotazione a sinistra.

Vero o Falso: Un albero AVL è sempre perfettamente equilibrato.

Falso. Un albero AVL è bilanciato, ma non perfettamente. Il fattore di bilanciamento può essere -1, 0 o 1.

Esempio di inserimento: 10, 20, 30.

Dopo l'inserimento di 30, l'albero diventa sbilanciato. Si applica una rotazione a sinistra su 10 per riequilibrare.

Cosa determina l'operazione di rotazione?

La rotazione è necessaria quando il fattore di bilanciamento di un nodo diventa maggiore di 1 o minore di -1, indicando uno sbilanciamento.

Tipi di rotazioni: nomina due.

1. Rotazione a sinistra 2. Rotazione a destra

Qual è il risultato di una rotazione a destra?

Una rotazione a destra sposta il nodo sinistro verso la radice e il nodo corrente verso destra, riequilibrando sottoalberi sbilanciati.

Inserimento segreto: come?

Inserisci il nuovo nodo seguendo l'ordinamento, quindi controlla e riequilibra l'albero se necessario.

Quali sono le rotazioni necessarie per un albero sbilanciato?

A seconda dello sbilanciamento, possono essere necessarie: rotazione a destra, rotazione a sinistra, rotazione destra-sinistra, rotazione sinistra-destra.

Qual è la complessità dell'inserimento?

La complessità dell'inserimento in un albero AVL è $\displaystyle O( ext{log } n)$.

Qual è la complessità della cancellazione?

La cancellazione in un albero AVL ha complessità $\displaystyle O( ext{log } n)$, simile all'inserimento.

Vero o falso: Gli alberi AVL sono sempre bilanciati.

Falso. Gli alberi AVL sono bilanciati dopo ogni operazione di inserimento o cancellazione.

Comparazione: Alberi AVL vs. Alberi Rosso-Neri.

- Entrambi sono alberi bilanciati. - Gli AVL sono più bilanciati, ma più lenti nell'inserimento rispetto ai Rosso-Neri.

Qual è la complessità della ricerca?

La complessità della ricerca in un albero AVL è $\displaystyle O( ext{log } n)$.

Completa: La profondità di un albero AVL è al massimo ____.

$\displaystyle 1.44 imes ext{log } n$.

Qual è l'effetto dell'imbalanzamento?

Un albero non bilanciato può degradare la complessità delle operazioni a $\displaystyle O(n)$.

Esempio: Inserimento di 10 in un albero vuoto.

L'inserimento di 10 in un albero AVL vuoto richiede $\displaystyle O(1)$ tempo.

Vero o falso: Gli alberi AVL richiedono più rotazioni.

Vero. Gli alberi AVL richiedono rotazioni per mantenere il bilanciamento.

Cosa determina l'altezza di un albero AVL?

L'altezza è determinata dal numero di nodi e dal bilanciamento.

Qual è il costo di una rotazione?

Il costo di una rotazione è $\displaystyle O(1)$ in un albero AVL.

Qual è la complessità spaziale di un albero AVL?

La complessità spaziale è $\displaystyle O(n)$, dove n è il numero di nodi.