logo

TechCodeview

Introduktion till Splay-trädets datastruktur

Splay tree är en självjusterande binär sökträdsdatastruktur, vilket innebär att trädstrukturen justeras dynamiskt baserat på de accessade eller infogade elementen. Med andra ord, trädet omorganiserar sig automatiskt så att ofta åtkomliga eller infogade element kommer närmare rotnoden.

  1. Splayträdet introducerades först av Daniel Dominic Sleator och Robert Endre Tarjan 1985. Det har en enkel och effektiv implementering som gör att den kan utföra sökning, infogning och radering i O(log n) amorterad tidskomplexitet, där n är antal element i trädet.
  2. Grundidén bakom spridningsträd är att föra det senast öppnade eller infogade elementet till roten av trädet genom att utföra en sekvens av trädrotationer, kallad spridning. Splaying är en process för att omstrukturera trädet genom att göra det senast öppnade eller infogade elementet till den nya roten och gradvis flytta de återstående noderna närmare roten.
  3. Splayträd är mycket effektiva i praktiken på grund av sin självjusterande natur, vilket minskar den totala åtkomsttiden för ofta åtkomliga element. Detta gör dem till ett bra val för applikationer som kräver snabba och dynamiska datastrukturer, såsom cachningssystem, datakomprimering och nätverksroutingalgoritmer.
  4. Den största nackdelen med splayträd är dock att de inte garanterar en balanserad trädstruktur, vilket kan leda till prestandaförsämring i värsta fall. Dessutom är splay trees inte lämpliga för applikationer som kräver garanterad prestanda i värsta fall, såsom realtidssystem eller säkerhetskritiska system.

Sammantaget är splay trees en kraftfull och mångsidig datastruktur som erbjuder snabb och effektiv åtkomst till ofta åtkomliga eller infogade element. De används ofta i olika applikationer och ger en utmärkt avvägning mellan prestanda och enkelhet.



Ett splayträd är ett självbalanserande binärt sökträd, designat för effektiv åtkomst till dataelement baserat på deras nyckelvärden.

  • Nyckelfunktionen i ett splayträd är att varje gång ett element öppnas flyttas det till roten av trädet, vilket skapar en mer balanserad struktur för efterföljande åtkomster.
  • Splayträd kännetecknas av att de använder rotationer, som är lokala transformationer av trädet som ändrar form men bevarar ordningen på elementen.
  • Rotationer används för att föra det åtkomliga elementet till roten av trädet, och även för att balansera om trädet om det blir obalanserat efter flera åtkomster.

Operationer i ett splayträd:

  • Införande: För att infoga ett nytt element i trädet, börja med att utföra en vanlig binär sökträdsinsättning. Använd sedan rotationer för att föra det nyinsatta elementet till trädets rot.
  • Radering : För att ta bort ett element från trädet, leta först upp det med en binär sökträdsökning. Sedan, om elementet inte har några barn, ta helt enkelt bort det. Om det har ett barn, främja det barnet till dess position i trädet. Om det har två underordnade element, hitta efterföljaren till elementet (det minsta elementet i dess högra underträd), byt nyckeln mot elementet som ska raderas och ta bort efterföljaren istället.
  • Sök : För att söka efter ett element i trädet, börja med att utföra en binär sökträdsökning. Om elementet hittas, använd rotationer för att föra det till roten av trädet. Om den inte hittas, tillämpa rotationer på den senast besökta noden i sökningen, som blir den nya roten.
  • Rotation : Rotationerna som används i ett splayträd är antingen en Zig- eller en Zig-Zig-rotation. En Zig-rotation används för att föra en nod till roten, medan en Zig-Zig-rotation används för att balansera trädet efter flera åtkomster till element i samma underträd.

Här är en steg-för-steg förklaring av rotationsoperationerna:

  • Zig rotation : Om en nod har ett rätt barn, utför en högerrotation för att föra den till roten. Om den har ett vänsterbarn, utför en vänsterrotation.
  • Zig-Zig Rotation: Om en nod har ett barnbarn som också är barnets högra eller vänstra barn, utför en dubbelrotation för att balansera trädet. Till exempel, om noden har ett höger barn och det högra barnet har ett vänster barn, utför en höger-vänster rotation. Om noden har ett vänster barn och det vänstra barnet har ett höger barn, utför en vänster-höger-rotation.
  • Notera: De specifika implementeringsdetaljerna, inklusive de exakta rotationer som används, kan variera beroende på den exakta formen av splayträdet.

Rotationer i Splay Tree

  • Zig rotation
  • Zag Rotation
  • Zig – Zig Rotation
  • Zag – Zag Rotation
  • Zig – Zag Rotation
  • Zag – Zig Rotation

1) Zig-rotation:

Zig-rotationen i splayträd fungerar på ett sätt som liknar den enkla högerrotationen i AVL-trädrotationer. Denna rotation resulterar i att noder flyttar en position åt höger från sin nuvarande plats. Tänk till exempel på följande scenario:

Zig-rotation (enkel rotation)



2) Zag Rotation:

