Splay tree je samonastavljiva binarna podatkovna struktura iskalnega drevesa, kar pomeni, da se drevesna struktura dinamično prilagaja glede na dostopne ali vstavljene elemente. Z drugimi besedami, drevo se samodejno reorganizira, tako da pogosto dostopni ali vstavljeni elementi postanejo bližje korenskemu vozlišču.

1. Drevo splay sta prvič predstavila Daniel Dominic Sleator in Robert Endre Tarjan leta 1985. Ima preprosto in učinkovito izvedbo, ki omogoča izvajanje operacij iskanja, vstavljanja in brisanja v O(log n) amortizirani časovni kompleksnosti, kjer je n število elementov v drevesu.
2. Osnovna ideja, ki stoji za razmaknjenimi drevesi, je pripeljati nazadnje dostopen ali vstavljen element v koren drevesa z izvajanjem zaporedja vrtenja drevesa, imenovanega razprševanje. Razširjanje je proces prestrukturiranja drevesa, tako da se zadnji dostopni ali vstavljeni element spremeni v nov koren in postopoma premakne preostala vozlišča bližje korenu.
3. Splay drevesa so v praksi zelo učinkovita zaradi svoje samonastavljive narave, ki skrajša skupni dostopni čas za pogosto dostopne elemente. Zaradi tega so dobra izbira za aplikacije, ki zahtevajo hitre in dinamične podatkovne strukture, kot so sistemi za predpomnjenje, stiskanje podatkov in algoritmi za omrežno usmerjanje.
4. Vendar pa je glavna pomanjkljivost raztegnjenih dreves ta, da ne zagotavljajo uravnotežene drevesne strukture, kar lahko v najslabšem možnem primeru povzroči poslabšanje zmogljivosti. Prav tako raztegnjena drevesa niso primerna za aplikacije, ki zahtevajo zajamčeno delovanje v najslabšem primeru, kot so sistemi v realnem času ali varnostno kritični sistemi.

Na splošno so raztegnjena drevesa močna in vsestranska podatkovna struktura, ki ponuja hiter in učinkovit dostop do pogosto dostopanih ali vstavljenih elementov. Široko se uporabljajo v različnih aplikacijah in zagotavljajo odličen kompromis med zmogljivostjo in preprostostjo.

Splay drevo je binarno iskalno drevo s samouravnoteženjem, zasnovano za učinkovit dostop do podatkovnih elementov na podlagi njihovih ključnih vrednosti.

• Ključna značilnost razmaknjenega drevesa je, da se ob vsakem dostopu do elementa premakne v koren drevesa, kar ustvari bolj uravnoteženo strukturo za nadaljnje dostope.
• Za nagnjena drevesa je značilna uporaba rotacij, ki so lokalne transformacije drevesa, ki spremenijo njegovo obliko, vendar ohranijo vrstni red elementov.
• Rotacije se uporabljajo za pripeljevanje dostopanega elementa do korena drevesa in tudi za ponovno uravnoteženje drevesa, če postane neuravnoteženo po večkratnih dostopih.

Operacije v splay drevesu:

• Vstavljanje: Če želite v drevo vstaviti nov element, začnite z običajnim vstavljanjem binarnega iskalnega drevesa. Nato uporabite rotacije, da pripeljete novo vstavljeni element do korena drevesa.
• Izbris : Če želite izbrisati element iz drevesa, ga najprej poiščite z iskanjem po binarnem iskalnem drevesu. Če element nima otrok, ga preprosto odstranite. Če ima enega otroka, ga dvignite na njegovo mesto v drevesu. Če ima dva otroka, poiščite naslednika elementa (najmanjši element v njegovem desnem poddrevesu), zamenjajte njegov ključ z elementom, ki ga želite izbrisati, in namesto tega izbrišite naslednika.
• Iskanje : Če želite poiskati element v drevesu, začnite z iskanjem po binarnem iskalnem drevesu. Če je element najden, uporabite rotacije, da ga pripeljete do korena drevesa. Če ni najden, uporabite rotacije za zadnje obiskano vozlišče pri iskanju, ki postane nov koren.
• Rotacija : Rotacije, ki se uporabljajo v raztegnjenem drevesu, so Zig ali Zig-Zig rotacija. Vrtenje Zig se uporablja, da se vozlišče pripelje do korena, medtem ko se vrtenje Zig-Zig uporablja za uravnoteženje drevesa po večkratnih dostopih do elementov v istem poddrevesu.

