logo

TechCodeview

Introduksjon til Splay-tredatastruktur

Splay tree er en selvjusterende binær søketredatastruktur, som betyr at trestrukturen justeres dynamisk basert på de åpnede eller innsatte elementene. Med andre ord omorganiserer treet seg selv slik at ofte åpnede eller innsatte elementer kommer nærmere rotnoden.

  1. Splaytreet ble først introdusert av Daniel Dominic Sleator og Robert Endre Tarjan i 1985. Det har en enkel og effektiv implementering som lar den utføre søke-, innsettings- og sletteoperasjoner i O(log n) amortisert tidskompleksitet, der n er antall elementer i treet.
  2. Den grunnleggende ideen bak splay-trær er å bringe det sist åpnede eller innsatte elementet til roten av treet ved å utføre en sekvens av trerotasjoner, kalt splaying. Splaying er en prosess for å restrukturere treet ved å gjøre det sist åpnede eller innsatte elementet til den nye roten og gradvis flytte de gjenværende nodene nærmere roten.
  3. Splay-trær er svært effektive i praksis på grunn av deres selvjusterende natur, noe som reduserer den totale tilgangstiden for ofte tilgang til elementer. Dette gjør dem til et godt valg for applikasjoner som krever raske og dynamiske datastrukturer, for eksempel cachingsystemer, datakomprimering og nettverksrutingsalgoritmer.
  4. Den største ulempen med splaytrær er imidlertid at de ikke garanterer en balansert trestruktur, noe som kan føre til ytelsesforringelse i verste fall. Splay-trær er heller ikke egnet for applikasjoner som krever garantert dårligst mulig ytelse, for eksempel sanntidssystemer eller sikkerhetskritiske systemer.

Samlet sett er splay-trær en kraftig og allsidig datastruktur som gir rask og effektiv tilgang til ofte åpnede eller innsatte elementer. De er mye brukt i ulike applikasjoner og gir en utmerket avveining mellom ytelse og enkelhet.



Et splay-tre er et selvbalanserende binært søketre, designet for effektiv tilgang til dataelementer basert på nøkkelverdiene deres.

  • Nøkkelfunksjonen til et splay-tre er at hver gang et element åpnes, flyttes det til roten av treet, og skaper en mer balansert struktur for påfølgende tilganger.
  • Splay-trær kjennetegnes ved bruk av rotasjoner, som er lokale transformasjoner av treet som endrer form, men bevarer rekkefølgen på elementene.
  • Rotasjoner brukes til å bringe det åpnede elementet til roten av treet, og også for å balansere treet på nytt hvis det blir ubalansert etter flere tilganger.

Operasjoner i et splay-tre:

  • Innsetting: For å sette inn et nytt element i treet, start med å utføre en vanlig binær søketreinnsetting. Bruk deretter rotasjoner for å bringe det nylig innsatte elementet til roten av treet.
  • Sletting : For å slette et element fra treet, finn det først ved hjelp av et binært søketresøk. Deretter, hvis elementet ikke har noen barn, fjerner du det. Hvis det har ett barn, forfrem det barnet til dets posisjon i treet. Hvis den har to barn, finn etterfølgeren til elementet (det minste elementet i dets høyre undertre), bytt nøkkelen med elementet som skal slettes, og slett etterfølgeren i stedet.
  • Søk : For å søke etter et element i treet, start med å utføre et binært søketresøk. Hvis elementet blir funnet, bruk rotasjoner for å bringe det til roten av treet. Hvis den ikke blir funnet, bruk rotasjoner på den siste noden som ble besøkt i søket, som blir den nye roten.
  • Rotasjon : Rotasjonene som brukes i et splay-tre er enten en Zig- eller en Zig-Zig-rotasjon. En Zig-rotasjon brukes til å bringe en node til roten, mens en Zig-Zig-rotasjon brukes til å balansere treet etter flere tilganger til elementer i samme undertre.

