logo

TechCodeview

Introducere în structura de date arbore Splay

Arborele Splay este o structură de date a arborelui de căutare binar cu autoajustare, ceea ce înseamnă că structura arborelui este ajustată dinamic pe baza elementelor accesate sau inserate. Cu alte cuvinte, arborele se reorganizează automat astfel încât elementele accesate sau inserate frecvent devin mai aproape de nodul rădăcină.

  1. Arborele splay a fost introdus pentru prima dată de Daniel Dominic Sleator și Robert Endre Tarjan în 1985. Are o implementare simplă și eficientă care îi permite să efectueze operațiuni de căutare, inserare și ștergere în complexitatea timpului amortizat O(log n), unde n este numărul de elemente din arbore.
  2. Ideea de bază din spatele arborilor splay este de a aduce cel mai recent element accesat sau inserat la rădăcina arborelui prin efectuarea unei secvențe de rotații ale arborelui, numită splaying. Splaying-ul este un proces de restructurare a arborelui prin transformarea celui mai recent accesat sau inserat în noua rădăcină și prin mutarea treptată a nodurilor rămase mai aproape de rădăcină.
  3. Arborele Splay sunt foarte eficienți în practică datorită naturii lor auto-ajustabile, care reduce timpul general de acces pentru elementele accesate frecvent. Acest lucru le face o alegere bună pentru aplicațiile care necesită structuri de date rapide și dinamice, cum ar fi sistemele de stocare în cache, compresia datelor și algoritmii de rutare a rețelei.
  4. Cu toate acestea, principalul dezavantaj al arborilor splay este acela că nu garantează o structură de arbore echilibrată, ceea ce poate duce la degradarea performanței în scenariile cele mai nefavorabile. De asemenea, arborii splay nu sunt potriviti pentru aplicații care necesită performanță garantată în cazul cel mai rău, cum ar fi sistemele în timp real sau sistemele critice pentru siguranță.

În general, arborii splay sunt o structură de date puternică și versatilă, care oferă acces rapid și eficient la elementele accesate sau inserate frecvent. Sunt utilizate pe scară largă în diverse aplicații și oferă un compromis excelent între performanță și simplitate.



Un arbore splay este un arbore de căutare binar cu auto-echilibrare, conceput pentru acces eficient la elementele de date pe baza valorilor cheie ale acestora.

  • Caracteristica cheie a unui arbore splay este că de fiecare dată când un element este accesat, acesta este mutat la rădăcina arborelui, creând o structură mai echilibrată pentru accesările ulterioare.
  • Copacii Splay se caracterizează prin utilizarea rotațiilor, care sunt transformări locale ale copacului care își schimbă forma, dar păstrează ordinea elementelor.
  • Rotațiile sunt folosite pentru a aduce elementul accesat la rădăcina arborelui și, de asemenea, pentru a reechilibra arborele dacă acesta devine dezechilibrat după accesări multiple.

Operații într-un arbore splay:

  • Inserare: Pentru a insera un nou element în arbore, începeți prin a efectua o inserare obișnuită a arborelui de căutare binar. Apoi, aplicați rotații pentru a aduce elementul nou introdus la rădăcina copacului.
  • Ștergere : Pentru a șterge un element din arbore, mai întâi localizați-l folosind o căutare binară în arbore. Apoi, dacă elementul nu are copii, pur și simplu eliminați-l. Dacă are un copil, promovați acel copil în poziția sa în copac. Dacă are doi copii, găsiți succesorul elementului (cel mai mic element din subarborele din dreapta), schimbați cheia acestuia cu elementul de șters și ștergeți succesorul.
  • Căutare : Pentru a căuta un element în arbore, începeți prin a efectua o căutare binară în arbore. Dacă elementul este găsit, aplicați rotații pentru a-l aduce la rădăcina copacului. Dacă nu este găsit, aplicați rotații ultimului nod vizitat în căutare, care devine noua rădăcină.
  • Rotație : Rotațiile utilizate într-un arbore splay sunt fie o rotație Zig, fie o rotație Zig-Zig. O rotație Zig este folosită pentru a aduce un nod la rădăcină, în timp ce o rotație Zig-Zig este folosită pentru a echilibra arborele după mai multe accesări la elementele din același subarbor.

