L'albero di splay è una struttura dati ad albero di ricerca binaria autoregolante, il che significa che la struttura ad albero viene regolata dinamicamente in base agli elementi a cui si accede o vengono inseriti. In altre parole, l'albero si riorganizza automaticamente in modo che gli elementi a cui si accede o che vengono inseriti di frequente si avvicinino al nodo radice.

1. Lo splay tree è stato introdotto per la prima volta da Daniel Dominic Sleator e Robert Endre Tarjan nel 1985. Ha un'implementazione semplice ed efficiente che gli consente di eseguire operazioni di ricerca, inserimento ed eliminazione con complessità temporale ammortizzata O (log n), dove n è il valore numero di elementi nell'albero.
2. L'idea di base dietro gli splay tree è quella di portare l'elemento a cui si è avuto accesso o inserito più recentemente alla radice dell'albero eseguendo una sequenza di rotazioni dell'albero, chiamata splaying. L'allargamento è un processo di ristrutturazione dell'albero rendendo l'elemento a cui si è avuto accesso o inserito più recentemente la nuova radice e spostando gradualmente i nodi rimanenti più vicini alla radice.
3. Gli alberi strombati sono altamente efficienti nella pratica grazie alla loro natura autoregolante, che riduce il tempo di accesso complessivo per gli elementi a cui si accede frequentemente. Ciò li rende una buona scelta per le applicazioni che richiedono strutture dati veloci e dinamiche, come sistemi di caching, compressione dei dati e algoritmi di routing di rete.
4. Tuttavia, lo svantaggio principale degli alberi splay è che non garantiscono una struttura ad albero equilibrata, il che può portare a un degrado delle prestazioni negli scenari peggiori. Inoltre, gli alberi splay non sono adatti per applicazioni che richiedono prestazioni garantite nel caso peggiore, come sistemi in tempo reale o sistemi critici per la sicurezza.

Nel complesso, gli alberi splay sono una struttura dati potente e versatile che offre un accesso rapido ed efficiente agli elementi a cui si accede o che vengono inseriti di frequente. Sono ampiamente utilizzati in varie applicazioni e forniscono un eccellente compromesso tra prestazioni e semplicità.

Uno splay tree è un albero di ricerca binario autobilanciante, progettato per un accesso efficiente agli elementi di dati in base ai loro valori chiave.

• La caratteristica fondamentale di uno splay tree è che ogni volta che si accede ad un elemento, questo viene spostato alla radice dell'albero, creando una struttura più equilibrata per gli accessi successivi.
• Gli alberi strombati sono caratterizzati dall'uso delle rotazioni, che sono trasformazioni locali dell'albero che ne cambiano la forma ma preservano l'ordine degli elementi.
• Le rotazioni vengono utilizzate per portare l'elemento a cui si accede alla radice dell'albero e anche per riequilibrare l'albero se diventa sbilanciato dopo più accessi.

Operazioni in un albero splay:

• Inserimento: Per inserire un nuovo elemento nell'albero, iniziare eseguendo un normale inserimento nell'albero di ricerca binario. Quindi, applica le rotazioni per portare l'elemento appena inserito alla radice dell'albero.
• Cancellazione : Per eliminare un elemento dall'albero, individuarlo innanzitutto utilizzando una ricerca nell'albero di ricerca binaria. Quindi, se l'elemento non ha figli, rimuovilo semplicemente. Se ha un figlio, promuovi quel bambino alla sua posizione nell'albero. Se ha due figli, trova il successore dell'elemento (l'elemento più piccolo nel suo sottoalbero destro), scambia la sua chiave con l'elemento da eliminare ed elimina invece il successore.
• Ricerca : Per cercare un elemento nell'albero, iniziare eseguendo una ricerca binaria nell'albero. Se l'elemento viene trovato, applica delle rotazioni per portarlo alla radice dell'albero. Se non viene trovato, applica le rotazioni all'ultimo nodo visitato nella ricerca, che diventa la nuova radice.
• Rotazione : Le rotazioni utilizzate in un albero strozzato sono una rotazione Zig o Zig-Zig. Una rotazione Zig viene utilizzata per portare un nodo alla radice, mentre una rotazione Zig-Zig viene utilizzata per bilanciare l'albero dopo accessi multipli agli elementi nello stesso sottoalbero.

Ecco una spiegazione passo passo delle operazioni di rotazione:

• Rotazione a zig : Se un nodo ha un figlio destro, esegui una rotazione verso destra per portarlo alla radice. Se ha un figlio sinistro, esegui una rotazione a sinistra.
• Rotazione Zig-Zig: Se un nodo ha un nipote che è anche il figlio destro o sinistro del suo figlio, esegui una doppia rotazione per bilanciare l'albero. Ad esempio, se il nodo ha un figlio destro e il figlio destro ha un figlio sinistro, esegui una rotazione destra-sinistra. Se il nodo ha un figlio sinistro e il figlio sinistro ha un figlio destro, esegui una rotazione sinistra-destra.
• Nota: I dettagli specifici dell'implementazione, comprese le esatte rotazioni utilizzate, possono variare a seconda della forma esatta dell'albero di strombatura.

Rotazioni nell'albero di splay

• Rotazione a zig
• Rotazione Zag
• Zig – Rotazione Zig
• Zag – Rotazione Zag
• Rotazione Zig-Zag
• Zag – Rotazione a zig

1) Rotazione a zig:

La rotazione Zig negli alberi splay funziona in modo simile alla singola rotazione destra nelle rotazioni degli alberi AVL. Questa rotazione fa sì che i nodi si spostino di una posizione a destra rispetto alla loro posizione corrente. Ad esempio, considera il seguente scenario:

Rotazione a zig (rotazione singola)

2) Rotazione Zag:

La rotazione Zag negli alberi splay funziona in modo simile alla rotazione singola a sinistra nelle rotazioni degli alberi AVL. Durante questa rotazione, i nodi si spostano di una posizione a sinistra rispetto alla loro posizione attuale. Ad esempio, considera la seguente illustrazione:

lunghezza della stringa java

Rotazione Zag (rotazione singola a sinistra)

3) Rotazione Zig-Zig:

La rotazione Zig-Zig negli alberi strozzati è una doppia rotazione a zig. Questa rotazione fa sì che i nodi si spostino di due posizioni a destra rispetto alla loro posizione attuale. Dai un'occhiata al seguente esempio per una migliore comprensione:

Rotazione Zig-Zig (doppia rotazione a destra)

4) Rotazione Zag-Zag:

Negli alberi strozzati, la rotazione Zag-Zag è una rotazione a doppio zag. Questa rotazione fa sì che i nodi si spostino di due posizioni a sinistra rispetto alla loro posizione attuale. Per esempio:

Rotazione Zag-Zag (doppia rotazione a sinistra)

5) Rotazione a zig-zag:

La rotazione a zig-zag negli alberi strozzati è una combinazione di una rotazione a zig seguita da una rotazione a zag. Come risultato di questa rotazione, i nodi si spostano di una posizione a destra e poi di una posizione a sinistra rispetto alla loro posizione attuale. L'illustrazione seguente fornisce una rappresentazione visiva di questo concetto:

Rotazione Zig-Zag

dimensioni del testo in lattice

6) Rotazione Zag-Zig:

La rotazione Zag-Zig negli alberi splay è una serie di rotazioni zag seguite da una rotazione zig. Ciò si traduce nello spostamento dei nodi di una posizione a sinistra, seguito da uno spostamento di una posizione a destra dalla loro posizione corrente. L'illustrazione seguente offre una rappresentazione visiva di questo concetto:

Rotazione Zag-Zig

