Gli alberi splay sono alberi di ricerca binari autobilanciati o autoregolati. In altre parole possiamo dire che gli splay tree sono le varianti degli alberi binari di ricerca. Il prerequisito per gli alberi splay che dovremmo conoscere sugli alberi di ricerca binari.

Come già sappiamo, la complessità temporale di un albero di ricerca binario in ogni caso. La complessità temporale di un albero di ricerca binario nel caso medio è O(log) e la complessità temporale nel caso peggiore è O(n). In un albero di ricerca binario, il valore del sottoalbero sinistro è inferiore al nodo radice e il valore del sottoalbero destro è maggiore del nodo radice; in tal caso, la complessità temporale sarebbe O(log) . Se l'albero binario fosse inclinato a sinistra o a destra, la complessità temporale sarebbe O(n). Per limitare l'asimmetria, il AVL e albero Rosso-Nero è entrato in scena, avendo O(log ) complessità temporale per tutte le operazioni in tutti i casi. Possiamo anche migliorare questa complessità temporale eseguendo implementazioni più pratiche, quindi il nuovo albero Cos'è uno Splay Tree?

Un albero strombato è un albero autobilanciante, ma Quindi anche gli alberi AVL e Rosso-Nero sono alberi autobilancianti. Ciò che rende unico l'albero strombato sono due alberi. Ha una proprietà in più che lo rende unico è l'allargamento.

Un albero splay contiene le stesse operazioni di a Albero di ricerca binario , ovvero inserimento, cancellazione e ricerca, ma contiene anche un'altra operazione, ovvero l'allargamento. COSÌ. tutte le operazioni nell'albero di splay sono seguite dallo splaying.

Gli alberi splay non sono alberi strettamente bilanciati, ma sono alberi approssimativamente bilanciati. Comprendiamo l'operazione di ricerca nello splay-tree.

Supponiamo di voler cercare 7 elementi nell'albero, mostrato di seguito:

Per cercare qualsiasi elemento nell'albero splay, eseguiremo innanzitutto l'operazione standard dell'albero di ricerca binario. Poiché 7 è inferiore a 10, arriveremo a sinistra del nodo radice. Dopo aver eseguito l'operazione di ricerca, dobbiamo eseguire la divaricazione. Qui splaying significa che l'operazione che stiamo eseguendo su qualsiasi elemento dovrebbe diventare il nodo radice dopo aver eseguito alcuni riarrangiamenti. La risistemazione dell'albero avverrà attraverso le rotazioni.

Nota: l'albero splay può essere definito come l'albero auto-regolato in cui qualsiasi operazione eseguita sull'elemento riorganizzerebbe l'albero in modo che l'elemento su cui è stata eseguita l'operazione diventi il ​​nodo radice dell'albero.

Rotazioni

Esistono sei tipi di rotazioni utilizzate per l'allargamento:

1. Rotazione a zig (rotazione a destra)
2. Rotazione Zag (rotazione a sinistra)
3. Zig zag (Zig seguito da zag)
4. Zag zig (Zag seguito da zig)
5. Zig zig (due rotazioni a destra)
6. Zag zag (due rotazioni a sinistra)

Fattori necessari per la selezione del tipo di rotazione

Di seguito sono riportati i fattori utilizzati per la selezione del tipo di rotazione:

• Il nodo che stiamo cercando di ruotare ha un nonno?
• Il nodo è figlio sinistro o destro del genitore?
• Il nodo sinistro o destro è figlio del nonno?

Casi per le rotazioni

Caso 1: Se il nodo non ha un nonno, e se è il figlio destro del genitore, allora effettuiamo la rotazione a sinistra; in caso contrario, viene eseguita la rotazione destra.

Caso 2: Se il nodo ha un nonno, in base ai seguenti scenari; la rotazione verrebbe eseguita:

Scenario 1: Se il nodo è il diritto del genitore e anche il genitore ha il diritto del suo genitore, allora zig zig rotazione destra destra viene eseguita.

Scenario 2: Se il nodo è a sinistra di un genitore, ma il genitore è a destra del suo genitore, allora rotazione a zig zag destra sinistra viene eseguita.

Scenario 3: Se il nodo è a destra del genitore e il genitore ha diritto al suo genitore, allora zig zig rotazione sinistra sinistra viene eseguita.

