Splay tree is een zelfaanpassende binaire zoekboomdatastructuur, wat betekent dat de boomstructuur dynamisch wordt aangepast op basis van de geopende of ingevoegde elementen. Met andere woorden: de boom reorganiseert zichzelf automatisch, zodat vaak gebruikte of ingevoegde elementen dichter bij het hoofdknooppunt komen te liggen.

1. De splay tree werd voor het eerst geïntroduceerd door Daniel Dominic Sleator en Robert Endre Tarjan in 1985. Het heeft een eenvoudige en efficiënte implementatie waarmee het zoek-, invoeg- en verwijderbewerkingen kan uitvoeren in O(log n) geamortiseerde tijdscomplexiteit, waarbij n de aantal elementen in de boom.
2. Het basisidee achter splay-bomen is om het meest recentelijk geopende of ingevoegde element naar de wortel van de boom te brengen door een reeks boomrotaties uit te voeren, genaamd splaying. Splaying is een proces waarbij de boom wordt geherstructureerd door van het meest recent geopende of ingevoegde element de nieuwe root te maken en de resterende knooppunten geleidelijk dichter bij de root te verplaatsen.
3. Splay-bomen zijn in de praktijk zeer efficiënt vanwege hun zelfinstellende karakter, waardoor de totale toegangstijd voor vaak gebruikte elementen wordt verkort. Dit maakt ze een goede keuze voor toepassingen die snelle en dynamische datastructuren vereisen, zoals cachingsystemen, datacompressie en netwerkrouteringsalgoritmen.
4. Het grootste nadeel van splay-trees is echter dat ze geen evenwichtige boomstructuur garanderen, wat in het ergste geval tot prestatieverlies kan leiden. Ook zijn splay-trees niet geschikt voor toepassingen die gegarandeerde worst-case prestaties vereisen, zoals real-time systemen of veiligheidskritische systemen.

Over het geheel genomen zijn splay-bomen een krachtige en veelzijdige datastructuur die snelle en efficiënte toegang biedt tot vaak gebruikte of ingevoegde elementen. Ze worden veel gebruikt in verschillende toepassingen en bieden een uitstekende balans tussen prestaties en eenvoud.

Een splay tree is een zelfbalancerende binaire zoekboom, ontworpen voor efficiënte toegang tot gegevenselementen op basis van hun sleutelwaarden.

• Het belangrijkste kenmerk van een splay tree is dat elke keer dat een element wordt geopend, het naar de root van de boom wordt verplaatst, waardoor een meer evenwichtige structuur ontstaat voor volgende toegangen.
• Splay-bomen worden gekenmerkt door het gebruik van rotaties, dit zijn lokale transformaties van de boom die van vorm veranderen maar de volgorde van de elementen behouden.
• Rotaties worden gebruikt om het gebruikte element naar de wortel van de boom te brengen, en ook om de boom opnieuw in evenwicht te brengen als deze na meerdere toegangen uit balans raakt.

Bewerkingen in een spreidingsboom:

• Plaatsing: Om een ​​nieuw element in de boom in te voegen, begint u met het regelmatig invoegen van een binaire zoekboom. Pas vervolgens rotaties toe om het nieuw ingevoegde element naar de wortel van de boom te brengen.
• Verwijdering : Om een ​​element uit de boom te verwijderen, lokaliseert u het eerst met behulp van een binaire zoekboomzoekopdracht. Als het element geen onderliggende elementen heeft, verwijdert u het eenvoudigweg. Als er één kind is, promoveer dat kind dan naar zijn positie in de stamboom. Als het twee kinderen heeft, zoek dan de opvolger van het element (het kleinste element in de rechter subboom), verwissel de sleutel met het element dat moet worden verwijderd en verwijder in plaats daarvan de opvolger.
• Zoekopdracht : Om naar een element in de boom te zoeken, begint u met het uitvoeren van een binaire zoekboomzoekopdracht. Als het element wordt gevonden, pas dan rotaties toe om het naar de wortel van de boom te brengen. Als het niet wordt gevonden, pas dan rotaties toe op het laatst bezochte knooppunt tijdens de zoekopdracht, dat de nieuwe root wordt.
• Rotatie : De rotaties die in een spreidingsboom worden gebruikt, zijn een zig- of een zig-zig-rotatie. Een Zig-rotatie wordt gebruikt om een ​​knooppunt naar de wortel te brengen, terwijl een Zig-Zig-rotatie wordt gebruikt om de boom in evenwicht te brengen na meerdere toegangen tot elementen in dezelfde subboom.

Hier volgt een stapsgewijze uitleg van de rotatiebewerkingen:

• Zig-rotatie : Als een knooppunt een rechterkind heeft, voer dan een rotatie naar rechts uit om het naar de wortel te brengen. Als er een links kind is, voer dan een rotatie naar links uit.
• Zig-Zig-rotatie: Als een knooppunt een kleinkind heeft dat ook het rechter- of linkerkind van het knooppunt is, voer dan een dubbele rotatie uit om de boom in evenwicht te brengen. Als het knooppunt bijvoorbeeld een rechterkind heeft en het rechterkind een linkerkind, voer dan een rotatie van rechts naar links uit. Als het knooppunt een linkerkind heeft en het linkerkind een rechterkind, voer dan een rotatie van links naar rechts uit.
• Opmerking: De specifieke implementatiedetails, inclusief de exacte gebruikte rotaties, kunnen variëren afhankelijk van de exacte vorm van de spreidingsboom.

Rotaties in de Splay Tree

• Zig-rotatie
• Zag-rotatie
• Zig – Zig-rotatie
• Zag – Zag-rotatie
• Zig-Zag-rotatie
• Zag – Zig-rotatie

1) Zig-rotatie:

De Zig-rotatie in gespreide bomen werkt op een manier die vergelijkbaar is met de enkele rotatie naar rechts in AVL-boomrotaties. Deze rotatie resulteert erin dat knooppunten één positie naar rechts verschuiven vanaf hun huidige locatie. Neem bijvoorbeeld het volgende scenario:

Zig-rotatie (enkele rotatie)

2) Zag-rotatie:

De Zag-rotatie in gespreide bomen werkt op dezelfde manier als de enkele rotatie naar links in AVL-boomrotaties. Tijdens deze rotatie verschuiven de knooppunten één positie naar links vanaf hun huidige locatie. Beschouw bijvoorbeeld de volgende illustratie:

java-waarde van enum

Zag-rotatie (enkele rotatie naar links)

3) Zig-zig-rotatie:

De zig-zig-rotatie in gespreide bomen is een dubbele zig-rotatie. Deze rotatie resulteert erin dat knooppunten twee posities naar rechts verschuiven vanaf hun huidige locatie. Bekijk het volgende voorbeeld voor een beter begrip:

Zig-Zig-rotatie (dubbele rotatie naar rechts)

4) Zag-Zag-rotatie:

Bij gespreide bomen is de Zag-Zag-rotatie een dubbele zagrotatie. Deze rotatie zorgt ervoor dat knooppunten vanuit hun huidige positie twee posities naar links bewegen. Bijvoorbeeld:

Zag-Zag-rotatie (dubbele rotatie naar links)

Java while-lus

5) Zigzagrotatie:

De zigzagrotatie in gespreide bomen is een combinatie van een zig-rotatie gevolgd door een zag-rotatie. Als gevolg van deze rotatie verschuiven knooppunten één positie naar rechts en vervolgens één positie naar links vanaf hun huidige locatie. De volgende illustratie biedt een visuele weergave van dit concept:

Zigzagrotatie

6) Zag-Zig-rotatie:

De Zag-Zig-rotatie in gespreide bomen is een reeks zagrotaties gevolgd door een zig-rotatie. Dit resulteert erin dat knooppunten één positie naar links verschuiven, gevolgd door een verschuiving van één positie naar rechts vanaf hun huidige locatie. De volgende illustratie biedt een visuele weergave van dit concept:

Zag-Zig-rotatie