Di seguito è riportato il codice C++ per implementare le rotazioni nell'albero Splay:

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->chiave = chiave;  nodo->sinistra = nodo->destra = nullptr;  nodo di ritorno; } Nodo* rightRotate(Nodo* x) { Nodo* y = x->sinistra;  x->sinistra = y->destra;  y->destra = x;  restituire y; } Nodo* sinistraRuota(Nodo* x) { Nodo* y = x->destra;  x->destra = y->sinistra;  y->sinistra = x;  restituire y; } Node* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root;  if (root->key> key) { if (root->left == nullptr) return root;  if (radice->sinistra->tasto> tasto) { radice->sinistra->sinistra = splay(radice->sinistra->sinistra, tasto);  radice = destraRuota(radice);  } altrimenti se (root->sinistra->tasto< key) {  root->sinistra->destra = splay(radice->sinistra->destra, tasto);  if (radice->sinistra->destra!= nullptr) radice->sinistra = sinistraRuota(radice->sinistra);  } return (root->sinistra == nullptr) ? radice: destraRuota(radice);  } else { if (root->right == nullptr) return root;  if (radice->destra->tasto> tasto) { radice->destra->sinistra = splay(radice->destra->sinistra, tasto);  if (radice->destra->sinistra!= nullptr) radice->destra = destraRuota(radice->destra);  } altrimenti se (root->destra->tasto< key) {  root->destra->destra = splay(radice->destra->destra, tasto);  radice = ruota a sinistra(radice);  } return (root->destra == nullptr) ? radice: sinistraRuota(radice);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  radice = splay(radice, chiave);  if (root->key == key) restituisce root;  Nodo* nodo = nuovoNodo(chiave);  if (root->key> key) { nodo->right = root;  nodo->sinistra = radice->sinistra;  root->sinistra = nullptr;  } else { nodo->sinistra = radice;  nodo->destra = radice->destra;  root->destra = nullptr;  } nodo restituito; } void preOrder(Nodo* nodo) { if (nodo!= nullptr) { cout<< node->chiave<< ' ';  preOrder(node->Sinistra);  preOrdine(nodo->destra);  } } int main() { Nodo* root = nullptr;  radice = inserisci(radice, 100);  radice = inserisci(radice, 50);  radice = inserisci(radice, 200);  radice = inserisci(radice, 40);  radice = inserisci(radice, 60);  cout<< 'Preorder traversal of the modified Splay tree:' << endl;  preOrder(root);  return 0; }>

// Java Program for the above approach class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key) {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x) {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x) {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key) {  if (root == null || root.key == key)  return root;  if (root.key>chiave) { if (root.left == null) restituisce root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  radice = destraRuota(radice);  } altrimenti se (root.left.key< key) {  root.left.right = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>chiave) { root.right.left = splay(root.right.left, key);  if (root.right.left!= null) root.right = rightRotate(root.right);  } altrimenti se (root.right.key< key) {  root.right.right = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root : leftRotate(root);  }  }  static Node insert(Node root, int key) {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>chiave) { nodo.destra = radice;  nodo.sinistra = radice.sinistra;  root.sinistra = null;  } else { nodo.sinistra = radice;  nodo.destra = radice.destra;  radice.destra = null;  } nodo restituito;  } static void preOrder(Nodo nodo) { if (nodo != null) { System.out.println();  System.out.print(node.key + ' ');  preordine(nodo.sinistra);  preordine(node.right);  } } public static void main(String[] args) { Node root = null;  radice = inserisci(radice, 100);  radice = inserisci(radice, 50);  radice = inserisci(radice, 200);  radice = inserisci(radice, 40);  radice = inserisci(radice, 60);  System.out.println('Preordina l'attraversamento dell'albero Splay modificato:');  preordine(root);  } } // Questo codice è un contributo di Princekumaras>

class Node: def __init__(self, key): self.key = key self.left = None self.right = None def new_node(key): return Node(key) def right_rotate(x): y = x.left x.left = y.right y.right = x return y def left_rotate(x): y = x.right x.right = y.left y.left = x return y def splay(root, key): if root is None : return new_node(key) if root.key == key: return root if root.key>chiave: se root.left è None: restituisce root se root.left.key> chiave: root.left.left = splay(root.left.left, key) root = right_rotate(root) elif root.left.key< key: root.left.right = splay(root.left.right, key) if root.left.right: root.left = left_rotate(root.left) return root.left if root.left is None else right_rotate(root) else: if root.right is None: return root if root.right.key>chiave: root.right.left = splay(root.right.left, key) if root.right.left: root.right = right_rotate(root.right) elif root.right.key< key: root.right.right = splay(root.right.right, key) root = left_rotate(root) return root.right if root.right is None else left_rotate(root) def insert(root, key): if root is None: return new_node(key) root = splay(root, key) if root.key == key: return root node = new_node(key) if root.key>chiave: nodo.destra = radice nodo.sinistra = radice.sinistra radice.sinistra = Nessun altro: nodo.sinistra = radice nodo.destra = radice.destra radice.destra = Nessuno return node def pre_order(nodo): if nodo: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Nessuno root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Attraversamento in preordine dell'albero Splay modificato:') pre_order(root)>