Scenario 4: Se il nodo è a destra di un genitore, ma il genitore è a sinistra del suo genitore, allora rotazione a zig zag destra-sinistra viene eseguita.

Ora, comprendiamo le rotazioni di cui sopra con esempi.

Per riorganizzare l'albero, dobbiamo eseguire alcune rotazioni. Di seguito sono riportati i tipi di rotazioni nell'albero di strombatura:

Rotazioni a zig

Le rotazioni a zig vengono utilizzate quando l'elemento da cercare è un nodo radice o il figlio di un nodo radice (ovvero, il figlio sinistro o destro).

Di seguito sono riportati i casi che possono esistere nell'albero splay durante la ricerca:

Caso 1: Se l'elemento di ricerca è un nodo radice dell'albero.

Caso 2: Se l'elemento di ricerca è figlio del nodo radice, si presenteranno i due scenari:

1. Se il bambino è sinistro, verrà eseguita la rotazione a destra, nota come rotazione a destra a zig.
2. Se il bambino è destro, verrà eseguita la rotazione a sinistra, nota come rotazione a zig a sinistra.

Diamo un'occhiata ai due scenari precedenti attraverso un esempio.

Considera l'esempio seguente:

Nell'esempio sopra, dobbiamo cercare 7 elementi nell'albero. Seguiremo i passaggi seguenti:

Passo 1: Per prima cosa confrontiamo 7 con un nodo radice. Poiché 7 è inferiore a 10, quindi è un figlio sinistro del nodo radice.

Passo 2: Una volta trovato l'elemento, eseguiremo la divaricazione. La rotazione a destra viene eseguita in modo che 7 diventi il ​​nodo radice dell'albero, come mostrato di seguito:

Consideriamo un altro esempio.

Nell'esempio sopra, dobbiamo cercare 20 elementi nell'albero. Seguiremo i passaggi seguenti:

Passo 1: Per prima cosa confrontiamo 20 con un nodo radice. Poiché 20 è maggiore del nodo radice, quindi è un figlio destro del nodo radice.

Passo 2: Una volta trovato l'elemento, eseguiremo la divaricazione. La rotazione a sinistra viene eseguita in modo che 20 elementi diventino il nodo radice dell'albero.

Rotazioni a zig zig

A volte si verifica la situazione in cui l'oggetto da cercare ha sia un genitore che un nonno. In questo caso dobbiamo eseguire quattro rotazioni di divaricazione.

Capiamo questo caso attraverso un esempio.

Supponiamo di dover cercare 1 elemento nell'albero, mostrato di seguito:

Passo 1: Innanzitutto, dobbiamo eseguire un'operazione di ricerca BST standard per cercare l'1 elemento. Poiché 1 è inferiore a 10 e 7, sarà a sinistra del nodo 7. Pertanto, l'elemento 1 ha un genitore, ovvero 7, nonché un nonno, ovvero 10.

Passo 2: In questo passaggio, dobbiamo eseguire la divaricazione. Dobbiamo rendere il nodo 1 come nodo radice con l'aiuto di alcune rotazioni. In questo caso non possiamo semplicemente eseguire una rotazione a zig o zag; dobbiamo implementare la rotazione a zig zig.

Per rendere il nodo 1 come nodo radice, dobbiamo eseguire due rotazioni destre note come rotazioni a zig zig. Quando eseguiamo la rotazione verso destra, il nodo 10 si sposterà verso il basso e il nodo 7 verrà verso l'alto come mostrato nella figura seguente:

Ancora una volta, eseguiremo la rotazione zig a destra, il nodo 7 si sposterà verso il basso e il nodo 1 verrà verso l'alto come mostrato di seguito:

Come osserviamo nella figura sopra, il nodo 1 è diventato il nodo radice dell'albero; pertanto la ricerca è completata.

Supponiamo di voler cercarne 20 nell'albero sottostante.

Per cercarne 20, dobbiamo eseguire due rotazioni a sinistra. Di seguito sono riportati i passaggi necessari per cercare 20 nodi:

Passo 1: Innanzitutto, eseguiamo l'operazione di ricerca BST standard. Poiché 20 è maggiore di 10 e 15, sarà a destra del nodo 15.

Passo 2: Il secondo passo è eseguire l'allargamento. In questo caso verrebbero eseguite due rotazioni a sinistra. Nella prima rotazione, il nodo 10 si sposterà verso il basso e il nodo 15 si sposterà verso l'alto come mostrato di seguito:

Nella seconda rotazione a sinistra, il nodo 15 si sposterà verso il basso e il nodo 20 diventerà il nodo radice dell'albero, come mostrato di seguito:

Come abbiamo osservato vengono eseguite due rotazioni a sinistra; quindi è nota come rotazione a zig zig verso sinistra.

Rotazioni a zig zag

Fino ad ora, abbiamo letto che sia i genitori che i nonni hanno una relazione RR o LL. Ora vedremo la relazione RL o LR tra il genitore e il nonno.

Capiamo questo caso attraverso un esempio.

Supponiamo di voler cercare 13 elementi nell'albero mostrato di seguito:

Passo 1: Innanzitutto, eseguiamo un'operazione di ricerca BST standard. Poiché 13 è maggiore di 10 ma minore di 15, il nodo 13 sarà il figlio sinistro del nodo 15.

Passo 2: Poiché il nodo 13 è a sinistra di 15 e il nodo 15 è a destra del nodo 10, esiste una relazione RL. Innanzitutto, eseguiamo la rotazione verso destra sul nodo 15, il 15 si sposterà verso il basso e il nodo 13 si sposterà verso l'alto, come mostrato di seguito:

Tuttavia, il nodo 13 non è il nodo radice e 13 è a destra del nodo radice, quindi eseguiremo la rotazione a sinistra nota come rotazione zag. Il nodo 10 si sposterà verso il basso e 13 diventerà il nodo radice come mostrato di seguito:

Come possiamo osservare nell'albero sopra, il nodo 13 è diventato il nodo radice; pertanto la ricerca è completata. In questo caso abbiamo eseguito prima la rotazione a zig e poi la rotazione a zag; quindi, è nota come rotazione a zig zag.

Rotazione zag zig

Capiamo questo caso attraverso un esempio.

Supponiamo di voler cercare 9 elementi nell'albero, mostrato di seguito:

Passo 1: Innanzitutto, eseguiamo l'operazione di ricerca BST standard. Poiché 9 è inferiore a 10 ma maggiore di 7, sarà il figlio destro del nodo 7.

Passo 2: Poiché il nodo 9 è a destra del nodo 7 e il nodo 7 è a sinistra del nodo 10, esiste una relazione LR. Innanzitutto, eseguiamo la rotazione a sinistra sul nodo 7. Il nodo 7 si sposterà verso il basso e il nodo 9 si sposterà verso l'alto come mostrato di seguito:

Tuttavia il nodo 9 non è un nodo radice e 9 è a sinistra del nodo radice, quindi eseguiremo la rotazione verso destra nota come rotazione a zig. Dopo aver eseguito la rotazione verso destra, il nodo 9 diventa il nodo radice, come mostrato di seguito:

Come possiamo osservare nell'albero sopra, il nodo 13 è un nodo radice; pertanto la ricerca è completata. In questo caso, abbiamo prima eseguito la rotazione zag (rotazione sinistra), quindi viene eseguita la rotazione zig (rotazione destra), quindi è nota come rotazione zag zig.

Vantaggi dell'albero Splay

• Nello splay tree non è necessario memorizzare informazioni aggiuntive. Al contrario, negli alberi AVL, dobbiamo memorizzare il fattore di equilibrio di ciascun nodo che richiede spazio extra, e gli alberi Rosso-Nero richiedono anche di memorizzare un bit extra di informazione che denota il colore del nodo, Rosso o Nero.
• È il tipo più veloce di albero di ricerca binaria per varie applicazioni pratiche. È usato dentro Compilatori Windows NT e GCC .
• Fornisce prestazioni migliori poiché i nodi a cui si accede frequentemente si sposteranno più vicino al nodo radice, grazie al quale è possibile accedere rapidamente agli elementi negli alberi splay. Viene utilizzato nell'implementazione della cache poiché i dati a cui si accede di recente vengono archiviati nella cache in modo che non sia necessario accedere alla memoria per accedere ai dati e ciò richiede meno tempo.

Svantaggio dell'albero Splay

Lo svantaggio principale dell'albero strombato sarebbe che gli alberi non sono strettamente bilanciati, cioè sono approssimativamente bilanciati. A volte gli alberi splay sono lineari, quindi richiederà una complessità temporale O (n).

Operazione di inserimento nell'albero Splay

Nel inserimento operazione, inseriamo prima l'elemento nell'albero e poi eseguiamo l'operazione di divaricazione sull'elemento inserito.