Zag-rotationen i splayträd fungerar på ett liknande sätt som den enda vänsterrotationen i AVL-trädrotationer. Under denna rotation flyttar noder en position till vänster från sin nuvarande plats. Tänk till exempel på följande illustration:

udp-protokoll

Zag Rotation (Enkel vänsterrotation)

3) Zig-Zig-rotation:

Zig-Zig-rotationen i splayträd är en dubbel zig-rotation. Denna rotation resulterar i att noder flyttar två positioner åt höger från sin nuvarande plats. Ta en titt på följande exempel för en bättre förståelse:



Zig-Zig-rotation (dubbel högerrotation)

4) Zag-Zag-rotation:

I splayträd är Zag-Zag Rotation en dubbel zagrotation. Denna rotation får noder att flytta två positioner till vänster från sin nuvarande position. Till exempel:

java arraylist sortering

Zag-Zag-rotation (dubbel vänsterrotation)

5) Zig-Zag-rotation:

Zig-Zag-rotationen i splayträd är en kombination av en zig-Zag-rotation följt av en zag-rotation. Som ett resultat av denna rotation skiftar noder en position till höger och sedan en position till vänster från sin nuvarande plats. Följande illustration ger en visuell representation av detta koncept:

Zig-Zag rotation


6) Zag-Zig Rotation:

Zag-Zig-rotationen i splayträd är en serie av zag-rotationer följt av en zig-rotation. Detta resulterar i att noder flyttar en position till vänster, följt av en förskjutning en position till höger från sin nuvarande plats. Följande illustration ger en visuell representation av detta koncept:

Zag-Zig Rotation

Nedan är C++-koden för att implementera rotationer i Splay-trädet:

C++ 
#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->nyckel = nyckel;  nod->vänster = nod->höger = nullptr;  returnod; } Nod* rightRotate(Node* x) { Node* y = x->left;  x->vänster = y->höger;  y->höger = x;  returnera y; } Nod* leftRotate(Node* x) { Node* y = x->right;  x->höger = y->vänster;  y->vänster = x;  returnera y; } Nod* splay(Nod* rot, int nyckel) { if (rot == nullptr || rot->nyckel == nyckel) returnerar rot;  if (rot->nyckel> nyckel) { if (rot->vänster == nullptr) returnerar rot;  if (root->vänster->tangent>tangent) { root->vänster->vänster = splay(root->vänster->vänster, nyckel);  root = rightRotate(root);  } annat om (root->vänster->tangent< key) {  root->vänster->höger = splay(root->vänster->höger, nyckel);  if (rot->vänster->höger != nullptr) rot->vänster = vänsterRotera(rot->vänster);  } returnera (root->vänster == nullptr) ? root : rightRotate(root);  } else { if (root->right == nullptr) returnerar root;  if (root->höger->tangent>tangent) { root->höger->vänster = splay(root->höger->vänster, nyckel);  if (root->höger->vänster != nullptr) root->höger = högerRotera(root->höger);  } annat om (root->höger->tangent< key) {  root->höger->höger = splay(root->höger->höger, nyckel);  root = leftRotate(root);  } returnera (root->right == nullptr) ? root : leftRotate(root);  } } Node* insert(Node* rot, int nyckel) { if (root == nullptr) returnera nyNode(nyckel);  root = splay(root, nyckel);  if (rot->nyckel == nyckel) returnerar rot;  Nod* nod = newNode(nyckel);  if (rot->nyckel> nyckel) { nod->höger = rot;  nod->vänster = rot->vänster;  root->vänster = nullptr;  } annat { nod->vänster = rot;  nod->höger = rot->höger;  root->right = nullptr;  } returnod; } void preOrder(Node* node) { if (nod != nullptr) { cout<< node->nyckel<< ' ';  preOrder(node->vänster);  preOrder(nod->höger);  } } int main() { Nod* rot = 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) returnerar root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  root = rightRotate(root);  } annat om (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);  } annat om (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>nyckel) { node.right = rot;  node.left = root.left;  root.left = null;  } annat { node.left = rot;  node.right = rot.höger;  root.right = null;  } returnod;  } static void preOrder(Node node) { if (nod != null) { System.out.println();  System.out.print(nod.nyckel + ' ');  förbeställning(nod.vänster);  förbeställning(nod.höger);  } } public static void main(String[] args) { Nodrot = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  System.out.println('Förbeställ genomgång av det modifierade Splay-trädet:');  förbeställning(root);  } } // Denna kod är bidragit av 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>nyckel: om root.left är Ingen: returnera root om root.left.key> nyckel: 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>nyckel: root.right.left = splay(root.right.left, key) om 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>nyckel: node.right = rot node.left = root.left root.left = Ingen annan: node.left = rot node.right = root.right root.right = Ingen returnod def pre_order(nod): if nod: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Ingen rot = infoga(root, 100) root = infoga(root) , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Förbeställ genomgång av det modifierade Splay-trädet:') 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) returnerar root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  root = rightRotate(root);  } annat om (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);  } annat om (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>nyckel) { node.right = rot;  node.left = root.left;  root.left = null;  } annat { node.left = rot;  node.right = rot.höger;  root.right = null;  } returnod;  } static void preOrder(Node node) { if (nod != null) { Console.Write(node.key + ' ');  förbeställning(nod.vänster);  förbeställning(nod.höger);  } } public static void Main(string[] args) { Nodrot = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  Console.WriteLine( 'Förbeställ genomgång av det modifierade Splay-trädet:');  förbeställning(root);  } } // Denna kod är bidragit av Prince 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>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);  } annat om (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, nyckel);  if (root.right.left != null) { root.right = SplayTree.rightRotate(root.right);  } } annat om (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>nyckel) { node.right = rot;  node.left = root.left;  root.left = null;  } annat { node.left = rot;  node.right = rot.höger;  root.right = null;  } returnod;  } static preOrder(nod) { if (nod != null) { console.log(nod.nyckel + ' ');  SplayTree.preOrder(node.left);  SplayTree.preOrder(node.right);  } } } låt 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('Förbeställ genomgång av det modifierade Splay-trädet:'); SplayTree.preOrder(root); // Koden är bidragit av Nidhi goel.>
Produktion 
Preorder traversal of the modified Splay tree:>

