Rotazione (informatica)

Da Wikipedia, l'enciclopedia libera.

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.

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