15, 10, 17, 7

Passo 1: Per prima cosa inseriamo il nodo 15 nell'albero. Dopo l'inserimento è necessario eseguire la divaricazione. Dato che 15 è un nodo radice, non è necessario eseguire lo splaying.

Passo 2: L'elemento successivo è 10. Poiché 10 è inferiore a 15, quindi il nodo 10 sarà il figlio sinistro del nodo 15, come mostrato di seguito:

Adesso ci esibiamo allargamento . Per rendere 10 come nodo radice, eseguiremo la rotazione destra, come mostrato di seguito:

Passaggio 3: L'elemento successivo è 17. Poiché 17 è maggiore di 10 e 15, diventerà il figlio destro del nodo 15.

Ora eseguiremo l'allargamento. Dato che 17 ha un genitore e un nonno, eseguiremo rotazioni a zig zig.

Nella figura sopra possiamo osservare che 17 diventa il nodo radice dell'albero; pertanto l'inserimento è completato.

Passaggio 4: L'elemento successivo è 7. Poiché 7 è inferiore a 17, 15 e 10, quindi il nodo 7 rimarrà figlio di 10.

Ora dobbiamo allargare l'albero. Poiché 7 ha un genitore e un nonno, eseguiremo due rotazioni a destra come mostrato di seguito:

Tuttavia, il nodo 7 non è un nodo radice, è un figlio sinistro del nodo radice, ovvero 17. Quindi, dobbiamo eseguire un'altra rotazione a destra per rendere il nodo 7 un nodo radice, come mostrato di seguito:

Algoritmo per l'operazione di inserimento

 Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n) 

Nell'algoritmo sopra, T è l'albero en è il nodo che vogliamo inserire. Abbiamo creato una variabile temporanea che contiene l'indirizzo del nodo radice. Eseguiremo il ciclo while finché il valore di temp non diventerà NULL.

Una volta completato l'inserimento verrà eseguita la divaricazione

Algoritmo per l'operazione di splaying

 Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y 

Nell'implementazione precedente, x è il nodo su cui viene eseguita la rotazione, mentre y è il figlio sinistro del nodo x.

Implementazione di left.rotation(T, x)

 left.rotation(T, x) y=x->right x->right = y->left y->left = x return y 

Nell'implementazione precedente, x è il nodo su cui viene eseguita la rotazione e y è il figlio destro del nodo x.

Cancellazione nell'albero Splay

Poiché sappiamo che gli alberi di splay sono le varianti dell'albero di ricerca binario, quindi l'operazione di cancellazione nell'albero di splay sarebbe simile al BST, ma l'unica differenza è che l'operazione di cancellazione è seguita negli alberi di splay dall'operazione di splay.

Tipi di eliminazioni:

Esistono due tipi di eliminazioni negli alberi splay:

1. Allargamento dal basso verso l'alto
2. Diffusione dall'alto verso il basso

Allargamento dal basso verso l'alto

Nello splaying bottom-up, prima eliminiamo l'elemento dall'albero e poi eseguiamo lo splaying sul nodo eliminato.

Comprendiamo la cancellazione nell'albero Splay.

Supponiamo di voler eliminare 12, 14 dall'albero mostrato di seguito:

allineamento img css

• Innanzitutto, eseguiamo semplicemente l'operazione di eliminazione BST standard per eliminare 12 elementi. Dato che 12 è un nodo foglia, eliminiamo semplicemente il nodo dall'albero.

La cancellazione non è ancora stata completata. Dobbiamo visualizzare il genitore del nodo eliminato, ovvero 10. Dobbiamo eseguire Gioco(10) sull'albero. Come possiamo osservare nell'albero sopra, 10 è a destra del nodo 7 e il nodo 7 è a sinistra del nodo 13. Quindi, prima eseguiamo la rotazione a sinistra sul nodo 7 e poi eseguiamo la rotazione a destra sul nodo 13, come di seguito illustrato:

Tuttavia, il nodo 10 non è un nodo radice; il nodo 10 è il figlio sinistro del nodo radice. Quindi, dobbiamo eseguire la giusta rotazione sul nodo radice, ovvero 14 per rendere il nodo 10 un nodo radice come mostrato di seguito:

• Ora dobbiamo eliminare l'elemento 14 dall'albero, che è mostrato di seguito:

Come sappiamo, non possiamo semplicemente eliminare il nodo interno. Sostituiremo il valore del nodo utilizzando predecessore in ordine O successore in ordine . Supponiamo di utilizzare un successore inordine in cui sostituiamo il valore con il valore più basso esistente nel sottoalbero destro. Il valore più basso nel sottoalbero destro del nodo 14 è 15, quindi sostituiamo il valore 14 con 15. Poiché il nodo 14 diventa il nodo foglia, possiamo semplicemente eliminarlo come mostrato di seguito:

Tuttavia, la cancellazione non è stata completata. Dobbiamo eseguire un'altra operazione, ovvero l'allargamento in cui dobbiamo rendere il genitore del nodo eliminato come nodo radice. Prima della cancellazione, il genitore del nodo 14 era il nodo radice, ovvero 10, quindi in questo caso è necessario eseguire qualsiasi allargamento.

Diffusione dall'alto verso il basso

Nello splaying top-down, eseguiamo prima lo splaying su cui si vuole effettuare la cancellazione e poi eliminiamo il nodo dall'albero. Una volta eliminato l'elemento, eseguiremo l'operazione di unione.

Capiamo lo splaying top-down attraverso un esempio.

Supponiamo di voler eliminare 16 dall'albero mostrato di seguito:

Passo 1: Nell'allargamento top-down, per prima cosa eseguiamo l'allargamento sul nodo 16. Il nodo 16 ha sia il genitore che il nonno. Il nodo 16 è alla destra del suo genitore e anche il nodo genitore è alla destra del suo genitore, quindi questa è una situazione zag zag. In questo caso, prima eseguiremo la rotazione a sinistra sul nodo 13 e poi sul 14 come mostrato di seguito:

Il nodo 16 non è ancora un nodo radice ed è un figlio destro del nodo radice, quindi dobbiamo eseguire la rotazione a sinistra sul nodo 12 per rendere il nodo 16 un nodo radice.

Una volta che il nodo 16 diventa un nodo radice, elimineremo il nodo 16 e otterremo due alberi diversi, ovvero il sottoalbero sinistro e il sottoalbero destro come mostrato di seguito:

Come sappiamo, i valori del sottoalbero di sinistra sono sempre inferiori ai valori del sottoalbero di destra. La radice del sottoalbero di sinistra è 12 e la radice del sottoalbero di destra è 17. Il primo passo è trovare l'elemento massimo nel sottoalbero di sinistra. Nel sottoalbero di sinistra, l'elemento massimo è 15, quindi dobbiamo eseguire l'operazione di divaricazione su 15.

Come possiamo osservare nell'albero sopra, l'elemento 15 ha un genitore e un nonno. Un nodo è a destra del suo genitore e anche il nodo genitore è a destra del suo genitore, quindi dobbiamo eseguire due rotazioni a sinistra per rendere il nodo 15 un nodo radice come mostrato di seguito:

Dopo aver eseguito due rotazioni sull'albero, il nodo 15 diventa il nodo radice. Come possiamo vedere, il figlio destro del 15 è NULL, quindi colleghiamo il nodo 17 alla parte destra del 15 come mostrato di seguito, e questa operazione è nota come giuntura operazione.

Nota: Se l'elemento non è presente nell'albero di splay, che deve essere cancellato, allora verrà eseguito lo splay. L'allargamento verrebbe eseguito sull'ultimo elemento a cui si è effettuato l'accesso prima di raggiungere il NULL.

Algoritmo dell'operazione Elimina

 If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root 

Nell'algoritmo sopra, controlliamo prima se la radice è Null o meno; se la radice è NULL significa che l'albero è vuoto. Se l'albero non è vuoto eseguiremo l'operazione di allargamento sull'elemento da eliminare. Una volta completata l'operazione di divaricazione confronteremo i dati della radice con l'elemento da eliminare; se entrambi non sono uguali significa che l'elemento non è presente nell'albero. Se sono uguali, possono verificarsi i seguenti casi:

Caso 1 : La sinistra della radice è NULL, la destra della radice diventa il nodo radice.

Caso 2 : Se esistono sia la sinistra che la destra, allora allarghiamo l'elemento massimo nel sottoalbero sinistro. Una volta completata la divaricazione, l'elemento massimo diventa la radice del sottoalbero sinistro. Il sottoalbero destro diventerebbe il figlio destro della radice del sottoalbero sinistro.