logo

TechCodeview

Úvod do stromové datové struktury Splay

Splay tree je samonastavitelná binární vyhledávací stromová datová struktura, což znamená, že stromová struktura je upravována dynamicky na základě přístupných nebo vložených prvků. Jinými slovy, strom se automaticky reorganizuje tak, aby se často používané nebo vkládané prvky přiblížily kořenovému uzlu.

  1. Splay strom byl poprvé představen Danielem Dominicem Sleatorem a Robertem Endre Tarjanem v roce 1985. Má jednoduchou a efektivní implementaci, která mu umožňuje provádět operace vyhledávání, vkládání a mazání v amortizované časové složitosti O(log n), kde n je počet prvků ve stromu.
  2. Základní myšlenkou rozvětvených stromů je přivést naposledy zpřístupněný nebo vložený prvek do kořene stromu provedením sekvence rotací stromu, nazývané splaying. Rozprostření je proces restrukturalizace stromu tak, že se z naposledy zpřístupněného nebo vloženého prvku stane nový kořen a zbývající uzly se postupně přesunou blíže ke kořenu.
  3. Rozvětvené stromy jsou v praxi vysoce efektivní díky své samonastavovací povaze, což snižuje celkovou přístupovou dobu pro často přístupné prvky. Díky tomu jsou dobrou volbou pro aplikace, které vyžadují rychlé a dynamické datové struktury, jako jsou systémy ukládání do mezipaměti, komprese dat a algoritmy síťového směrování.
  4. Hlavní nevýhodou rozvětvených stromů je však to, že nezaručují vyváženou stromovou strukturu, což může v nejhorších scénářích vést ke snížení výkonu. Rozvětvené stromy také nejsou vhodné pro aplikace, které vyžadují zaručený výkon v nejhorším případě, jako jsou systémy v reálném čase nebo systémy kritické z hlediska bezpečnosti.

Celkově jsou splay stromy výkonnou a všestrannou datovou strukturou, která nabízí rychlý a efektivní přístup k často používaným nebo vkládaným prvkům. Jsou široce používány v různých aplikacích a poskytují vynikající kompromis mezi výkonem a jednoduchostí.



Splay tree je samovyvažující binární vyhledávací strom navržený pro efektivní přístup k datovým prvkům na základě jejich klíčových hodnot.

  • Klíčovou vlastností splay stromu je, že pokaždé, když je prvek zpřístupněn, je přesunut do kořene stromu, čímž se vytváří vyváženější struktura pro následné přístupy.
  • Rozvětvené stromy jsou charakteristické tím, že používají rotace, což jsou místní transformace stromu, které mění jeho tvar, ale zachovávají pořadí prvků.
  • Rotace se používají k přenesení přístupného prvku do kořene stromu a také k obnovení rovnováhy stromu, pokud se po vícenásobných přístupech stane nevyváženým.

Operace ve stromě zobrazení:

  • Vložení: Chcete-li do stromu vložit nový prvek, začněte běžným vkládáním binárního vyhledávacího stromu. Poté použijte rotace, aby se nově vložený prvek dostal do kořene stromu.
  • Vymazání : Chcete-li odstranit prvek ze stromu, nejprve jej vyhledejte pomocí binárního vyhledávání ve stromu. Pak, pokud prvek nemá žádné potomky, jednoduše jej odstraňte. Pokud má jedno dítě, povyšte ho na jeho pozici ve stromu. Pokud má dva potomky, najděte následníka prvku (nejmenší prvek v jeho pravém podstromu), prohoďte jeho klíč s prvkem, který má být odstraněn, a místo toho smažte následníka.
  • Vyhledávání : Chcete-li vyhledat prvek ve stromu, začněte prohledáváním binárního vyhledávacího stromu. Pokud je prvek nalezen, použijte rotace, abyste jej přenesli do kořene stromu. Pokud není nalezen, použijte rotace na poslední uzel navštívený ve vyhledávání, který se stane novým kořenem.
  • Otáčení : Rotace používané ve stromě zobrazení jsou buď Zig nebo Zig-Zig rotace. Rotace Zig se používá k přivedení uzlu ke kořenu, zatímco rotace Zig-Zig se používá k vyvážení stromu po více přístupech k prvkům ve stejném podstromu.

