Albero splay

Un albero splay è un albero binario di ricerca con la proprietà che gli elementi cui si è acceduto più di recente tendono a trovarsi più vicini alla radice. In questo modo la loro ricerca è più efficiente che in un normale albero binario e talvolta anche più che in un albero bilanciato. 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, accorciano di circa la metà la distanza tra la radice e tutti i nodi visitati durante la ricerca. Tuttavia, esse non garantiscono che l'albero risultante sia bilanciato, e nel caso peggiore un accesso a un nodo può richiedere di visitare tutti i nodi dell'albero (complessità lineare); il costo ammortizzato invece è $O(\log n)$.

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.

Collegamenti esterni

• (EN) Eric W. Weisstein, Splay Tree, su MathWorld, Wolfram Research.