Tu je razlaga operacij vrtenja po korakih:

• Zig rotacija : Če ima vozlišče pravega podrejenega, izvedite desno rotacijo, da ga pripeljete do korena. Če ima levega otroka, izvedite levo rotacijo.
• Vrtenje cik-cik: Če ima vozlišče vnuka, ki je tudi njegov desni ali levi otrok, izvedite dvojno rotacijo, da uravnotežite drevo. Na primer, če ima vozlišče desnega otroka in ima desni otrok levega otroka, izvedite rotacijo desno-levo. Če ima vozlišče levega podrejenega in levi podrejeni podrejeni podrejeni element, izvedite rotacijo levo-desno.
• Opomba: Posebne podrobnosti izvedbe, vključno z natančnimi uporabljenimi rotacijami, se lahko razlikujejo glede na natančno obliko raztegnjenega drevesa.

Rotacije v Splay Tree

• Zig rotacija
• Zag vrtenje
• Zig – Zig rotacija
• Zag – Vrtenje Zag
• Zig – Zag vrtenje
• Zag – Cik vrtenje

1) Zig rotacija:

Zig rotacija v nagnjenih drevesih deluje na podoben način kot ena rotacija v desno pri rotacijah drevesa AVL. To vrtenje povzroči, da se vozlišča premaknejo za en položaj v desno od svoje trenutne lokacije. Na primer, razmislite o naslednjem scenariju:

Zig rotacija (enojna rotacija)

2) Vrtenje Zag:

Vrtenje Zag v drevesih z nagibom deluje na podoben način kot enojno vrtenje v levo pri vrtenju drevesa AVL. Med tem vrtenjem se vozlišča premaknejo za en položaj v levo od svoje trenutne lokacije. Na primer, razmislite o naslednji ilustraciji:

rimske številke od 1 do 100

Zag vrtenje (enojno levo vrtenje)

3) Cik-cik vrtenje:

Cik-cik rotacija pri nagnjenih drevesih je dvojna cik rotacija. To vrtenje povzroči, da se vozlišča premaknejo za dve poziciji v desno od svoje trenutne lokacije. Za boljše razumevanje si oglejte naslednji primer:

Cik-cik vrtenje (dvojno desno vrtenje)

4) Vrtenje Zag-Zag:

Pri nagnjenih drevesih je Zag-Zag rotacija dvojna zag rotacija. Ta rotacija povzroči, da se vozlišča premaknejo za dve poziciji v levo od trenutne pozicije. Na primer:

izbirna vrsta

Zag-zag vrtenje (dvojno levo vrtenje)

5) Cik-cak vrtenje:

Cik-cak rotacija pri nagnjenih drevesih je kombinacija cik-cak rotacije, ki ji sledi cak rotacija. Zaradi te rotacije se vozlišča premaknejo za en položaj v desno in nato za en položaj v levo s svoje trenutne lokacije. Naslednja ilustracija vizualno prikazuje ta koncept:

Cik-cak vrtenje

6) Vrtenje Zag-Cik:

Zag-cik rotacija pri nagnjenih drevesih je niz zag rotacije, ki ji sledi cik rotacija. Posledica tega je, da se vozlišča premaknejo za en položaj v levo, čemur sledi premik za en položaj v desno s trenutne lokacije. Naslednja ilustracija ponuja vizualno predstavitev tega koncepta:

Zag-cik vrtenje

Spodaj je koda C++ za implementacijo rotacije v drevesu Splay:

