Albero splay
Da Wikipedia, l'enciclopedia libera.
Uno albero splay è un albero per ricerca binaria bilanciata con la proprietà, che gli elementi che vengono accessi più frequentemente, si trovano più vicini alla radice, di modo che la loro ricerca dura meno. Per ottenere questa proprietà, si allarga (in inglese splay) l'albero in modo che il nodo contenente la chiave cercata, viene spostato alla radice attraverso delle rotazioni. Queste rotazioni oltre a portare il nodo alla radice, accorcia la distanza tra la radice e tutti i nodi che si trovavano sul percorso che andava dalla precedente radice, al nodo che contiene la chiave cercata, di circa la metà.
Gli alberi splay sono preferiti per l'implementazione di cache, in cui le informazioni non sono accedute uniformemente (accesso casuale), ma una parte degli elementi vengono acceduti più frequentementente di altri (accesso localizzato). Ad ogni accesso l'algoritmo splay sposta tale nodo alla radice, e di conseguenza gli elementi acceduti più frequentemente si trovano sempre vicino alla radice dell'albero, rendendi più velocemente accessibili e migliorando sensibilmente i tempi di accesso globali alla cache nelle operazioni di ricerca e cancellazione. Nonostante il vantaggio prestazionale rispetto a un Albero_AVL, esistono più implementazioni e migliori librerie del secondo tipo, per la sua maggiore semplicità e per il fatto che il collo di bottiglia di molte cache è l'accesso al disco (più lento di tre ordini di grandezza) e non le operazioni sulla struttura dati.