Hieronder vindt u de C++-code om rotaties in de Splay-boom te implementeren:

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->sleutel = sleutel;  knooppunt->links = knooppunt->rechts = nullptr;  retourknooppunt; } Knooppunt* rechtsRoteren(Knooppunt* x) { Knooppunt* y = x->links;  x->links = y->rechts;  y->rechts = x;  retour y; } Knooppunt* leftRotate(Knooppunt* x) { Knooppunt* y = x->rechts;  x->rechts = y->links;  y->links = x;  retour y; } Knooppunt* splay(Knooppunt* root, int sleutel) { if (root == nullptr || root->key == sleutel) return root;  if (root->key> key) { if (root->left == nullptr) return root;  if (root->links->toets> sleutel) { root->links->links = splay(root->links->links, sleutel);  wortel = rechtsRoteren(wortel);  } else if (root->links->toets< key) {  root->links->rechts = splay(root->links->rechts, sleutel);  if (wortel->links->rechts!= nullptr) root->links = linksdraaien(wortel->links);  } return (root->links == nullptr) ? wortel: rechtsRoteren(wortel);  } else { if (root->right == nullptr) return root;  if (wortel->rechts->toets> sleutel) { wortel->rechts->links = splay(wortel->rechts->links, sleutel);  if (wortel->rechts->links!= nullptr) wortel->rechts = rechtsRoteren(wortel->rechts);  } else if (root->rechts->toets< key) {  root->rechts->rechts = splay(root->rechts->rechts, sleutel);  wortel = linksdraaien(wortel);  } return (root->rechts == nullptr) ? wortel: linksRoteren(wortel);  } } Knooppunt* insert(Knooppunt* root, int sleutel) { if (root == nullptr) return newNode(sleutel);  root = splay(root, sleutel);  if (root->sleutel == sleutel) retourneert root;  Knooppunt* knooppunt = newNode(sleutel);  if (root->sleutel> sleutel) { knooppunt->rechts = root;  knooppunt->links = wortel->links;  wortel->links = nullptr;  } else { knooppunt->links = root;  knooppunt->rechts = wortel->rechts;  root->rechts = nullptr;  } retourknooppunt; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->sleutel<< ' ';  preOrder(node->links);  preOrder(knooppunt->rechts);  } } int main() { Knooppunt* root = nullptr;  wortel = invoegen(wortel, 100);  wortel = invoegen(wortel, 50);  wortel = invoegen(wortel, 200);  wortel = invoegen(wortel, 40);  wortel = invoegen(wortel, 60);  uit<< '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>sleutel) { if (root.left == null) return root;  if (root.left.key> sleutel) { root.left.left = splay(root.left.left, sleutel);  wortel = rechtsRoteren(wortel);  } 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>sleutel) { root.right.left = splay(root.right.left, sleutel);  if (root.right.left!= null) root.right = rechtsRoteren(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>sleutel) { node.right = root;  knooppunt.links = root.links;  root.left = nul;  } anders { node.left = root;  knooppunt.rechts = root.rechts;  root.right = nul;  } retourknooppunt;  } static void preOrder(knooppunt) { if (knooppunt!= null) { System.out.println();  Systeem.uit.print(knooppunt.sleutel + ' ');  preOrder(node.links);  preOrder(node.right);  } } public static void main(String[] args) { Knooppunt root = null;  wortel = invoegen(wortel, 100);  wortel = invoegen(wortel, 50);  wortel = invoegen(wortel, 200);  wortel = invoegen(wortel, 40);  wortel = invoegen(wortel, 60);  System.out.println('Voorbestelling doorkruisen van de gewijzigde Splay-boom:');  vooraf bestellen(root);  } } // Deze code is bijgedragen door prinskumaras>

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>sleutel: als root.left Geen is: retourneert root als root.left.key> sleutel: root.left.left = splay(root.left.left, sleutel) root = rechts_roteren(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>sleutel: root.right.left = splay(root.right.left, sleutel) if root.right.left: root.right = rechts_roteren(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>sleutel: node.right = root node.left = root.left root.left = Geen anders: node.left = root node.right = root.right root.right = Geen return node def pre_order(node): if node: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Geen root = insert(root, 100) root = insert(root , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Preorder traversal van de gewijzigde Splay-boom:') 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>sleutel) { if (root.left == null) return root;  if (root.left.key> sleutel) { root.left.left = splay(root.left.left, sleutel);  wortel = rechtsRoteren(wortel);  } 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>sleutel) { root.right.left = splay(root.right.left, sleutel);  if (root.right.left!= null) root.right = rechtsRoteren(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>sleutel) { node.right = root;  knooppunt.links = root.links;  root.left = nul;  } anders { node.left = root;  knooppunt.rechts = root.rechts;  root.right = nul;  } retourknooppunt;  } static void preOrder(knooppunt) { if (knooppunt!= null) { Console.Write(knooppunt.key + ' ');  preOrder(node.links);  preOrder(node.right);  } } public static void Main(string[] args) { Knooppunt root = null;  wortel = invoegen(wortel, 100);  wortel = invoegen(wortel, 50);  wortel = invoegen(wortel, 200);  wortel = invoegen(wortel, 40);  wortel = invoegen(wortel, 60);  Console.WriteLine( 'Voorbestelling doorkruisen van de gewijzigde Splay-boom:');  vooraf bestellen(root);  } } // Deze code is bijgedragen door Prince 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>sleutel) { if (root.left == null) { return root;  } if (root.left.key> sleutel) { root.left.left = SplayTree.splay(root.left.left, sleutel);  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>sleutel) { root.right.left = SplayTree.splay(root.right.left, sleutel);  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>sleutel) { node.right = root;  knooppunt.links = root.links;  root.left = nul;  } anders { node.left = root;  knooppunt.rechts = root.rechts;  root.right = nul;  } retourknooppunt;  } statische preOrder(node) { if (node ​​!= null) { console.log(node.key + ' ');  SplayTree.preOrder(knooppunt.links);  SplayTree.preOrder(knooppunt.rechts);  } } } laat root = nul; 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('Voorbestelling doorkruisen van de gewijzigde Splay-boom:'); SplayTree.preOrder(root); // De code is bijgedragen door Nidhi goel.>

Preorder traversal of the modified Splay tree:>

Nadelen van de splay tree-datastructuur:

• Onevenwichtige bomen: Splay-bomen kunnen uit balans raken en inefficiënt worden als de boom herhaaldelijk in dezelfde richting wordt gedraaid.
• Geheugengebruik: Splay-bomen kunnen veel geheugen gebruiken in vergelijking met andere datastructuren, omdat elk knooppunt aanvullende informatie bevat.
• Complexiteit: Splay-bomen kunnen een hoge tijdscomplexiteit hebben voor basisbewerkingen zoals invoegen en verwijderen, omdat de bomen na elke bewerking opnieuw moeten worden georganiseerd.
• Reorganisatie-overhead: De spreidoperatie die bij elke operatie nodig is, kan tijdrovend zijn en resulteren in een hoge overhead.
• Beperkte gebruiksscenario's : Splay-bomen zijn niet geschikt voor alle datastructuren en hebben beperkte gebruiksmogelijkheden omdat ze niet efficiënt omgaan met dubbele sleutels.

Toepassingen van de splayboom:

• Caching : Splay-bomen kunnen worden gebruikt om cachegeheugenbeheer te implementeren, waarbij de meest gebruikte items naar de top van de boom worden verplaatst voor snellere toegang.
• Database-indexering : Splay-bomen kunnen worden gebruikt om databases te indexeren, zodat gegevens sneller kunnen worden gezocht en opgehaald.
• Bestandssystemen : Splay-bomen kunnen worden gebruikt om metagegevens van het bestandssysteem op te slaan, zoals de toewijzingstabel, de mapstructuur en bestandskenmerken.
• Data compressie: Splay-bomen kunnen worden gebruikt om gegevens te comprimeren door herhalende patronen te identificeren en te coderen.
• Tekstverwerking : Splay-bomen kunnen worden gebruikt in tekstverwerkingstoepassingen, zoals spellingcontrole, waarbij woorden worden opgeslagen in een splay-boom voor snel zoeken en ophalen.
• Grafiekalgoritmen: Splay-bomen kunnen worden gebruikt om grafiekalgoritmen te implementeren, zoals het vinden van het kortste pad in een gewogen grafiek.
• Online gaming: Splay-bomen kunnen bij online gaming worden gebruikt om topscores, klassementen en spelerstatistieken op te slaan en te beheren.

Natuurlijk, hier zijn enkele voor- en nadelen van spreidbomen, evenals enkele aanbevolen boeken om meer over het onderwerp te leren:

Voordelen van Splay-bomen:

Splay-bomen hebben voor veel bewerkingen de tijdscomplexiteit van O(log n) afgeschreven, waardoor ze in sommige gevallen sneller zijn dan veel andere gebalanceerde boomdatastructuren.
Splay-bomen zijn zelfaanpassend, wat betekent dat ze zichzelf automatisch in evenwicht brengen als er items worden ingevoegd en verwijderd. Dit kan helpen de prestatievermindering te voorkomen die kan optreden wanneer een boom uit balans raakt.

Nadelen van Splay-bomen:

Splay-bomen kunnen voor sommige bewerkingen in het slechtste geval een tijdcomplexiteit van O(n) hebben, waardoor ze minder voorspelbaar zijn dan andere gebalanceerde boomdatastructuren zoals AVL-bomen of rood-zwarte bomen.
Splay-bomen zijn mogelijk niet geschikt voor bepaalde toepassingen waarbij voorspelbare prestaties vereist zijn.

restoperator van Python

Aanbevolen boeken over Splay Trees:

Datastructuren en algoritmeanalyse in Java door Mark Allen Weiss
Inleiding tot algoritmen door Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest en Clifford Stein
Datastructuren en algoritmen in C++ door Michael T. Goodrich en Roberto Tamassia

Conclusie:

Kortom, Splay Trees zijn een dynamische, zelfbalancerende binaire zoekboomdatastructuur die een efficiënte manier biedt om elementen te zoeken, in te voegen en te verwijderen. Ze verschillen van traditionele gebalanceerde binaire zoekbomen zoals AVL- en rood-zwarte bomen, omdat ze de boom na elke bewerking reorganiseren om het recentelijk benaderde knooppunt naar de root te brengen. Dit helpt de hoogte van de boom te verminderen en resulteert in snellere bewerkingen. Splay Trees zijn zeer flexibel en kunnen worden aangepast aan verschillende gebruikssituaties. Hoewel ze misschien een hogere overhead hebben in termen van rotaties, maken hun eenvoud en veelzijdigheid ze tot nuttige hulpmiddelen voor het oplossen van een breed scala aan problemen.