Rotazione (informatica)
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
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
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.