Zde je podrobné vysvětlení operací rotace:

  • Zig Rotace : Pokud má uzel pravého potomka, proveďte rotaci doprava, abyste jej přivedli ke kořenu. Pokud má dítě vlevo, proveďte rotaci vlevo.
  • Rotace cik-cik: Pokud má uzel vnouče, které je zároveň pravým nebo levým potomkem jeho potomka, proveďte dvojitou rotaci, abyste strom vyvážili. Pokud má například uzel pravého potomka a pravý potomek levého potomka, proveďte rotaci zprava doleva. Pokud má uzel levé dítě a levé dítě pravé dítě, proveďte rotaci zleva doprava.
  • Poznámka: Konkrétní detaily implementace, včetně přesných použitých rotací, se mohou lišit v závislosti na přesné podobě rozvětveného stromu.

Rotace v Splay Tree

  • Zig Rotace
  • Zag Rotace
  • Zig – Zig Rotace
  • Zag – Zag Rotace
  • Rotace cik – cak
  • Zag – Zig Rotation

1) Zig Rotace:

Zig Rotation v rozvětvených stromech funguje podobným způsobem jako jedno otočení doprava u rotací AVL Tree. Toto otočení má za následek posunutí uzlů o jednu pozici doprava z jejich aktuálního umístění. Zvažte například následující scénář:

Zig Rotation (Jednoduché otočení)



2) Rotace zag:

Rotace Zag v rozvětvených stromech funguje podobným způsobem jako jednoduchá rotace doleva u rotací stromu AVL. Během této rotace se uzly posunou o jednu pozici doleva ze svého aktuálního umístění. Zvažte například následující obrázek:

celé číslo na řetězec

Zag Rotace (Jedno levé otočení)

3) Rotace cik-cik:

Rotace cik-cik v rozvětvených stromech je dvojitá cik rotace. Toto otočení má za následek posunutí uzlů o dvě pozice doprava z jejich aktuálního umístění. Pro lepší pochopení se podívejte na následující příklad:



Rotace cik-cik (dvojité otočení doprava)

4) Rotace zag-zag:

V rozvětvených stromech je rotace zag-zag dvojitá rotace zag. Tato rotace způsobí, že se uzly posunou o dvě pozice doleva ze své současné pozice. Například:

Rotace zag-zag (dvojité otočení doleva)

5) Cik-cak rotace:

Cik-cak rotace v rozvětvených stromech je kombinací cik rotace následované cak rotací. V důsledku této rotace se uzly posunou o jednu pozici doprava a poté o jednu pozici doleva ze svého aktuálního umístění. Následující ilustrace poskytuje vizuální znázornění tohoto konceptu:

Cik-cak rotace

pole řazení java


6) Rotace Zag-Zig:

Rotace Zag-Zig v rozvětvených stromech je série zag rotací následovaných klikatou rotací. To má za následek posunutí uzlů o jednu pozici doleva a následné posunutí o jednu pozici doprava z jejich aktuálního umístění. Následující ilustrace nabízí vizuální znázornění tohoto konceptu:

Rotace Zag-Zig

Níže je uveden kód C++ pro implementaci rotací ve stromu Splay:

C++ 
#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->klíč = klíč;  uzel->vlevo = uzel->vpravo = nullptr;  návratový uzel; } Uzel* vpravoRotate(Uzel* x) { Uzel* y = x->vlevo;  x->vlevo = y->vpravo;  y->vpravo = x;  vrátit y; } Uzel* dolevaRotate(Uzel* x) { Uzel* y = x->vpravo;  x->vpravo = y->vlevo;  y->vlevo = x;  vrátit 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 (root->left->key< key) {  root->left->right = splay(root->left->right, key);  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 (kořen->vpravo->klávesa< key) {  root->right->right = splay(root->right->right, key);  root = leftRotate(kořen);  } return (root->right == nullptr) ? root : leftRotate(root);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  root = splay(kořen, klíč);  if (root->key == key) return root;  Uzel* uzel = novyUzel(klíč);  if (root->key> key) { node->right = root;  uzel->left = root->left;  root->left = nullptr;  } else { uzel->left = root;  uzel->vpravo = kořen->vpravo;  root->right = nullptr;  } návratový uzel; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->klíč<< ' ';  preOrder(node->vlevo, odjet);  preOrder(uzel->vpravo);  } } int main() { Uzel* root = nullptr;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(kořen, 40);  root = insert(root, 60);  cout<< 'Preorder traversal of the modified Splay tree:' << endl;  preOrder(root);  return 0; }>
Jáva 
// 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>klíč) { 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>klíč) { node.right = root;  uzel.left = root.left;  root.left = null;  } else { uzel.left = root;  node.right = root.right;  root.right = null;  } návratový uzel;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(node.key + ' ');  preOrder(uzel.left);  preOrder(node.right);  } } public static void main(String[] args) { Kořen uzlu = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(kořen, 40);  root = insert(root, 60);  System.out.println('Přechod předobjednávky upraveného stromu Splay:');  preOrder(kořen);  } } // Tento kód přispěl 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>key: if root.left is None: return root if 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>klíč: 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>klíč: node.right = root node.left = root.left root.left = Žádný jiný: node.left = kořenový uzel.right = root.right root.right = Žádný return node def pre_order(uzel): if node: print (node.key, end=' ') pre_order(uzel.left) pre_order(uzel.right) if __name__ == '__main__': root = Žádný root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Přechod předobjedná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>klíč) { 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>klíč) { node.right = root;  uzel.left = root.left;  root.left = null;  } else { uzel.left = root;  node.right = root.right;  root.right = null;  } návratový uzel;  } static void preOrder(Node node) { if (uzel != null) { Console.Write(node.key + ' ');  preOrder(uzel.left);  preOrder(uzel.right);  } } public static void Main(string[] args) { Kořen uzlu = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(kořen, 40);  root = insert(root, 60);  Console.WriteLine( 'Přechod předobjednávky upraveného stromu Splay:');  preOrder(kořen);  } } // Tento kód přispěl princ Kumar>
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>klíč) { if (root.left == null) { return root;  } if (root.left.key> key) { root.left.left = SplayTree.splay(root.left.left, key);  root = SplayTree.rightRotate(kořen);  } 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>klíč) { 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>klíč) { node.right = root;  uzel.left = root.left;  root.left = null;  } else { uzel.left = root;  node.right = root.right;  root.right = null;  } návratový uzel;  } static preOrder(uzel) { if (uzel != null) { console.log(uzel.key + ' ');  SplayTree.preOrder(uzel.left);  SplayTree.preOrder(node.right);  } } } nech root = null; root = SplayTree.insert(kořen, 100); root = SplayTree.insert(kořen, 50); root = SplayTree.insert(kořen, 200); root = SplayTree.insert(kořen, 40); root = SplayTree.insert(kořen, 60); console.log('Přechod předobjednávky upraveného stromu Splay:'); SplayTree.preOrder(root); // Kód přispěl Nidhi goel.>
Výstup 
Preorder traversal of the modified Splay tree:>