Her er en trinnvis forklaring av rotasjonsoperasjonene:

  • Zig-rotasjon : Hvis en node har et riktig barn, utfør en høyrerotasjon for å bringe det til roten. Hvis den har et venstre barn, utfør en venstrerotasjon.
  • Zig-Zig-rotasjon: Hvis en node har et barnebarn som også er barnets høyre eller venstre barn, utfør en dobbel rotasjon for å balansere treet. For eksempel, hvis noden har et høyre barn og det høyre barnet har et venstre barn, utfør en høyre-venstre rotasjon. Hvis noden har et venstre barn og det venstre barnet har et høyre barn, utfør en venstre-høyre rotasjon.
  • Merk: De spesifikke implementeringsdetaljene, inkludert de nøyaktige rotasjonene som brukes, kan variere avhengig av den eksakte formen til splaytreet.

Rotasjoner i Splay Tree

  • Zig-rotasjon
  • Zag Rotasjon
  • Zig – Zig-rotasjon
  • Zag – Zag Rotasjon
  • Zig – Zag Rotasjon
  • Zag – Zig-rotasjon

1) Zig-rotasjon:

Zig-rotasjonen i splay-trær fungerer på en måte som ligner den enkle høyrerotasjonen i AVL-trerotasjoner. Denne rotasjonen resulterer i at noder flytter én posisjon til høyre fra deres nåværende plassering. Tenk for eksempel på følgende scenario:

Zig-rotasjon (enkel rotasjon)



2) Zag-rotasjon:

Zag-rotasjonen i splay-trær fungerer på samme måte som den enkle venstrerotasjonen i AVL-trerotasjoner. Under denne rotasjonen skifter noder én posisjon til venstre fra deres nåværende plassering. Tenk for eksempel på følgende illustrasjon:

len av streng i java

Zag-rotasjon (enkel venstrerotasjon)

3) Zig-Zig-rotasjon:

Zig-Zig-rotasjonen i spredetrær er en dobbel sikkrotasjon. Denne rotasjonen resulterer i at noder skifter to posisjoner til høyre fra deres nåværende plassering. Ta en titt på følgende eksempel for en bedre forståelse:



Zig-Zig-rotasjon (dobbel høyrerotasjon)

4) Zag-Zag-rotasjon:

I splaytrær er Zag-Zag-rotasjonen en dobbel zag-rotasjon. Denne rotasjonen får noder til å flytte to posisjoner til venstre fra deres nåværende posisjon. For eksempel:

Zag-Zag-rotasjon (dobbel venstrerotasjon)

5) Zig-Zag-rotasjon:

Zig-Zag-rotasjonen i spredte trær er en kombinasjon av en sikk-rotasjon etterfulgt av en zag-rotasjon. Som et resultat av denne rotasjonen skifter noder en posisjon til høyre og deretter en posisjon til venstre fra deres nåværende plassering. Følgende illustrasjon gir en visuell representasjon av dette konseptet:

mysql ikke lik

Sikk-sakk rotasjon


6) Zag-Zig-rotasjon:

Zag-Zig-rotasjonen i spredte trær er en serie med zag-rotasjoner etterfulgt av en sikk-rotasjon. Dette resulterer i at noder flytter seg én posisjon til venstre, etterfulgt av en forskyvning én posisjon til høyre fra deres nåværende plassering. Følgende illustrasjon gir en visuell representasjon av dette konseptet:

Zag-Zig rotasjon

Nedenfor er C++-koden for å implementere rotasjoner i Splay-treet:

C++ 
#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->nøkkel = nøkkel;  node->venstre = node->høyre = nullptr;  retur node; } Node* rightRotate(Node* x) { Node* y = x->venstre;  x->venstre = y->høyre;  y->høyre = x;  returner y; } Node* venstreRoter(Node* x) { Node* y = x->høyre;  x->høyre = y->venstre;  y->venstre = x;  returner y; } Node* splay(Node* rot, int nøkkel) { if (rot == nullptr || rot->nøkkel == nøkkel) returner rot;  if (root->key> key) { if (root->venstre == nullptr) returner rot;  if (rot->venstre->tast>tast) { rot->venstre->venstre = splay(rot->venstre->venstre, nøkkel);  rot = høyreRoter(rot);  } annet hvis (root->venstre->tast< key) {  root->venstre->høyre = splay(root->venstre->høyre, nøkkel);  if (rot->venstre->høyre != nullptr) rot->venstre = venstreRoter(rot->venstre);  } returnere (root->venstre == nullptr) ? rot : høyreRoter(rot);  } else { if (root->right == nullptr) returner root;  if (rot->høyre->tast>tast) { rot->høyre->venstre = splay(root->høyre->venstre, nøkkel);  if (rot->høyre->venstre != nullptr) rot->høyre = høyreRoter(rot->høyre);  } annet hvis (root->høyre->tast< key) {  root->høyre->høyre = splay(root->høyre->høyre, nøkkel);  rot = venstreRoter(rot);  } return (root->right == nullptr) ? rot : venstreRoter(rot);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  root = splay(rot, nøkkel);  if (rot->nøkkel == nøkkel) returner rot;  Node* node = nyNode(nøkkel);  if (root->key> key) { node->right = rot;  node->venstre = rot->venstre;  root->venstre = nullptr;  } annet { node->venstre = rot;  node->høyre = rot->høyre;  root->right = nullptr;  } returnode; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->nøkkel<< ' ';  preOrder(node->venstre);  forhåndsbestilling(node->høyre);  } } int main() { Node* 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) returner root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  rot = høyreRoter(rot);  } annet hvis (root.venstre.tast< 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);  } annet hvis (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>nøkkel) { node.right = rot;  node.left = rot.venstre;  root.left = null;  } annet { node.left = rot;  node.right = rot.høyre;  root.right = null;  } returnode;  } static void preOrder(Node node) { if (node ​​!= null) { System.out.println();  System.out.print(node.key + ' ');  forhåndsbestilling(node.venstre);  forhåndsbestilling(node.høyre);  } } public static void main(String[] args) { Node rot = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  System.out.println('Forhåndsbestill gjennomgang av det modifiserte Splay-treet:');  forhåndsbestilling(root);  } } // Denne koden er bidratt 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>nøkkel: hvis root.left er Ingen: returner rot hvis root.left.key> nøkkel: 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>nøkkel: node.right = root node.left = root.left root.left = Ingen andre: node.left = root node.right = root.right root.right = Ingen returnode def pre_order(node): if node: print (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__main__': root = Ingen rot = insert(root, 100) root = insert(root) , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Forhåndsbestill gjennomgang av det modifiserte Splay-treet:') 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) returner root;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  rot = høyreRoter(rot);  } annet hvis (root.venstre.tast< 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);  } annet hvis (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>nøkkel) { node.right = rot;  node.left = rot.venstre;  root.left = null;  } annet { node.left = rot;  node.right = rot.høyre;  root.right = null;  } returnode;  } static void preOrder(Node node) { if (node ​​!= null) { Console.Write(node.key + ' ');  forhåndsbestilling(node.venstre);  forhåndsbestilling(node.høyre);  } } offentlig statisk tomrom Main(streng[] args) { Noderot = null;  root = insert(root, 100);  root = insert(root, 50);  root = insert(root, 200);  root = insert(root, 40);  root = insert(root, 60);  Console.WriteLine( 'Forhåndsbestill gjennomgang av det modifiserte Splay-treet:');  forhåndsbestilling(root);  } } // Denne koden er bidratt 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);  } annet hvis (root.venstre.tast< 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);  } } annet hvis (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>nøkkel) { node.right = rot;  node.left = rot.venstre;  root.left = null;  } annet { node.left = rot;  node.right = rot.høyre;  root.right = null;  } returnode;  } static preOrder(node) { if (node ​​!= null) { console.log(node.key + ' ');  SplayTree.preOrder(node.venstre);  SplayTree.preOrder(node.right);  } } } la 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('Forhåndsbestill gjennomgang av det modifiserte Splay-treet:'); SplayTree.preOrder(root); // Koden er bidratt av Nidhi goel.>
Produksjon 
Preorder traversal of the modified Splay tree:>

Ulemper med splay tree datastruktur:

  • Ubalanserte trær: Splay-trær kan bli ubalanserte og ineffektive hvis treet roteres gjentatte ganger i samme retning.
  • Minnebruk: Splay-trær kan bruke mye minne sammenlignet med andre datastrukturer fordi hver node inneholder tilleggsinformasjon.
  • Kompleksitet: Splay-trær kan ha høy tidskompleksitet for grunnleggende operasjoner som innsetting og sletting fordi trærne må omorganiseres etter hver operasjon.
  • Omorganiseringskostnader: Spredningsoperasjonen som kreves i hver operasjon kan være tidkrevende og resultere i høy overhead.
  • Tilfeller med begrenset bruk : Splay-trær er ikke egnet for alle datastrukturer og har begrensede brukstilfeller fordi de ikke håndterer dupliserte nøkler effektivt.

Bruksområder for splaytreet:

  • Buffer : Splay-trær kan brukes til å implementere cache-minneadministrasjon, der de mest brukte elementene flyttes til toppen av treet for raskere tilgang.
  • Databaseindeksering : Splay-trær kan brukes til å indeksere databaser for raskere søk og gjenfinning av data.
  • Filsystemer : Splay-trær kan brukes til å lagre filsystemmetadata, for eksempel allokeringstabell, katalogstruktur og filattributter.
  • Datakomprimering: Splay-trær kan brukes til å komprimere data ved å identifisere og kode repeterende mønstre.
  • Tekstbehandling : Splay-trær kan brukes i tekstbehandlingsapplikasjoner, for eksempel stavekontroll, der ord lagres i et splay-tre for raskt søk og gjenfinning.
  • Grafalgoritmer: Splay-trær kan brukes til å implementere grafalgoritmer, for eksempel å finne den korteste veien i en vektet graf.
  • Nettspill: Splay-trær kan brukes i nettspill for å lagre og administrere høye poengsummer, topplister og spillerstatistikk.

Jada, her er noen fordeler og ulemper med splay-trær, samt noen anbefalte bøker for å lære mer om emnet:

Fordeler med Splay Trees:

Splay-trær har amortisert tidskompleksitet O(log n) for mange operasjoner, noe som gjør dem raskere enn mange andre balanserte tredatastrukturer i noen tilfeller.
Splay-trær er selvjusterende, noe som betyr at de automatisk balanserer seg selv når gjenstander settes inn og fjernes. Dette kan bidra til å unngå ytelsesdegraderingen som kan oppstå når et tre blir ubalansert.

Ulemper med Splay Trees:

Splay-trær kan i verste fall ha tidskompleksitet O(n) for enkelte operasjoner, noe som gjør dem mindre forutsigbare enn andre balanserte tredatastrukturer som AVL-trær eller rød-svarte trær.
Splay-trær er kanskje ikke egnet for visse bruksområder der forutsigbar ytelse er nødvendig.

Anbefalte bøker om Splay Trees:

Datastrukturer og algoritmeanalyse i Java av Mark Allen Weiss
Introduksjon til algoritmer av Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest og Clifford Stein
Datastrukturer og algoritmer i C++ av Michael T. Goodrich og Roberto Tamassia

Konklusjon:

Avslutningsvis er Splay Trees en dynamisk selvbalanserende binær søketredatastruktur som gir en effektiv måte å søke, sette inn og slette elementer på. De skiller seg fra tradisjonelle balanserte binære søketrær som AVL og rød-svarte trær, ettersom de omorganiserer treet etter hver operasjon for å bringe den nylig åpnede noden til roten. Dette bidrar til å redusere høyden på treet og resulterer i raskere operasjoner. Splay Trees er svært fleksible og kan tilpasses ulike bruksområder. Selv om de kan ha høyere overhead når det gjelder rotasjoner, gjør deres enkelhet og allsidighet dem nyttige verktøy for å løse et bredt spekter av problemer.

windows.open javascript