Der Splay-Baum ist eine selbstanpassende binäre Suchbaum-Datenstruktur, was bedeutet, dass die Baumstruktur dynamisch basierend auf den aufgerufenen oder eingefügten Elementen angepasst wird. Mit anderen Worten: Der Baum organisiert sich automatisch neu, sodass häufig aufgerufene oder eingefügte Elemente näher am Wurzelknoten liegen.

1. Der Spreizbaum wurde erstmals 1985 von Daniel Dominic Sleator und Robert Endre Tarjan eingeführt. Er verfügt über eine einfache und effiziente Implementierung, die es ihm ermöglicht, Such-, Einfügungs- und Löschoperationen mit einer amortisierten Zeitkomplexität von O(log n) durchzuführen, wobei n die ist Anzahl der Elemente im Baum.
2. Die Grundidee hinter Splay-Bäumen besteht darin, das zuletzt aufgerufene oder eingefügte Element an die Wurzel des Baums zu bringen, indem eine Folge von Baumrotationen durchgeführt wird, die als Splaying bezeichnet wird. Spreizen ist ein Prozess der Umstrukturierung des Baums, indem das zuletzt aufgerufene oder eingefügte Element zum neuen Stamm wird und die verbleibenden Knoten schrittweise näher an den Stamm herangeführt werden.
3. Spreizbäume sind in der Praxis aufgrund ihrer selbstanpassenden Natur äußerst effizient, wodurch die Gesamtzugriffszeit für häufig aufgerufene Elemente verkürzt wird. Dies macht sie zu einer guten Wahl für Anwendungen, die schnelle und dynamische Datenstrukturen erfordern, wie etwa Caching-Systeme, Datenkomprimierung und Netzwerk-Routing-Algorithmen.
4. Der Hauptnachteil von Spreizbäumen besteht jedoch darin, dass sie keine ausgewogene Baumstruktur garantieren, was im schlimmsten Fall zu Leistungseinbußen führen kann. Außerdem eignen sich Spreizbäume nicht für Anwendungen, die eine garantierte Worst-Case-Leistung erfordern, wie etwa Echtzeitsysteme oder sicherheitskritische Systeme.

Insgesamt handelt es sich bei Spreizbäumen um eine leistungsstarke und vielseitige Datenstruktur, die einen schnellen und effizienten Zugriff auf häufig aufgerufene oder eingefügte Elemente bietet. Sie werden häufig in verschiedenen Anwendungen eingesetzt und bieten einen hervorragenden Kompromiss zwischen Leistung und Einfachheit.

Ein Splay Tree ist ein selbstausgleichender binärer Suchbaum, der für den effizienten Zugriff auf Datenelemente basierend auf ihren Schlüsselwerten konzipiert ist.

• Das Hauptmerkmal eines Spreizbaums besteht darin, dass jedes Mal, wenn auf ein Element zugegriffen wird, es in die Wurzel des Baums verschoben wird, wodurch eine ausgewogenere Struktur für nachfolgende Zugriffe entsteht.
• Spreizbäume zeichnen sich durch die Verwendung von Rotationen aus, bei denen es sich um lokale Transformationen des Baums handelt, die seine Form ändern, aber die Reihenfolge der Elemente beibehalten.
• Rotationen werden verwendet, um das Element, auf das zugegriffen wird, an die Wurzel des Baums zu bringen und auch, um den Baum neu auszubalancieren, wenn er nach mehreren Zugriffen aus dem Gleichgewicht gerät.

Operationen in einem Spreizbaum:

• Einfügung: Um ein neues Element in den Baum einzufügen, führen Sie zunächst eine reguläre binäre Suchbaumeinfügung durch. Wenden Sie dann Drehungen an, um das neu eingefügte Element an die Wurzel des Baums zu bringen.
• Streichung : Um ein Element aus dem Baum zu löschen, suchen Sie es zunächst mithilfe einer binären Baumsuche. Wenn das Element dann keine untergeordneten Elemente hat, entfernen Sie es einfach. Wenn es ein Kind hat, befördern Sie dieses Kind an seine Position im Stammbaum. Wenn es zwei untergeordnete Elemente hat, suchen Sie den Nachfolger des Elements (das kleinste Element in seinem rechten Teilbaum), tauschen Sie seinen Schlüssel mit dem zu löschenden Element aus und löschen Sie stattdessen den Nachfolger.
• Suchen : Um nach einem Element im Baum zu suchen, führen Sie zunächst eine binäre Baumsuche durch. Wenn das Element gefunden wird, wenden Sie Drehungen an, um es zur Wurzel des Baums zu bringen. Wenn er nicht gefunden wird, wenden Sie Rotationen auf den letzten bei der Suche besuchten Knoten an, der zum neuen Stamm wird.
• Drehung : Die in einem Spreizbaum verwendeten Rotationen sind entweder eine Zig- oder eine Zig-Zig-Rotation. Eine Zig-Zig-Rotation wird verwendet, um einen Knoten zur Wurzel zu bringen, während eine Zig-Zig-Rotation verwendet wird, um den Baum nach mehreren Zugriffen auf Elemente im selben Unterbaum auszugleichen.

Hier finden Sie eine Schritt-für-Schritt-Erklärung der Rotationsvorgänge:

• Zick-Rotation : Wenn ein Knoten ein rechtes Kind hat, führen Sie eine Rechtsdrehung durch, um ihn zur Wurzel zu bringen. Wenn es ein linkes Kind hat, führen Sie eine Linksdrehung durch.
• Zick-Zig-Rotation: Wenn ein Knoten ein Enkelkind hat, das auch das rechte oder linke Kind seines Kindes ist, führen Sie eine doppelte Drehung durch, um den Baum auszugleichen. Wenn der Knoten beispielsweise ein rechtes Kind hat und das rechte Kind ein linkes Kind hat, führen Sie eine Rechts-Links-Rotation durch. Wenn der Knoten ein linkes Kind hat und das linke Kind ein rechtes Kind hat, führen Sie eine Links-Rechts-Rotation durch.
• Notiz: Die spezifischen Implementierungsdetails, einschließlich der genauen verwendeten Rotationen, können je nach der genauen Form des Spreizbaums variieren.

Rotationen im Splay Tree

• Zick-Rotation
• Zackenrotation
• Zick – Zick-Rotation
• Zag – Zag-Rotation
• Zick-Zack-Rotation
• Zag – Zick-Rotation

1) Zick-Rotation:

Die Zick-Rotation in Spreizbäumen funktioniert auf ähnliche Weise wie die einzelne Rechtsdrehung in AVL-Baumrotationen. Diese Drehung führt dazu, dass Knoten von ihrem aktuellen Standort um eine Position nach rechts verschoben werden. Stellen Sie sich beispielsweise das folgende Szenario vor:

Zick-Rotation (Einzelrotation)

2) Zackendrehung:

Die Zag-Rotation in Spreizbäumen funktioniert auf ähnliche Weise wie die einzelne Linksrotation in AVL-Baumrotationen. Während dieser Drehung verschieben sich die Knoten von ihrer aktuellen Position um eine Position nach links. Betrachten Sie zum Beispiel die folgende Abbildung:

Shilpa Shetty Alter

Zag-Rotation (einzelne Linksrotation)

3) Zick-Zig-Rotation:

Die Zig-Zig-Rotation bei Spreizbäumen ist eine doppelte Zick-Rotation. Diese Drehung führt dazu, dass Knoten von ihrem aktuellen Standort aus um zwei Positionen nach rechts verschoben werden. Schauen Sie sich zum besseren Verständnis das folgende Beispiel an:

Wie groß ist mein Monitor?

Zick-Zig-Rotation (doppelte Rechtsrotation)

4) Zag-Zag-Rotation:

Bei Spreizbäumen handelt es sich bei der Zag-Zag-Rotation um eine doppelte Zackenrotation. Durch diese Drehung verschieben sich die Knoten von ihrer aktuellen Position um zwei Positionen nach links. Zum Beispiel:

Zag-Zag-Rotation (Doppelte Linksrotation)

5) Zick-Zack-Rotation:

Die Zick-Zack-Rotation in Spreizbäumen ist eine Kombination aus einer Zick-Zack-Rotation gefolgt von einer Zack-Rotation. Durch diese Drehung verschieben sich die Knoten von ihrer aktuellen Position um eine Position nach rechts und dann um eine Position nach links. Die folgende Abbildung bietet eine visuelle Darstellung dieses Konzepts:

Zick-Zack-Rotation

6) Zag-Zig-Rotation:

Die Zag-Zig-Rotation in Spreizbäumen besteht aus einer Reihe von Zackenrotationen, denen eine Zick-Rotation folgt. Dies führt dazu, dass sich Knoten um eine Position nach links verschieben, gefolgt von einer Verschiebung um eine Position nach rechts von ihrem aktuellen Standort. Die folgende Abbildung bietet eine visuelle Darstellung dieses Konzepts:

Zack-Zick-Rotation

Unten finden Sie den C++-Code zum Implementieren von Rotationen im Splay-Baum:

#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->Schlüssel = Schlüssel;  node->left = node->right = nullptr;  Rückkehrknoten; } Node* rightRotate(Node* x) { Node* y = x->left;  x->links = y->rechts;  y->rechts = x;  y zurückgeben; } Node* leftRotate(Node* x) { Node* y = x->right;  x->rechts = y->links;  y->links = x;  y zurückgeben; } 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 (root->right->key< 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(root, key);  if (root->key == key) return root;  Node* node = newNode(key);  if (root->key> key) { node->right = root;  node->left = root->left;  root->left = nullptr;  } else { node->left = root;  node->right = root->right;  root->right = nullptr;  } return node; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->Schlüssel<< ' ';  preOrder(node->links);  preOrder(node->right);  } } int main() { Node* 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 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>Schlüssel) { 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>key) { 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>Schlüssel) { node.right = root;  node.left = root.left;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } return node;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(node.key + ' ');  Vorbestellung(node.left);  Vorbestellung(node.right);  } } public static void main(String[] args) { Node root = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  System.out.println('Durchquerung des geänderten Splay-Baums vorbestellen:');  Vorbestellung(root);  } } // Dieser Code wurde von Princekumaras beigesteuert>

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: wenn root.left None ist: root zurückgeben, wenn 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>key: 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>Schlüssel: node.right = root node.left = root.left root.left = Keine sonst: node.left = root node.right = root.right root.right = Keine return node def pre_order(node): 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) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Vorbestellungsdurchquerung des modifizierten Splay-Baums:') 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>Schlüssel) { 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>key) { 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>Schlüssel) { node.right = root;  node.left = root.left;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } return node;  } static void preOrder(Node node) { if (node ​​!= null) { Console.Write(node.key + ' ');  Vorbestellung(node.left);  Vorbestellung(node.right);  } } public static void Main(string[] args) { Node root = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  Console.WriteLine( 'Durchquerung des geänderten Splay-Baums vorbestellen:');  Vorbestellung(root);  } } // Dieser Code wurde von Prince Kumar beigesteuert>

// 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>Schlüssel) { 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>key) { 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>Schlüssel) { node.right = root;  node.left = root.left;  root.left = null;  } else { node.left = root;  node.right = root.right;  root.right = null;  } return node;  } 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('Durchquerung des geänderten Splay-Baums vorbestellen:'); SplayTree.preOrder(root); // Der Code wurde von Nidhi Goel beigesteuert.>

Preorder traversal of the modified Splay tree:>

Nachteile der Spreizbaum-Datenstruktur:

• Unausgeglichene Bäume: Gespreizte Bäume können aus dem Gleichgewicht geraten und ineffizient werden, wenn der Baum wiederholt in die gleiche Richtung gedreht wird.
• Speichernutzung: Spreizbäume können im Vergleich zu anderen Datenstrukturen viel Speicher beanspruchen, da jeder Knoten zusätzliche Informationen enthält.
• Komplexität: Spreizbäume können für grundlegende Vorgänge wie Einfügen und Löschen eine hohe zeitliche Komplexität aufweisen, da die Bäume nach jedem Vorgang neu organisiert werden müssen.
• Reorganisationsaufwand: Der bei jedem Arbeitsgang erforderliche Spreizvorgang kann zeitaufwändig sein und zu einem hohen Overhead führen.
• Begrenzte Anwendungsfälle : Splay-Bäume sind nicht für alle Datenstrukturen geeignet und haben begrenzte Anwendungsfälle, da sie doppelte Schlüssel nicht effizient verarbeiten.

Anwendungen des Spreizbaums:

• Caching : Splay-Bäume können zur Implementierung der Cache-Speicherverwaltung verwendet werden, wobei die am häufigsten aufgerufenen Elemente für einen schnelleren Zugriff an die Spitze des Baums verschoben werden.
• Datenbankindizierung : Splay-Bäume können zur Indizierung von Datenbanken verwendet werden, um die Suche und den Abruf von Daten zu beschleunigen.
• Dateisysteme : Splay-Bäume können zum Speichern von Dateisystem-Metadaten wie der Zuordnungstabelle, der Verzeichnisstruktur und Dateiattributen verwendet werden.
• Datenkompression: Spreizbäume können zum Komprimieren von Daten verwendet werden, indem sich wiederholende Muster identifiziert und kodiert werden.
• Textverarbeitung : Spreizbäume können in Textverarbeitungsanwendungen wie Rechtschreibprüfungen verwendet werden, wo Wörter zum schnellen Suchen und Abrufen in einem Spreizbaum gespeichert werden.
• Graphalgorithmen: Spreizbäume können zur Implementierung von Diagrammalgorithmen verwendet werden, beispielsweise zum Finden des kürzesten Pfads in einem gewichteten Diagramm.
• Online Spielen: Splay Trees können im Online-Gaming zum Speichern und Verwalten von Highscores, Bestenlisten und Spielerstatistiken verwendet werden.

Klar, hier sind einige Vor- und Nachteile von Spreizbäumen sowie einige empfohlene Bücher, um mehr über das Thema zu erfahren:

Struktur in der Datenstruktur

Vorteile von Splay Trees:

Spreizbäume haben für viele Operationen eine amortisierte Zeitkomplexität von O(log n), wodurch sie in einigen Fällen schneller sind als viele andere ausgeglichene Baumdatenstrukturen.
Spreizbäume sind selbstjustierend, das heißt, sie balancieren sich automatisch aus, wenn Gegenstände eingefügt und entfernt werden. Dies kann dazu beitragen, Leistungseinbußen zu vermeiden, die auftreten können, wenn ein Baum aus dem Gleichgewicht gerät.

Nachteile von Spreizbäumen:

Splay-Bäume können für einige Operationen im ungünstigsten Fall eine Zeitkomplexität von O(n) aufweisen, wodurch sie weniger vorhersehbar sind als andere ausgeglichene Baumdatenstrukturen wie AVL-Bäume oder Rot-Schwarz-Bäume.
Für bestimmte Anwendungen, bei denen eine vorhersehbare Leistung erforderlich ist, sind Spreizbäume möglicherweise nicht geeignet.

Empfohlene Bücher zu Splay Trees:

Datenstrukturen und Algorithmenanalyse in Java von Mark Allen Weiss
Einführung in Algorithmen von Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein
Datenstrukturen und Algorithmen in C++ von Michael T. Goodrich und Roberto Tamassia

Abschluss:

Zusammenfassend lässt sich sagen, dass Splay Trees eine dynamische, selbstausgleichende binäre Suchbaum-Datenstruktur sind, die eine effiziente Möglichkeit zum Suchen, Einfügen und Löschen von Elementen bietet. Sie unterscheiden sich von herkömmlichen balancierten binären Suchbäumen wie AVL- und Rot-Schwarz-Bäumen dadurch, dass sie den Baum nach jeder Operation neu organisieren, um den zuletzt aufgerufenen Knoten zur Wurzel zu bringen. Dies trägt dazu bei, die Höhe des Baumes zu verringern und führt zu schnelleren Arbeitsabläufen. Splay Trees sind äußerst flexibel und können an verschiedene Anwendungsfälle angepasst werden. Obwohl sie möglicherweise einen höheren Rotationsaufwand verursachen, sind sie aufgrund ihrer Einfachheit und Vielseitigkeit nützliche Werkzeuge zur Lösung einer Vielzahl von Problemen.