Splay Tree

Struttura dati di tipo Self-Adjusting.

• Gli Splay Tree implementano operazioni consecutive di ricerca, inserimento, cancellazione in tempo , dove è il numero di inserimenti in un albero inizialmente vuoto.
• Cioè ciascuna delle operazioni è eseguita in un tempo ammortizzato .

Idea:

Per quanto possibile, avvicinare alla radice i nodi che si incontrano durante un accesso.

Una procedura che funziona è di risalire due passi per volta quando possibile.

Splay( x,T)

• Si cerca su con una ricerca binaria.
• A partire dal nodo dove la ricerca si è fermata, e procedendo verso la radice, si applicano le operazioni di tip Zig, Zig-Zag o Zig-Zig necessarie

Insert( x,T)

• Si esegue Splay()
• Si inserisce il nuovo nodo
• Si esegue nuovamente Splay

Siano i nodi:

• , nonno;
• , padre o parent;
• , nodo su cui stiamo effettuando l’operazione.  

Stiamo effettuando l’operazione Splay su in tutti i seguenti esempi:

Zig-Zag

Esempio di Zig-Zag

Ogni nodo si sposta una posizione a destra seguita da una posizione a sinistra dalla posizione corrente. In super short:

Zig-Zig

Esempio di Zig-Zig

Altro non è che una doppia operazione zig, definita sotto. Ogni nodo si muove due posizioni a destra dalla sua posizione attuale.

In super short:

Zig

Nello Zig il nodo è sprovvisto di nonno.  Ogni nodo si muove una posizione a destra dalla sua attuale posizione.

Esempio di Zig

  In super short:

Insert(x,T)

Per inserire il nuovo nodo, prima effettuo una ricerca. 

Ovviamente, non trovando il nodo, effettuo l’inserimento nel punto dove la ricerca è fallita. 

In questo modo, manteniamo la proprietà di ricerca binaria: Difatti, se , saremo sicuri che si trova nel sottoalbero destro rispetto a . Viceversa, se , si troverà nel sottoalbero sinistro.

Dopo l’inserimento, eseguiamo una ulteriore Splay per ribilanciare l’albero.

Esempio di Insert(x,T)

Delete(x,T)

• Si esegue una Splay(x,T) iniziale, portando x alla radice dell’albero.
• Si cancella il nodo x, ottenendo così due alberi .
• Si esegue una Splay(x,), con nuova radice.
• Si pone la radice di come figlio destro di .

Siamo sicuri che .

Esempio di Delete(x,T)

Analisi Ammortizzata Splay Tree

Costi delle operazioni elementari:

• Zig: 1 rotazione
• Zig-Zag: 2 rotazioni
• Zig-Zig: 2 rotazioni

Poniamo:

• , rango di

Esempio di Calcolo \phi(T)

  Sia un albero vuoto, si ha:

 

Sia un qualsiasi albero:

Pertanto, possiamo utlizzare il potenziale per calcolare un upper bound al costo reale di operazioni (cioè ,,) di cui sono , a partire da uno splay tree vuoto. 

Lemma

Siano , e sia  

Allora:

Dimostrazione Si osservi:

Considerando  

 

Prendendo i logaritmi di ambo i membri: 

 

 

Teorema

Il costo ammortizzato dell’operazione Splay(x,T) è al più

Dimostrazione (Per casi!)

Calcoliamo per iniziare il costo ammortizzato di una operazione di tipo Zig, Zig-Zag, Zig-Zig

Notazione e Abbreviazioni

Indiamo con il numero di nodi nel sottoalbero di radice x prima e dopo l’operazione in esame, analogamente per il Rango. 

Inoltre:

• etc… 

Caso Zig-Zig

Costo Reale=2 

 

Si osservi che: 

,     

E quindi: 

  Perciò siamo sicuri che:

 

Caso Zig-Zag

  Costo Reale=2  

Si osservi che: 

,    

E quindi:

,  

#todo La dimostrazione è simile a prima, non c’è tempo di trascriverla correttamente al momento.

Caso Zig

Costo Reale=1 

 

 

Costo Ammortizzato Splay (senza dim, no time):

Gli Splay Tree possono anche essere definiti top-down.