Nackdelar med splay tree datastruktur:

  • Obalanserade träd: Splayträd kan bli obalanserade och ineffektiva om trädet upprepade gånger roteras i samma riktning.
  • Minnesanvändning: Splay-träd kan använda mycket minne jämfört med andra datastrukturer eftersom varje nod innehåller ytterligare information.
  • Komplexitet: Splayträd kan ha en hög tidskomplexitet för grundläggande operationer som infogning och borttagning eftersom träden behöver omorganiseras efter varje operation.
  • Omorganisationskostnader: Den spridningsoperation som krävs vid varje operation kan vara tidskrävande och resultera i höga omkostnader.
  • Begränsad användning : Splayträd är inte lämpliga för alla datastrukturer och har begränsade användningsfall eftersom de inte hanterar dubbletter av nycklar effektivt.

Tillämpningar av splayträdet:

  • Cachning : Splay-träd kan användas för att implementera cacheminneshantering, där de mest åtkomliga objekten flyttas till toppen av trädet för snabbare åtkomst.
  • Databasindexering : Splay-träd kan användas för att indexera databaser för snabbare sökning och hämtning av data.
  • Filsystem : Splay-träd kan användas för att lagra filsystemmetadata, såsom allokeringstabell, katalogstruktur och filattribut.
  • Datakomprimering: Splay-träd kan användas för att komprimera data genom att identifiera och koda upprepade mönster.
  • Textbearbetning : Splay-träd kan användas i textbearbetningsapplikationer, som stavningskontroller, där ord lagras i ett splayträd för snabb sökning och hämtning.
  • Grafalgoritmer: Splay-träd kan användas för att implementera grafalgoritmer, som att hitta den kortaste vägen i en viktad graf.
  • Online-spelande: Splayträd kan användas i onlinespel för att lagra och hantera höga poäng, topplistor och spelarstatistik.

Visst, här är några fördelar och nackdelar med splayträd, samt några rekommenderade böcker för att lära dig mer om ämnet:

Java-exempelprogram

Fördelar med Splay Trees:

Splayträd har amorterad tidskomplexitet O(log n) för många operationer, vilket gör dem snabbare än många andra balanserade träddatastrukturer i vissa fall.
Splayträd är självjusterande, vilket innebär att de automatiskt balanserar sig själva när föremål sätts in och tas bort. Detta kan hjälpa till att undvika den prestandaförsämring som kan uppstå när ett träd blir obalanserat.

Nackdelar med Splay Trees:

Splayträd kan ha värsta tänkbara tidskomplexitet O(n) för vissa operationer, vilket gör dem mindre förutsägbara än andra balanserade träddatastrukturer som AVL-träd eller röd-svarta träd.
Splay trees kanske inte är lämpliga för vissa applikationer där förutsägbar prestanda krävs.

Rekommenderade böcker om Splay Trees:

Datastrukturer och algoritmanalys i Java av Mark Allen Weiss
Introduktion till algoritmer av Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest och Clifford Stein
Datastrukturer och algoritmer i C++ av Michael T. Goodrich och Roberto Tamassia

Slutsats:

Sammanfattningsvis är Splay Trees en dynamisk självbalanserande binär sökträdsdatastruktur som ger ett effektivt sätt att söka, infoga och ta bort element. De skiljer sig från traditionella balanserade binära sökträd som AVL och röd-svarta träd, eftersom de omorganiserar trädet efter varje operation för att föra den nyligen öppnade noden till roten. Detta hjälper till att minska höjden på trädet och resulterar i snabbare operationer. Splay Trees är mycket flexibla och kan anpassas till olika användningsfall. Även om de kan ha högre omkostnader när det gäller rotationer, gör deras enkelhet och mångsidighet dem användbara verktyg för att lösa ett brett spektrum av problem.