int v nizu

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->ključ = ključ;  vozlišče->levo = vozlišče->desno = nullptr;  povratno vozlišče; } Vozlišče* rightRotate(Vozlišče* x) { Vozlišče* y = x->levo;  x->levo = y->desno;  y->desno = x;  vrni y; } Vozlišče* levoZavrti(Vozlišče* x) { Vozlišče* y = x->desno;  x->desno = y->levo;  y->levo = x;  vrni y; } Vozlišče* splay(Node* root, int key) { if (root == nullptr || root->key == key) return root;  if (root->key> key) { if (root->left == nullptr) vrni koren;  if (root->left->key> key) { root->left->left = splay(root->left->left, key);  root = rightRotate(root);  } else if (root->left->key< key) {  root->levo->desno = splay(root->left->desno, tipka);  if (root->left->right != nullptr) root->left = leftRotate(root->left);  } return (root->left == nullptr)? root : rightRotate(root);  } else { if (root->right == nullptr) return root;  if (root->right->key> key) { root->right->left = splay(root->right->left, key);  if (root->right->left != nullptr) root->right = rightRotate(root->right);  } else if (root->desno->key< key) {  root->desno->desno = splay(root->right->desno, tipka);  root = levoRotate(root);  } return (root->right == nullptr)? root : leftRotate(root);  } } Vozlišče* vstavi(Vozlišče* koren, int ključ) { if (root == nullptr) vrni novoVozlišče(ključ);  root = splay(root, key);  if (root->key == key) vrni koren;  Vozlišče* vozlišče = novoVozlišče(ključ);  if (root->key> key) { node->right = root;  vozlišče->levo = koren->levo;  root->left = nullptr;  } else { vozlišče->levo = koren;  vozlišče->desno = koren->desno;  koren->desno = nullptr;  } povratno vozlišče; } void preOrder(Vozlišče* vozlišče) { if (vozlišče != nullptr) { cout<< node->ključ<< ' ';  preOrder(node->levo);  prednaročilo(vozlišče->desno);  } } int main() { Node* root = nullptr;  koren = vstavi (koren, 100);  koren = vstavi(koren, 50);  koren = vstavi(koren, 200);  koren = vstavi (koren, 40);  koren = vstavi (koren, 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>ključ) { if (root.left == null) vrni koren;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  root = rightRotate(root);  } 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>tipka) { root.right.left = splay(root.right.left, key);  if (root.right.left != null) root.right = rightRotate(root.right);  } else if (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>ključ) { node.right = root;  vozlišče.levo = koren.levo;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } povratno vozlišče;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(node.key + ' ');  prednaročilo(vozlišče.levo);  prednaročilo(vozlišče.desno);  } } public static void main(String[] args) { Node root = null;  koren = vstavi (koren, 100);  koren = vstavi(koren, 50);  koren = vstavi(koren, 200);  koren = vstavi (koren, 40);  koren = vstavi (koren, 60);  System.out.println('Prehod prednaročila spremenjenega drevesa Splay:');  preOrder(root);  } } // To kodo je prispeval 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>ključ: če je root.left None: vrni root, če je root.left.key> ključ: 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>ključ: 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>ključ: node.right = root node.left = root.left root.left = None other: node.left = root node.right = root.right root.right = None return node def pre_order(node): if node: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Brez root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Prehod prednaročila spremenjenega drevesa Splay:') 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>ključ) { if (root.left == null) vrni koren;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  root = rightRotate(root);  } 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>tipka) { root.right.left = splay(root.right.left, key);  if (root.right.left != null) root.right = rightRotate(root.right);  } else if (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>ključ) { node.right = root;  vozlišče.levo = koren.levo;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } povratno vozlišče;  } static void preOrder(Node node) { if (node ​​!= null) { Console.Write(node.key + ' ');  prednaročilo(vozlišče.levo);  prednaročilo(vozlišče.desno);  } } public static void Main(string[] args) { Node root = null;  koren = vstavi (koren, 100);  koren = vstavi(koren, 50);  koren = vstavi(koren, 200);  koren = vstavi (koren, 40);  koren = vstavi (koren, 60);  Console.WriteLine( 'Prehod prednaročila spremenjenega drevesa Splay:');  preOrder(root);  } } // To kodo je prispeval princ 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>ključ) { if (root.left == null) { return root;  } if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key);  root = SplayTree.rightRotate(root);  } else if (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>ključ) { root.right.left = SplayTree.splay(root.right.left, key);  if (root.right.left != null) { root.right = SplayTree.rightRotate(root.right);  } } else if (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>ključ) { node.right = root;  vozlišče.levo = koren.levo;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } povratno vozlišče;  } static preOrder(node) { if (node ​​!= null) { console.log(node.key + ' ');  SplayTree.preOrder(node.left);  SplayTree.preOrder(node.right);  } } } let root = null; root = SplayTree.insert(root, 100); root = SplayTree.insert(root, 50); root = SplayTree.insert(root, 200); root = SplayTree.insert(root, 40); root = SplayTree.insert(root, 60); console.log('Prehod po prednaročilu spremenjenega drevesa Splay:'); SplayTree.preOrder(root); // Kodo je prispeval Nidhi goel.>

Preorder traversal of the modified Splay tree:>

Slabosti podatkovne strukture splay drevesa:

• Neuravnotežena drevesa: Nagnjena drevesa lahko postanejo neuravnotežena in neučinkovita, če se drevo večkrat obrača v isto smer.
• Poraba pomnilnika: Splay drevesa lahko porabijo veliko pomnilnika v primerjavi z drugimi podatkovnimi strukturami, ker vsako vozlišče vsebuje dodatne informacije.
• Kompleksnost: Splay drevesa so lahko zelo časovno zapletena za osnovne operacije, kot sta vstavljanje in brisanje, ker je treba drevesa po vsaki operaciji reorganizirati.
• Stroški reorganizacije: Operacija razpenjanja, ki je potrebna pri vsaki operaciji, je lahko dolgotrajna in povzroči visoke režijske stroške.
• Primeri omejene uporabe : Splay drevesa niso primerna za vse podatkovne strukture in imajo omejene primere uporabe, ker ne obravnavajo učinkovito podvojenih ključev.

Uporaba drevesa splay:

• Predpomnjenje : Splay drevesa se lahko uporabljajo za implementacijo upravljanja predpomnilnika, kjer se najpogosteje dostopani elementi premaknejo na vrh drevesa za hitrejši dostop.
• Indeksiranje baze podatkov : Splay drevesa se lahko uporabljajo za indeksiranje baz podatkov za hitrejše iskanje in pridobivanje podatkov.
• Datotečni sistemi : Splay drevesa se lahko uporabljajo za shranjevanje metapodatkov datotečnega sistema, kot so razporeditvena tabela, struktura imenika in atributi datoteke.
• Stiskanje podatkov: Splay drevesa se lahko uporabljajo za stiskanje podatkov z identifikacijo in kodiranjem ponavljajočih se vzorcev.
• Obdelava besedila : Razmaknjena drevesa se lahko uporabljajo v aplikacijah za obdelavo besedila, kot so črkovalniki, kjer so besede shranjene v razmaknjenem drevesu za hitro iskanje in priklic.
• Algoritmi grafov: Splay drevesa se lahko uporabljajo za implementacijo algoritmov grafov, kot je iskanje najkrajše poti v tehtanem grafu.
• Spletno igranje: Splay drevesa se lahko uporabljajo v spletnih igrah za shranjevanje in upravljanje visokih rezultatov, lestvic najboljših in statistik igralcev.

Seveda, tukaj je nekaj prednosti in slabosti nagnjenih dreves ter nekaj priporočenih knjig za več informacij o tej temi:

Prednosti Splay Trees:

Splay drevesa imajo amortizirano časovno kompleksnost O(log n) za številne operacije, zaradi česar so v nekaterih primerih hitrejša od mnogih drugih uravnoteženih drevesnih podatkovnih struktur.
Izbočena drevesa so samonastavljiva, kar pomeni, da se samodejno uravnotežijo med vstavljanjem in odstranjevanjem predmetov. To lahko pomaga preprečiti poslabšanje zmogljivosti, do katerega lahko pride, ko drevo postane neuravnoteženo.

Slabosti Splay Trees:

Splay drevesa imajo lahko v najslabšem primeru časovno kompleksnost O(n) za nekatere operacije, zaradi česar so manj predvidljive kot druge uravnotežene drevesne podatkovne strukture, kot so drevesa AVL ali rdeče-črna drevesa.
Splay drevesa morda niso primerna za nekatere aplikacije, kjer je potrebna predvidljiva zmogljivost.

Priporočene knjige o Splay Trees:

Podatkovne strukture in analiza algoritmov v Javi Mark Allen Weiss
Uvod v algoritme Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest in Clifford Stein
Podatkovne strukture in algoritmi v C++ avtorja Michael T. Goodrich in Roberto Tamassia

Zaključek:

Skratka, drevesa Splay so dinamična binarna podatkovna struktura iskalnega drevesa s samouravnoteženjem, ki zagotavlja učinkovit način iskanja, vstavljanja in brisanja elementov. Razlikujejo se od tradicionalnih uravnoteženih binarnih iskalnih dreves, kot sta AVL in rdeče-črna drevesa, saj reorganizirajo drevo po vsaki operaciji, da pripeljejo nedavno dostopno vozlišče v koren. To pomaga zmanjšati višino drevesa in povzroči hitrejše delovanje. Splay Trees so zelo prilagodljivi in ​​jih je mogoče prilagoditi različnim primerom uporabe. Čeprav imajo morda višje režijske stroške v smislu rotacije, so zaradi svoje preprostosti in vsestranskosti uporabna orodja za reševanje širokega spektra problemov.