Iată o explicație pas cu pas a operațiunilor de rotație:

  • Rotație zig : Dacă un nod are un copil potrivit, efectuați o rotație dreaptă pentru a-l aduce la rădăcină. Dacă are un copil stâng, efectuați o rotație la stânga.
  • Rotație zig-zig: Dacă un nod are un nepot care este și copilul drept sau stâng al copilului său, efectuați o rotație dublă pentru a echilibra arborele. De exemplu, dacă nodul are un copil drept și copilul drept are un copil stâng, efectuați o rotație dreapta-stânga. Dacă nodul are un copil stâng și copilul stâng are un copil drept, efectuați o rotație stânga-dreapta.
  • Notă: Detaliile specifice de implementare, inclusiv rotațiile exacte utilizate, pot varia în funcție de forma exactă a arborelui splay.

Rotații în Splay Tree

  • Rotație zig
  • Rotație Zag
  • Zig – Zig Rotație
  • Zag – Rotație Zag
  • Rotație Zig – Zag
  • Zag – rotație în zig

1) Rotație zig:

Rotația Zig în arbori splay funcționează într-un mod similar cu rotația unică la dreapta în rotațiile arborelui AVL. Această rotație duce la mutarea nodurilor cu o poziție la dreapta față de locația lor curentă. De exemplu, luați în considerare următorul scenariu:

Rotire în zig (o singură rotație)



2) Rotație Zag:

Rotația Zag în arbori splay funcționează într-un mod similar cu rotația unică la stânga în rotațiile arborelui AVL. În timpul acestei rotații, nodurile își schimbă o poziție la stânga față de locația lor curentă. De exemplu, luați în considerare următoarea ilustrație:

lista de inițializare python

Rotire Zag (Rotire unică la stânga)

3) Rotație zig-zig:

Rotația Zig-Zig în arbori splay este o rotație dublă în zig. Această rotație are ca rezultat deplasarea nodurilor cu două poziții la dreapta față de locația lor curentă. Aruncă o privire la următorul exemplu pentru o mai bună înțelegere:



Rotație zig-zig (rotire dublă la dreapta)

4) Rotație Zag-Zag:

În arbori splay, rotația Zag-Zag este o rotație dublă zag. Această rotație face ca nodurile să se miște două poziții la stânga față de poziția lor actuală. De exemplu:

Rotație Zag-Zag (rotire dublă la stânga)

5) Rotație în zig-zag:

Rotația în zig-zag în arbori splay este o combinație a unei rotații în zig urmată de o rotație în zag. Ca urmare a acestei rotații, nodurile își schimbă o poziție la dreapta și apoi o poziție la stânga față de locația lor curentă. Următoarea ilustrație oferă o reprezentare vizuală a acestui concept:

convertor șir în int

Rotație în zig-zag


6) Rotație Zag-Zig:

Rotația Zag-Zig în arbori splay este o serie de rotații în zag urmate de o rotație în zig. Acest lucru duce la mutarea nodurilor cu o poziție la stânga, urmată de o schimbare cu o poziție la dreapta față de locația lor curentă. Următoarea ilustrație oferă o reprezentare vizuală a acestui concept:

Rotație Zag-Zig

„abc” este în cifre”

Mai jos este codul C++ pentru implementarea rotațiilor în arborele Splay:

C++ 
#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->cheie = cheie;  nod->left = nod->right = nullptr;  nodul de întoarcere; } Nod* rightRotate(Nod* x) { Nod* y = x->stânga;  x->stânga = y->dreapta;  y->dreapta = x;  returnează y; } Nodul* stângaRotire(Nodul* x) { Nodul* y = x->dreapta;  x->dreapta = y->stânga;  y->stânga = x;  returnează y; } Nod* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root;  if (root->key> key) { if (root->left == nullptr) return root;  if (rădăcină->stânga->key> cheie) { root->left->left = splay(root->left->left, key);  rădăcină = dreaptaRotate(rădăcină);  } else if (rădăcină->stânga->cheie< key) {  root->stânga->dreapta = splay(rădăcină->stânga->dreapta, cheie);  if (rădăcină->stânga->dreapta != nullptr) rădăcină->stânga = stângaRotire(rădăcină->stânga);  } return (rădăcină->stânga == nullptr) ? rădăcină: dreaptaRotate(rădăcină);  } else { if (rădăcină->dreapta == nullptr) returnează rădăcină;  if (root->right->key> key) { root->right->left = splay(root->right->left, key);  if (rădăcină->dreapta->stânga != nullptr) rădăcină->dreapta = dreaptaRotire(rădăcină->dreapta);  } else if (rădăcină->dreapta->cheie< key) {  root->dreapta->dreapta = splay(rădăcină->dreapta->dreapta, cheie);  rădăcină = stângaRotire(rădăcină);  } return (rădăcină->dreapta == nullptr) ? rădăcină: stângaRotire(rădăcină);  } } Nod* insert(Nod* root, int key) { if (root == nullptr) return newNode(cheie);  root = splay(rădăcină, cheie);  if (rădăcină->cheie == cheie) returnează rădăcină;  Nod* nod = nouNod(cheie);  if (root->key> key) { nod->right = root;  nod->stânga = rădăcină->stânga;  root->left = nullptr;  } else { nod->stânga = rădăcină;  nod->dreapta = rădăcină->dreapta;  root->right = nullptr;  } return nod; } void preOrder(Nod* node) { if (nod != nullptr) { cout<< node->cheie<< ' ';  preOrder(node->stânga);  precomanda(nodul->dreapta);  } } int main() { Nod* root = nullptr;  rădăcină = insert (rădăcină, 100);  rădăcină = insert (rădăcină, 50);  rădăcină = insert (rădăcină, 200);  rădăcină = insert(rădăcină, 40);  rădăcină = insert(rădăcină, 60);  cout<< 'Preorder traversal of the modified Splay tree:' << endl;  preOrder(root);  return 0; }>
Java 
// 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>cheie) { if (root.left == null) returnează rădăcină;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  rădăcină = dreaptaRotate(rădăcină);  } else if (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>cheie) { root.right.left = splay(root.right.left, key);  if (root.right.left != null) root.right = rightRotate(root.right);  } altfel dacă (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>cheie) { node.right = root;  node.left = root.left;  root.left = nul;  } else { node.left = root;  node.right = root.right;  root.right = nul;  } return nod;  } static void preOrder(Nod node) { if (nod != null) { System.out.println();  System.out.print(node.key + ' ');  precomanda(nod.stânga);  precomanda(nod.dreapta);  } } public static void main(String[] args) { Nod root = null;  root = insert (rădăcină, 100);  rădăcină = insert (rădăcină, 50);  rădăcină = insert (rădăcină, 200);  rădăcină = insert(rădăcină, 40);  rădăcină = insert (rădăcină, 60);  System.out.println('Parcurgere precomanda a arborelui Splay modificat:');  precomandă(rădăcină);  } } // Acest cod este contribuit de princekumaras>
Python3 
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>cheie: dacă root.left este None: returnează rădăcină dacă root.left.key> cheie: 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>cheie: 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>cheie: node.right = rădăcină node.left = root.left root.left = Nimic altceva: node.left = rădăcină node.right = root.right root.right = Nici unul returnează nod def pre_order(nod): if node: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = None root = insert(root, 100) root = insert(root) , 50) rădăcină = inserare (rădăcină, 200) rădăcină = inserare (rădăcină, 40) rădăcină = inserare (rădăcină, 60) print('Precomandă parcurgerea arborelui Splay modificat:') pre_order(rădăcină)>
C# 
// 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>cheie) { if (root.left == null) returnează rădăcină;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  rădăcină = dreaptaRotate(rădăcină);  } else if (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>cheie) { root.right.left = splay(root.right.left, key);  if (root.right.left != null) root.right = rightRotate(root.right);  } altfel dacă (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>cheie) { node.right = root;  node.left = root.left;  root.left = nul;  } else { node.left = root;  node.right = root.right;  root.right = nul;  } return nod;  } static void preOrder(Nod node) { if (nod != null) { Console.Write(node.key + ' ');  precomanda(nod.stânga);  precomanda(nod.dreapta);  } } public static void Main(string[] args) { Node root = null;  root = insert (rădăcină, 100);  rădăcină = insert (rădăcină, 50);  rădăcină = insert (rădăcină, 200);  rădăcină = insert(rădăcină, 40);  rădăcină = insert (rădăcină, 60);  Console.WriteLine('Parcurgere precomanda a arborelui Splay modificat:');  precomandă(rădăcină);  } } // Acest cod este contribuit de prințul Kumar>>Javascript>>  
  Ieșire      Copaci dezechilibrati:    Copacii Splay pot deveni dezechilibrati și ineficienți dacă arborele este rotit în mod repetat în aceeași direcție.
  •     Folosirea memoriei:    Arborii Splay pot folosi multă memorie în comparație cu alte structuri de date, deoarece fiecare nod conține informații suplimentare.
  •     Complexitate:    Arborii Splay pot avea o complexitate mare de timp pentru operațiuni de bază, cum ar fi inserarea și ștergerea, deoarece arborii trebuie reorganizați după fiecare operațiune.
  •     Cheltuieli generale de reorganizare:    Operația de împrăștiere necesară în fiecare operațiune poate consuma mult timp și poate duce la o supraîncărcare mare.
  •     Cazuri de utilizare limitată    : arborii Splay nu sunt potriviti pentru toate structurile de date și au cazuri de utilizare limitate, deoarece nu gestionează eficient cheile duplicate.
    • Aplicații ale arborelui splay:
    •     Memorarea în cache    : Arborele Splay pot fi folosiți pentru a implementa gestionarea memoriei cache, unde elementele accesate cel mai frecvent sunt mutate în partea de sus a arborelui pentru un acces mai rapid.
    •     Indexarea bazei de date    : arborii Splay pot fi utilizați pentru a indexa bazele de date pentru o căutare mai rapidă și o recuperare a datelor.
    •     Sisteme de fișiere    : Arborele Splay pot fi utilizați pentru a stoca metadatele sistemului de fișiere, cum ar fi tabelul de alocare, structura directoarelor și atributele fișierului.
    •     Comprimarea datelor:    Arborele Splay pot fi utilizați pentru a comprima datele prin identificarea și codificarea modelelor repetate.
    •     Procesarea textului    : Arborele Splay pot fi utilizați în aplicațiile de procesare a textului, cum ar fi verificatoarele ortografice, unde cuvintele sunt stocate într-un arbore Splay pentru căutare și regăsire rapidă.
    •     Algoritmi grafici:    Arborii Splay pot fi utilizați pentru a implementa algoritmi de grafic, cum ar fi găsirea celei mai scurte căi într-un grafic ponderat.
    •     Jocuri online:    Arborele Splay pot fi folosiți în jocurile online pentru a stoca și gestiona scorurile mari, clasamentele și statisticile jucătorilor.
    Sigur, iată câteva avantaje și dezavantaje ale arborilor splay, precum și câteva cărți recomandate pentru a afla mai multe despre acest subiect:
     
    Avantajele arborilor Splay:
    Arborii Splay au o complexitate de timp amortizată de O(log n) pentru multe operațiuni, făcându-le mai rapide decât multe alte structuri de date arbore echilibrate în unele cazuri.  
    Arborele Splay se auto-ajustează, ceea ce înseamnă că se echilibrează automat pe măsură ce articolele sunt introduse și îndepărtate. Acest lucru poate ajuta la evitarea degradarii performanței care poate apărea atunci când un copac devine dezechilibrat.
     
    Dezavantajele arborilor Splay:
    Arborii Splay pot avea o complexitate de timp în cel mai rău caz de O(n) pentru unele operațiuni, făcându-le mai puțin previzibile decât alte structuri de date arbore echilibrate, cum ar fi arborii AVL sau arborii roșu-negru.  
    Arborele Splay poate să nu fie potrivit pentru anumite aplicații în care este necesară o performanță previzibilă.
     
    Cărți recomandate despre Splay Trees:
    Structuri de date și analiza algoritmilor în Java de Mark Allen Weiss  
    Introducere în algoritmi de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest și Clifford Stein  
    Structuri de date și algoritmi în C++ de Michael T. Goodrich și Roberto Tamassia
     
    Concluzie:
    În concluzie, Splay Trees sunt o structură de date dinamică a arborelui de căutare binar cu auto-echilibrare care oferă o modalitate eficientă de căutare, inserare și ștergere a elementelor. Ele diferă de arborii de căutare binari echilibrați tradiționali, cum ar fi arborii AVL și roșu-negru, deoarece reorganizează arborele după fiecare operațiune pentru a aduce nodul recent accesat la rădăcină. Acest lucru ajută la reducerea înălțimii copacului și are ca rezultat operațiuni mai rapide. Splay Trees sunt foarte flexibili și pot fi adaptați la diferite cazuri de utilizare. Deși pot avea o suprasolicitare mai mare în ceea ce privește rotațiile, simplitatea și versatilitatea lor le fac instrumente utile pentru rezolvarea unei game largi de probleme.