// C# program for the above approach using System; class Node {  public int key;  public Node left, right; } class SplayTree {  static Node newNode(int key)  {  Node node = new Node();  node.key = key;  node.left = node.right = null;  return node;  }  static Node rightRotate(Node x)  {  Node y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static Node leftRotate(Node x)  {  Node y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static Node splay(Node root, int key)  {  if (root == null || root.key == key)  return root;  if (root.key>chiave) { if (root.left == null) restituisce root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  radice = destraRuota(radice);  } altrimenti se (root.left.key< key) {  root.left.right  = splay(root.left.right, key);  if (root.left.right != null)  root.left = leftRotate(root.left);  }  return (root.left == null) ? root  : rightRotate(root);  }  else {  if (root.right == null)  return root;  if (root.right.key>chiave) { root.right.left = splay(root.right.left, key);  if (root.right.left!= null) root.right = rightRotate(root.right);  } altrimenti se (root.right.key< key) {  root.right.right  = splay(root.right.right, key);  root = leftRotate(root);  }  return (root.right == null) ? root  : leftRotate(root);  }  }  static Node insert(Node root, int key)  {  if (root == null)  return newNode(key);  root = splay(root, key);  if (root.key == key)  return root;  Node node = newNode(key);  if (root.key>chiave) { nodo.destra = radice;  nodo.sinistra = radice.sinistra;  root.sinistra = null;  } else { nodo.sinistra = radice;  nodo.destra = radice.destra;  radice.destra = null;  } nodo restituito;  } static void preOrder(Nodo nodo) { if (nodo != null) { Console.Write(node.key + ' ');  preordine(nodo.sinistra);  preordine(node.right);  } } public static void Main(string[] args) { Node root = null;  radice = inserisci(radice, 100);  radice = inserisci(radice, 50);  radice = inserisci(radice, 200);  radice = inserisci(radice, 40);  radice = inserisci(radice, 60);  Console.WriteLine( 'Preordina l'attraversamento dell'albero Splay modificato:');  preordine(root);  } } // Questo codice è stato fornito dal principe Kumar>

// Javascript code addition  class Node {  constructor(key) {  this.key = key;  this.left = null;  this.right = null;  } } class SplayTree {  static newNode(key) {  const node = new Node(key);  return node;  }  static rightRotate(x) {  const y = x.left;  x.left = y.right;  y.right = x;  return y;  }  static leftRotate(x) {  const y = x.right;  x.right = y.left;  y.left = x;  return y;  }  static splay(root, key) {  if (root == null || root.key == key) {  return root;  }  if (root.key>chiave) { if (root.left == null) { return root;  } if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key);  radice = SplayTree.rightRotate(radice);  } altrimenti se (root.left.key< key) {  root.left.right = SplayTree.splay(root.left.right, key);  if (root.left.right != null) {  root.left = SplayTree.leftRotate(root.left);  }  }  return root.left == null ? root : SplayTree.rightRotate(root);  } else {  if (root.right == null) {  return root;  }  if (root.right.key>chiave) { root.right.left = SplayTree.splay(root.right.left, chiave);  if (root.right.left!= null) { root.right = SplayTree.rightRotate(root.right);  } } altrimenti se (root.right.key< key) {  root.right.right = SplayTree.splay(root.right.right, key);  root = SplayTree.leftRotate(root);  }  return root.right == null ? root : SplayTree.leftRotate(root);  }  }  static insert(root, key) {  if (root == null) {  return SplayTree.newNode(key);  }  root = SplayTree.splay(root, key);  if (root.key == key) {  return root;  }  const node = SplayTree.newNode(key);  if (root.key>chiave) { nodo.destra = radice;  nodo.sinistra = radice.sinistra;  root.sinistra = null;  } else { nodo.sinistra = radice;  nodo.destra = radice.destra;  radice.destra = null;  } nodo restituito;  } static preOrder(nodo) { if (nodo!= null) { console.log(node.key + ' ');  SplayTree.preOrder(node.left);  SplayTree.preOrder(node.right);  } } } lascia root = null; radice = SplayTree.insert(radice, 100); radice = SplayTree.insert(radice, 50); radice = SplayTree.insert(radice, 200); radice = SplayTree.insert(radice, 40); radice = SplayTree.insert(radice, 60); console.log('Preordina l'attraversamento dell'albero Splay modificato:'); SplayTree.preOrder(root); // Il codice è un contributo di Nidhi goel.>

Preorder traversal of the modified Splay tree:>

Svantaggi della struttura dati dell'albero splay:

• Alberi sbilanciati: Gli alberi allargati possono diventare sbilanciati e inefficienti se l'albero viene ruotato ripetutamente nella stessa direzione.
• Utilizzo della memoria: Gli alberi di visualizzazione possono utilizzare molta memoria rispetto ad altre strutture dati perché ogni nodo contiene informazioni aggiuntive.
• Complessità: Gli alberi di splay possono avere una complessità temporale elevata per operazioni di base come l'inserimento e l'eliminazione perché gli alberi devono essere riorganizzati dopo ogni operazione.
• Spese generali di riorganizzazione: L'operazione di divaricazione richiesta in ogni operazione può richiedere molto tempo e comportare costi elevati.
• Casi d'uso limitati : gli alberi di splay non sono adatti a tutte le strutture dati e hanno casi d'uso limitati perché non gestiscono le chiavi duplicate in modo efficiente.

Applicazioni dell'albero strozzato:

• Memorizzazione nella cache : gli alberi di visualizzazione possono essere utilizzati per implementare la gestione della memoria cache, in cui gli elementi a cui si accede più frequentemente vengono spostati nella parte superiore dell'albero per un accesso più rapido.
• Indicizzazione dei database : gli alberi di visualizzazione possono essere utilizzati per indicizzare i database per una ricerca e un recupero dei dati più rapidi.
• Sistemi di file : gli alberi di visualizzazione possono essere utilizzati per archiviare metadati del file system, come la tabella di allocazione, la struttura delle directory e gli attributi dei file.
• Compressione dati: Gli alberi di splay possono essere utilizzati per comprimere i dati identificando e codificando modelli ripetitivi.
• Elaborazione del testo : gli alberi di splay possono essere utilizzati nelle applicazioni di elaborazione del testo, come i correttori ortografici, in cui le parole vengono archiviate in un albero di splay per una ricerca e un recupero rapidi.
• Algoritmi grafici: Gli alberi di splay possono essere utilizzati per implementare algoritmi grafici, come trovare il percorso più breve in un grafico ponderato.
• Il gioco online: Gli alberi di visualizzazione possono essere utilizzati nei giochi online per archiviare e gestire i punteggi più alti, le classifiche e le statistiche dei giocatori.

Certo, ecco alcuni vantaggi e svantaggi degli alberi strombati, nonché alcuni libri consigliati per saperne di più sull'argomento:

Vantaggi degli alberi dilatati:

Gli alberi di splay hanno una complessità temporale ammortizzata di O (log n) per molte operazioni, rendendoli in alcuni casi più veloci di molte altre strutture dati ad albero bilanciate.
Gli alberi di espansione sono autoregolanti, il che significa che si bilanciano automaticamente quando gli elementi vengono inseriti e rimossi. Ciò può aiutare a evitare il degrado delle prestazioni che può verificarsi quando un albero diventa sbilanciato.

arraylist ordinato in Java

Svantaggi degli alberi splay:

Gli alberi di splay possono avere una complessità temporale nel caso peggiore pari a O(n) per alcune operazioni, rendendoli meno prevedibili rispetto ad altre strutture dati ad albero bilanciate come gli alberi AVL o gli alberi rosso-neri.
Gli alberi splay potrebbero non essere adatti per alcune applicazioni in cui sono richieste prestazioni prevedibili.

Libri consigliati su Splay Trees:

Strutture dati e analisi degli algoritmi in Java di Mark Allen Weiss
Introduzione agli algoritmi di Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein
Strutture dati e algoritmi in C++ di Michael T. Goodrich e Roberto Tamassia

Conclusione:

In conclusione, Splay Trees è una struttura dati dinamica ad albero di ricerca binaria autobilanciata che fornisce un modo efficiente di cercare, inserire ed eliminare elementi. Differiscono dai tradizionali alberi di ricerca binari bilanciati come gli alberi AVL e Rosso-Nero, poiché riorganizzano l'albero dopo ogni operazione per riportare alla radice il nodo a cui si è avuto accesso di recente. Ciò aiuta a ridurre l'altezza dell'albero e si traduce in operazioni più veloci. Gli Splay Tree sono altamente flessibili e possono essere adattati a vari casi d'uso. Sebbene possano avere un sovraccarico maggiore in termini di rotazioni, la loro semplicità e versatilità li rendono strumenti utili per risolvere una vasta gamma di problemi.