Rotazione (informatica)

Da Wikipedia, l'enciclopedia libera.
Vai alla navigazione Vai alla ricerca
Rotazione a destra sul nodo Head 10

La rotazione è, in informatica, un procedimento attuato su un albero binario di ricerca per renderlo bilanciato senza intaccare le regole di ordinamento degli elementi o nodi dell'albero.

Scopo[modifica | modifica wikitesto]

La rotazione opera spostando volta per volta un nodo più sopra e un nodo più sotto nella struttura dell'albero. È usata per cambiare la forma dell'albero e in particolare per diminuirne l'altezza al fine di migliorare il bilanciamento dell'albero stesso. Ciò avviene spostando sottoalberi più piccoli in posizioni più basse e sottoalberi più grandi in posizioni più alte. I benefici di tale procedimento si avvertono in molte operazioni comuni negli alberi binari di ricerca (ad esempio inserimento e rimozione).

Regole di ordinamento[modifica | modifica wikitesto]

Assegnato il valore della radice e dato un nodo contenente un valore x da inserire nell'albero, se i nodi dell'albero contengono numeri le regole di ordinamento di un albero binario di ricerca sono le seguenti: si parte dalla radice e si va a sinistra se x è minore della radice e a destra se x è maggiore della radice. Effettuato questo passaggio, si procede allo stesso modo finché si incontra un nodo che non ha entrambi i figli. A quel punto si posiziona il nodo contenente il dato x e il processo termina.

  Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica