logo

TechCodeview

Úvod do stromovej dátovej štruktúry Splay

Splay tree je samonastaviteľná binárna dátová stromová štruktúra vyhľadávania, čo znamená, že stromová štruktúra sa dynamicky upravuje na základe sprístupnených alebo vložených prvkov. Inými slovami, strom sa automaticky reorganizuje tak, aby sa často prístupné alebo vkladané prvky priblížili ku koreňovému uzlu.

  1. Splay strom prvýkrát predstavili Daniel Dominic Sleator a Robert Endre Tarjan v roku 1985. Má jednoduchú a efektívnu implementáciu, ktorá mu umožňuje vykonávať operácie vyhľadávania, vkladania a vymazávania v časovej zložitosti O(log n), kde n je počet prvkov v strome.
  2. Základnou myšlienkou roztiahnutých stromov je priviesť naposledy sprístupnený alebo vložený prvok do koreňa stromu vykonaním sekvencie rotácie stromu, ktorá sa nazýva roztiahnutie. Rozloženie je proces reštrukturalizácie stromu tak, že sa z naposledy sprístupneného alebo vloženého prvku stane nový koreň a postupne sa zostávajúce uzly približujú ku koreňu.
  3. Rozvetvené stromy sú v praxi vysoko efektívne vďaka ich samoregulačnému charakteru, čo znižuje celkový čas prístupu pre často prístupné prvky. Vďaka tomu sú dobrou voľbou pre aplikácie, ktoré vyžadujú rýchle a dynamické dátové štruktúry, ako sú systémy ukladania do vyrovnávacej pamäte, kompresia údajov a algoritmy sieťového smerovania.
  4. Hlavnou nevýhodou rozvetvených stromov je však to, že nezaručujú vyváženú stromovú štruktúru, čo môže v najhorších prípadoch viesť k zníženiu výkonu. Rozšírené stromy tiež nie sú vhodné pre aplikácie, ktoré vyžadujú garantovaný výkon v najhoršom prípade, ako sú systémy v reálnom čase alebo systémy kritické z hľadiska bezpečnosti.

Celkovo sú splay stromy výkonnou a všestrannou dátovou štruktúrou, ktorá ponúka rýchly a efektívny prístup k často používaným alebo vkladaným prvkom. Sú široko používané v rôznych aplikáciách a poskytujú vynikajúci kompromis medzi výkonom a jednoduchosťou.



Rozšírený strom je samovyvažujúci binárny vyhľadávací strom navrhnutý pre efektívny prístup k dátovým prvkom na základe ich kľúčových hodnôt.

  • Kľúčovou vlastnosťou rozvetveného stromu je, že pri každom prístupe k prvku sa prvok presunie do koreňa stromu, čím sa vytvorí vyváženejšia štruktúra pre následné prístupy.
  • Rozvetvené stromy sú charakteristické používaním rotácií, čo sú lokálne transformácie stromu, ktoré menia jeho tvar, ale zachovávajú poradie prvkov.
  • Rotácie sa používajú na privedenie prvku ku koreňu stromu a tiež na opätovné vyváženie stromu, ak sa po viacerých prístupoch stane nevyváženým.

Operácie v strome zobrazenia:

  • Vloženie: Ak chcete do stromu vložiť nový prvok, začnite vykonaním bežného vkladania binárneho vyhľadávacieho stromu. Potom použite rotácie, aby sa novo vložený prvok dostal ku koreňu stromu.
  • Vymazanie : Ak chcete odstrániť prvok zo stromu, najprv ho nájdite pomocou binárneho vyhľadávania v strome. Potom, ak prvok nemá žiadne deti, jednoducho ho odstráňte. Ak má jedno dieťa, povýšte ho na jeho pozíciu v strome. Ak má dve deti, nájdite následníka prvku (najmenší prvok v jeho pravom podstrome), vymeňte jeho kľúč za prvok, ktorý sa má odstrániť, a namiesto toho vymažte následníka.
  • Vyhľadávanie : Ak chcete vyhľadať prvok v strome, začnite vykonaním vyhľadávania v binárnom strome vyhľadávania. Ak sa prvok nájde, použite rotácie, aby ste ho priviedli ku koreňu stromu. Ak sa nenájde, použite rotácie na posledný navštívený uzol vo vyhľadávaní, ktorý sa stane novým koreňom.
  • Rotácia : Rotácie používané v roztiahnutom strome sú buď Zig alebo Zig-Zig rotácia. Zig rotácia sa používa na privedenie uzla ku koreňu, zatiaľ čo rotácia Zig-Zig sa používa na vyváženie stromu po viacerých prístupoch k prvkom v rovnakom podstrome.

Tu je podrobné vysvetlenie operácií rotácie:

  • Zig rotácia : Ak má uzol pravé dieťa, vykonajte rotáciu doprava, aby ste ho dostali ku koreňu. Ak má dieťa vľavo, vykonajte rotáciu doľava.
  • Rotácia cik-cik: Ak má uzol vnúča, ktorý je zároveň pravým alebo ľavým dieťaťom jeho dieťaťa, vykonajte dvojitú rotáciu, aby ste strom vyvážili. Napríklad, ak má uzol pravé dieťa a pravé dieťa má ľavé dieťa, vykonajte rotáciu sprava doľava. Ak má uzol ľavé dieťa a ľavé dieťa pravé dieťa, vykonajte rotáciu zľava doprava.
  • Poznámka: Špecifické detaily implementácie, vrátane presných použitých rotácií, sa môžu líšiť v závislosti od presnej formy rozloženia stromu.

Rotácie v Splay Tree

  • Zig rotácia
  • Rotácia Zag
  • Zig – Zig Rotácia
  • Zag – Zag Rotácia
  • Zig – Zag rotácia
  • Zag – Zig Rotation

1) Zig Rotácia:

Zig rotácia v roztiahnutých stromoch funguje podobným spôsobom ako jedna doprava v rotáciách AVL Tree. Táto rotácia vedie k tomu, že uzly sa posunú o jednu pozíciu doprava z ich aktuálnej polohy. Zvážte napríklad nasledujúci scenár:

Zig Rotation (Jednoduché otočenie)



2) Rotácia zag:

Rotácia Zag v roztiahnutých stromoch funguje podobným spôsobom ako jedna rotácia vľavo pri rotáciách stromu AVL. Počas tejto rotácie sa uzly posunú o jednu pozíciu doľava zo svojej aktuálnej polohy. Zvážte napríklad nasledujúci obrázok:

rímske čísla 1 až 100

Rotácia zag (jedno otočenie doľava)

3) Cik-cik rotácia:

Rotácia cik-cik v rozvetvených stromoch je dvojitá cik rotácia. Toto otočenie má za následok posunutie uzlov o dve pozície doprava z ich aktuálnej polohy. Pre lepšie pochopenie si pozrite nasledujúci príklad:



Cik-cik rotácia (Dvojité otočenie doprava)

4) Rotácia zag-zag:

V rozvetvených stromoch je rotácia zag-zag dvojitá rotácia zag. Táto rotácia spôsobí, že sa uzly posunú o dve pozície doľava zo svojej súčasnej polohy. Napríklad:

Rotácia zag-zag (dvojité otočenie doľava)

5) Cik-cak rotácia:

Cik-cak rotácia v roztiahnutých stromoch je kombináciou cik-cak rotácie nasledovanej zag rotáciou. V dôsledku tejto rotácie sa uzly posunú o jednu pozíciu doprava a potom o jednu pozíciu doľava zo svojej aktuálnej polohy. Nasledujúca ilustrácia poskytuje vizuálnu reprezentáciu tohto konceptu:

Cik-cak rotácia

kedy bola vynájdená škola


6) Rotácia Zag-Zig:

Rotácia zag-cik v roztiahnutých stromoch je séria zag rotácií, po ktorých nasleduje kľukatá rotácia. Výsledkom je, že uzly sa posunú o jednu pozíciu doľava, po čom nasleduje posun o jednu pozíciu doprava z ich aktuálnej polohy. Nasledujúca ilustrácia ponúka vizuálne znázornenie tohto konceptu:

Rotácia Zag-Zig

Nižšie je uvedený kód C++ na implementáciu rotácií v strome Splay:

C++ 
#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->kľúč = kľúč;  uzol->vľavo = uzol->vpravo = nullptr;  návratový uzol; } Uzol* vpravoRotate(Uzol* x) { Uzol* y = x->vľavo;  x->vľavo = y->vpravo;  y->vpravo = x;  vrátiť y; } Uzol* doľavaRotate(Uzol* x) { Uzol* y = x->vpravo;  x->vpravo = y->vľavo;  y->vľavo = x;  vrátiť 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 (root->left->key> key) { root->left->left = splay(root->left->left, key);  root = rightRotate(root);  } else if (koreň->doľava->kláves< key) {  root->vľavo->vpravo = roztiahnutie(koreň->vľavo->vpravo, kľúč);  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 (koreň->vpravo->kláves< key) {  root->right->right = splay(root->right->right, key);  root = leftRotate(root);  } return (root->right == nullptr) ? root : leftRotate(root);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  root = splay(koreň, kľúč);  if (root->key == key) return root;  Uzol* uzol = novyUzol(kľúč);  if (root->key> key) { node->right = root;  uzol->left = root->left;  root->left = nullptr;  } else { node->left = root;  uzol->vpravo = root->vpravo;  root->right = nullptr;  } návratový uzol; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->kľúč<< ' ';  preOrder(node->vľavo);  preOrder(node->right);  } } int main() { Uzol* root = nullptr;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 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>key) { if (root.left == null) return root;  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>kľúč) { 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>kľúč) { node.right = root;  node.left = root.left;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } návratový uzol;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(uzol.kľúč + ' ');  preOrder(uzol.left);  preOrder(node.right);  } } public static void main(String[] argumenty) { Koreň uzla = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  System.out.println('Prechod predobjednávky upraveného stromu Splay:');  preOrder(root);  } } // Tento kód prispel 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>kľúč: ak root.left je None: vráti root, ak root.left.key> key: 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>kľúč: 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>kľúč: node.right = root node.left = root.left root.left = Žiadny iný: node.left = root node.right = root.right root.right = Žiadny návratový uzol def pre_order(node): if node: print (node.key, end=' ') pre_order(uzol.left) pre_order(node.right) if __name__ == '__main__': root = None root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Prechod predobjednávky upraveného stromu Splay:') pre_order(root)>
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>key) { if (root.left == null) return root;  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>kľúč) { 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>kľúč) { node.right = root;  node.left = root.left;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } návratový uzol;  } static void preOrder(Node node) { if (node ​​!= null) { Console.Write(node.key + ' ');  preOrder(uzol.left);  preOrder(node.right);  } } public static void Main(string[] args) { Koreň uzla = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  Console.WriteLine( 'Prechod predobjednávky upraveného stromu Splay:');  preOrder(root);  } } // Tento kód prispel princom Kumarom>
Javascript 
// 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>key) { 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>kľúč) { 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>kľúč) { node.right = root;  node.left = root.left;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } návratový uzol;  } static preOrder(uzol) { if (uzol != null) { console.log(uzol.key + ' ');  SplayTree.preOrder(node.left);  SplayTree.preOrder(node.right);  } } } nech 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('Prechod predobjednávky upraveného stromu Splay:'); SplayTree.preOrder(root); // Kód prispel Nidhi goel.>
Výkon 
Preorder traversal of the modified Splay tree:>

Nevýhody dátovej štruktúry splay tree:

  • Nevyvážené stromy: Rozvetvené stromy sa môžu stať nevyváženými a neefektívnymi, ak sa strom opakovane otáča rovnakým smerom.
  • Využitie pamäte: Splay stromy môžu v porovnaní s inými dátovými štruktúrami využívať veľa pamäte, pretože každý uzol obsahuje ďalšie informácie.
  • zložitosť: Rozvetvené stromy môžu byť časovo náročné na základné operácie, ako je vkladanie a vymazávanie, pretože stromy je potrebné po každej operácii reorganizovať.
  • Režijné náklady na reorganizáciu: Operácia rozprestierania potrebná pri každej operácii môže byť časovo náročná a viesť k vysokej réžii.
  • Obmedzené prípady použitia : Splay stromy nie sú vhodné pre všetky dátové štruktúry a majú obmedzené prípady použitia, pretože efektívne nespracúvajú duplicitné kľúče.

Aplikácie rozvetveného stromu:

  • Ukladanie do vyrovnávacej pamäte : Stromy Splay možno použiť na implementáciu správy vyrovnávacej pamäte, kde sa najčastejšie používané položky presunú do hornej časti stromu pre rýchlejší prístup.
  • Indexovanie databázy : Splay stromy možno použiť na indexovanie databáz pre rýchlejšie vyhľadávanie a získavanie údajov.
  • Súborové systémy : Splay stromy možno použiť na ukladanie metadát súborového systému, ako je napríklad alokačná tabuľka, štruktúra adresára a atribúty súboru.
  • Kompresia údajov: Splay stromy možno použiť na kompresiu údajov identifikáciou a kódovaním opakujúcich sa vzorov.
  • Spracovanie textu : Stromy rozloženia možno použiť v aplikáciách na spracovanie textu, ako je kontrola pravopisu, kde sú slová uložené v strome rozloženia na rýchle vyhľadávanie a načítanie.
  • Algoritmy grafov: Rozšírené stromy možno použiť na implementáciu grafových algoritmov, ako je hľadanie najkratšej cesty vo váženom grafe.
  • Online hranie: Splay stromy možno použiť v online hrách na ukladanie a správu najvyšších skóre, rebríčkov a štatistík hráčov.

Iste, tu sú niektoré výhody a nevýhody rozvetvených stromov, ako aj niekoľko odporúčaných kníh, kde sa dozviete viac o tejto téme:

Výhody rozvetvených stromov:

Rozšírené stromy majú amortizovanú časovú zložitosť O(log n) pre mnohé operácie, vďaka čomu sú v niektorých prípadoch rýchlejšie ako mnohé iné vyvážené stromové dátové štruktúry.
Rozvetvené stromy sú samonastaviteľné, čo znamená, že sa automaticky vyrovnávajú pri vkladaní a vyberaní položiek. To môže pomôcť vyhnúť sa zníženiu výkonu, ku ktorému môže dôjsť, keď sa strom stane nevyváženým.

koľko týždňov má mesiac

Nevýhody rozvetvených stromov:

Rozšírené stromy môžu mať v najhoršom prípade časovú zložitosť O(n) pre niektoré operácie, vďaka čomu sú menej predvídateľné ako iné vyvážené stromové dátové štruktúry, ako sú AVL stromy alebo červeno-čierne stromy.
Rozvetvené stromy nemusia byť vhodné pre určité aplikácie, kde sa vyžaduje predvídateľný výkon.

Odporúčané knihy o Splay Trees:

Dátové štruktúry a analýza algoritmov v Jave od Marka Allena Weissa
Úvod do algoritmov od Thomasa H. Cormena, Charlesa E. Leisersona, Ronalda L. Rivesta a Clifforda Steina
Dátové štruktúry a algoritmy v C++ od Michaela T. Goodricha a Roberta Tamassiu

záver:

Na záver, Splay Trees sú dynamická, samovyvažujúca sa binárna dátová stromová štruktúra vyhľadávania, ktorá poskytuje efektívny spôsob vyhľadávania, vkladania a odstraňovania prvkov. Líšia sa od tradičných vyvážených binárnych vyhľadávacích stromov, ako sú AVL a Red-Black stromy, pretože reorganizujú strom po každej operácii, aby priviedli nedávno sprístupnený uzol do koreňa. To pomáha znížiť výšku stromu a má za následok rýchlejšie operácie. Splay Trees sú vysoko flexibilné a dajú sa prispôsobiť rôznym prípadom použitia. Aj keď môžu mať vyššiu réžiu z hľadiska rotácií, ich jednoduchosť a všestrannosť z nich robí užitočné nástroje na riešenie širokého spektra problémov.