Nevýhody datové struktury splay tree:

  • Nevyvážené stromy: Rozvětvené stromy se mohou stát nevyváženými a neefektivními, pokud se strom opakovaně otáčí stejným směrem.
  • Využití paměti: Splay stromy mohou ve srovnání s jinými datovými strukturami využívat hodně paměti, protože každý uzel obsahuje další informace.
  • Složitost: Rozprostřené stromy mohou mít vysokou časovou složitost pro základní operace, jako je vkládání a mazání, protože stromy je třeba po každé operaci reorganizovat.
  • Režijní náklady na reorganizaci: Operace roztažení vyžadovaná v každé operaci může být časově náročná a vést k vysoké režii.
  • Omezené případy použití : Stromy zobrazení nejsou vhodné pro všechny datové struktury a mají omezené případy použití, protože nezpracovávají duplicitní klíče efektivně.

Aplikace rozvětveného stromu:

  • Ukládání do mezipaměti : Stromy Splay lze použít k implementaci správy mezipaměti, kde jsou nejčastěji používané položky přesunuty do horní části stromu pro rychlejší přístup.
  • Indexování databáze : Splay stromy lze použít k indexování databází pro rychlejší vyhledávání a načítání dat.
  • Souborové systémy : Stromy Splay lze použít k ukládání metadat systému souborů, jako je alokační tabulka, struktura adresářů a atributy souborů.
  • Komprese dat: Splay stromy lze použít ke kompresi dat identifikací a kódováním opakujících se vzorů.
  • Zpracování textu : Stromy zobrazení lze použít v aplikacích pro zpracování textu, jako je kontrola pravopisu, kde jsou slova uložena ve stromu zobrazení pro rychlé vyhledávání a načítání.
  • Algoritmy grafů: Splay stromy lze použít k implementaci grafových algoritmů, jako je nalezení nejkratší cesty ve váženém grafu.
  • Online hry: Splay stromy lze použít v online hraní k ukládání a správě nejvyšších skóre, žebříčků a statistik hráčů.

Jistě, zde jsou některé výhody a nevýhody rozvětvených stromů a také některé doporučené knihy, kde se můžete dozvědět více o tématu:

Výhody rozvětvených stromů:

Splay stromy mají amortizovanou časovou složitost O(log n) pro mnoho operací, díky čemuž jsou v některých případech rychlejší než mnoho jiných vyvážených stromových datových struktur.
Rozvětvené stromy jsou samonastavitelné, což znamená, že se automaticky vyvažují při vkládání a odebírání položek. To může pomoci vyhnout se snížení výkonu, ke kterému může dojít, když se strom stane nevyváženým.

jlist

Nevýhody rozvětvených stromů:

Rozprostřené stromy mohou mít v nejhorším případě časovou složitost O(n) pro některé operace, což je činí méně předvídatelnými než jiné datové struktury vyváženého stromu, jako jsou AVL stromy nebo červeno-černé stromy.
Rozvětvené stromy nemusí být vhodné pro určité aplikace, kde je vyžadován předvídatelný výkon.

Doporučené knihy o Splay Trees:

Datové struktury a analýza algoritmů v Javě od Marka Allena Weisse
Úvod do algoritmů od Thomase H. Cormena, Charlese E. Leisersona, Ronalda L. Rivesta a Clifforda Steina
Datové struktury a algoritmy v C++ od Michaela T. Goodricha a Roberta Tamassie

Závěr:

Závěrem lze říci, že Splay Trees jsou dynamickou samovyvažující binární strukturou vyhledávacího stromu, která poskytuje efektivní způsob vyhledávání, vkládání a mazání prvků. Liší se od tradičních vyvážených binárních vyhledávacích stromů, jako jsou AVL a Red-Black stromy, protože reorganizují strom po každé operaci tak, aby přivedl nedávno zpřístupněný uzel do kořene. To pomáhá snížit výšku stromu a má za následek rychlejší operace. Splay Trees jsou vysoce flexibilní a lze je přizpůsobit různým případům použití. Ačkoli mohou mít vyšší režii, pokud jde o rotace, jejich jednoduchost a všestrannost z nich činí užitečné nástroje pro řešení široké škály problémů.