logo

TechCodeview

Ievads Splay koka datu struktūrā

Splay koks ir pašregulējoša binārā meklēšanas koka datu struktūra, kas nozīmē, ka koka struktūra tiek dinamiski pielāgota, pamatojoties uz piekļūtajiem vai ievietotajiem elementiem. Citiem vārdiem sakot, koks automātiski pārkārtojas tā, lai bieži piekļūti vai ievietotie elementi kļūtu tuvāk saknes mezglam.

  1. Atvēršanas koku pirmo reizi ieviesa Daniels Dominiks Sleators un Roberts Endre Tarjans 1985. gadā. Tam ir vienkārša un efektīva ieviešana, kas ļauj veikt meklēšanas, ievietošanas un dzēšanas darbības O(log n) amortizētā laika sarežģītībā, kur n ir elementu skaits kokā.
  2. Izvēršanas koku pamatideja ir nogādāt koka saknē pēdējo piekļuvi vai ievietoto elementu, veicot koka apgriezienu secību, ko sauc par izkliedēšanu. Atvēršana ir koka pārstrukturēšanas process, padarot pēdējo piekļūto vai ievietoto elementu par jauno sakni un pakāpeniski pārvietojot atlikušos mezglus tuvāk saknei.
  3. Izliekuma koki praksē ir ļoti efektīvi, pateicoties to pašregulējošajam raksturam, kas samazina kopējo piekļuves laiku bieži piekļūstamiem elementiem. Tas padara tos par labu izvēli lietojumprogrammām, kurām nepieciešamas ātras un dinamiskas datu struktūras, piemēram, kešatmiņas sistēmām, datu saspiešanai un tīkla maršrutēšanas algoritmiem.
  4. Tomēr galvenais izplešanās koku trūkums ir tas, ka tie negarantē līdzsvarotu koku struktūru, kas var izraisīt veiktspējas pasliktināšanos sliktākajā gadījumā. Arī šķelšanās koki nav piemēroti lietojumprogrammām, kurām nepieciešama garantēta sliktākā gadījuma veiktspēja, piemēram, reāllaika sistēmām vai drošības ziņā kritiskām sistēmām.

Kopumā izvietošanas koki ir jaudīga un daudzpusīga datu struktūra, kas piedāvā ātru un efektīvu piekļuvi bieži piekļūtiem vai ievietotiem elementiem. Tos plaši izmanto dažādās lietojumprogrammās un nodrošina lielisku kompromisu starp veiktspēju un vienkāršību.



Atvēršanas koks ir pašlīdzsvarojošs binārais meklēšanas koks, kas paredzēts efektīvai piekļuvei datu elementiem, pamatojoties uz to galvenajām vērtībām.

  • Izvēršanas koka galvenā iezīme ir tāda, ka katru reizi, kad tiek piekļūts elementam, tas tiek pārvietots uz koka sakni, radot līdzsvarotāku struktūru turpmākajām piekļūšanas reizēm.
  • Spilgtajiem kokiem ir raksturīga rotāciju izmantošana, kas ir lokālas koka transformācijas, kas maina tā formu, bet saglabā elementu kārtību.
  • Rotācijas tiek izmantotas, lai nogādātu pieejamo elementu līdz koka saknei, kā arī lai līdzsvarotu koku, ja pēc vairākkārtējas piekļuves tas kļūst nelīdzsvarots.

Darbības splay kokā:

  • Ievietošana: Lai kokā ievietotu jaunu elementu, sāciet ar parastu binārās meklēšanas koka ievietošanu. Pēc tam veiciet rotācijas, lai tikko ievietotais elements nonāktu koka saknē.
  • Dzēšana : lai dzēstu elementu no koka, vispirms atrodiet to, izmantojot bināro meklēšanu kokā. Pēc tam, ja elementam nav bērnu, vienkārši noņemiet to. Ja tam ir viens bērns, paaugstiniet šo bērnu uz viņa vietu kokā. Ja tam ir divi pakārtoti, atrodiet elementa pēcteci (mazākais elements tā labajā apakškokā), nomainiet tā atslēgu ar dzēšamo elementu un tā vietā izdzēsiet pēcteci.
  • Meklēt : lai kokā meklētu elementu, sāciet, veicot bināro meklēšanu kokā. Ja elements ir atrasts, veiciet apgriezienus, lai to nogādātu līdz koka saknei. Ja tas netiek atrasts, piemērojiet rotācijas pēdējam meklētajam mezglam, kas kļūst par jauno sakni.
  • Rotācija : Rotācijas, kas tiek izmantotas zig-ziga formātā, ir vai nu Zig-Zig. Zig rotācija tiek izmantota, lai mezglu novirzītu uz sakni, savukārt Zig-Zig rotācija tiek izmantota, lai līdzsvarotu koku pēc vairākkārtējas piekļuves tā paša apakškoka elementiem.

Šeit ir detalizēts rotācijas darbību skaidrojums:

  • Zig Rotācija : Ja mezglam ir pareizais atvasinājums, veiciet pareizo pagriešanu, lai to novirzītu uz sakni. Ja tai ir kreisais bērns, veiciet rotāciju pa kreisi.
  • Zig-Zig rotācija: Ja mezglam ir mazbērns, kas ir arī tā bērna labais vai kreisais bērns, veiciet dubultu rotāciju, lai līdzsvarotu koku. Piemēram, ja mezglam ir labais bērns un labajam bērnam ir kreisais bērns, veiciet rotāciju pa labi un pa kreisi. Ja mezglam ir kreisais bērns un kreisajam bērnam ir labais bērns, veiciet rotāciju no kreisās uz labo pusi.
  • Piezīme: Konkrētās ieviešanas detaļas, tostarp precīzas izmantotās rotācijas, var atšķirties atkarībā no precīzas izkliedēšanas koka formas.

Rotācijas programmā Splay Tree

  • Zig Rotācija
  • Zag Rotation
  • Zig – Zig Rotation
  • Zag — Zag Rotation
  • Zig – Zag Rotation
  • Zag – Zig Rotation

1) Zig rotācija:

Zig Rotation izliekuma kokos darbojas līdzīgi kā viena rotācija pa labi AVL Tree rotācijās. Šīs rotācijas rezultātā mezgli pārvietojas par vienu pozīciju pa labi no pašreizējās atrašanās vietas. Piemēram, apsveriet šādu scenāriju:

Zig Rotation (viena rotācija)



2) Zag Rotation:

Zag Rotation šķelšanās kokos darbojas līdzīgi kā viena rotācija pa kreisi AVL Tree rotācijās. Šīs rotācijas laikā mezgli pārbīda vienu pozīciju pa kreisi no pašreizējās atrašanās vietas. Piemēram, apsveriet šādu ilustrāciju:

java kolekciju ietvars

Zag Rotation (viena pagriešana pa kreisi)

3) Zig-Zig rotācija:

Zig-Zig Rotation splay kokos ir dubultā zig rotācija. Šīs rotācijas rezultātā mezgli pārvietojas divas pozīcijas pa labi no to pašreizējās atrašanās vietas. Apskatiet šo piemēru, lai labāk izprastu:



Vijay filmu aktieris

Zig-Zig rotācija (dubultā pa labi)

4) Zag-Zag rotācija:

Izplešanās kokos Zag-Zag Rotation ir dubultā zag rotācija. Šī rotācija liek mezgliem pārvietot divas pozīcijas pa kreisi no pašreizējās pozīcijas. Piemēram:

Zag-Zag rotācija (dubultā pagriešana pa kreisi)

5) Zig-Zag rotācija:

Zig-Zag Rotation šķelšanās kokos ir zig rotācijas kombinācija, kam seko zagveida rotācija. Šīs rotācijas rezultātā mezgli no pašreizējās atrašanās vietas nobīda vienu pozīciju pa labi un pēc tam vienu pozīciju pa kreisi. Sekojošā ilustrācija sniedz vizuālu šīs koncepcijas attēlojumu:

Zig-Zag rotācija


6) Zag-Zig rotācija:

Zag-Zig Rotation šķelšanās kokos ir virkne zag rotāciju, kam seko zig rotācija. Tā rezultātā mezgli pārvietojas par vienu pozīciju pa kreisi, kam seko viena pozīcija pa labi no pašreizējās atrašanās vietas. Sekojošā ilustrācija piedāvā vizuālu šīs koncepcijas attēlojumu:

Zag-Zig rotācija

Zemāk ir C++ kods, lai ieviestu rotācijas Splay kokā:

C++ 
#include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->atslēga = atslēga;  mezgls->pa kreisi = mezgls->pa labi = nullptr;  atgriešanās mezgls; } Node* rightRotate(Node* x) { Node* y = x->left;  x->pa kreisi = y->pa labi;  y->pa labi = x;  atgriezt y; } Node* leftRotate(Node* x) { Node* y = x->right;  x->pa labi = y->pa kreisi;  y->pa kreisi = x;  atgriezt 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 (sakne->kreisais->taustiņš> taustiņš) { sakne->kreisais->pa kreisi = splay(root->left->left, key);  sakne = pa labiPagriezt(sakne);  } else if (root->left->key< key) {  root->pa kreisi->pa labi = splay(sakne->kreisais->pa labi, taustiņš);  if (root->left->right != nullptr) root->left = leftRotate(root->left);  } return (root->left == nullptr)? sakne : pa labiPagriezt(sakne);  } else { if (root->right == nullptr) return root;  if (sakne->labais->taustiņš> taustiņš) { sakne->labais->pa kreisi = splay(sakne->labais->pa kreisi, taustiņš);  if (sakne->labais->pa kreisi != nullptr) root->right = rightRotate(root->right);  } else if (root->right-> key< key) {  root->pa labi->pa labi = splay(sakne->labais->labais, taustiņš);  sakne = pa kreisiPagriezt(sakne);  } return (root->right == nullptr) ? sakne : pa kreisiPagriezt(sakne);  } } Node* insert(Node* root, int key) { if (root == nullptr) return newNode(key);  sakne = splay(sakne, atslēga);  if (root->key == atslēga) atgriež sakni;  Mezgls* mezgls = jaunsMezgls(atslēga);  if (root->key> key) { mezgls->labais = sakne;  mezgls->pa kreisi = sakne->pa kreisi;  sakne->pa kreisi = nullptr;  } else { mezgls->pa kreisi = sakne;  mezgls->labais = sakne->pa labi;  sakne->pa labi = nullptr;  } atgriešanas mezgls; } void preOrder(Node* node) { if (node ​​!= nullptr) { cout<< node->taustiņu<< ' ';  preOrder(node->pa kreisi);  preOrder(mezgls->pa labi);  } } int main() { Mezgls* sakne = nullptr;  sakne = ievietot(sakne, 100);  sakne = ievietot(sakne, 50);  sakne = ievietot(sakne, 200);  sakne = ievietot(sakne, 40);  sakne = ievietot(sakne, 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>taustiņš) { if (root.left == null) return root;  if (root.left.key> taustiņš) { root.left.left = splay(root.left.left, key);  sakne = pa labiPagriezt(sakne);  } 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>taustiņš) { 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>atslēga) { node.right = sakne;  node.left = root.left;  root.left = null;  } else { node.left = sakne;  node.right = root.right;  root.right = null;  } atgriešanas mezgls;  } static void preOrder(Node node) { if (mezgls != null) { System.out.println();  System.out.print(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void main(String[] args) { Mezgla sakne = null;  sakne = ievietot(sakne, 100);  sakne = ievietot(sakne, 50);  sakne = ievietot(sakne, 200);  sakne = ievietot(sakne, 40);  sakne = ievietot(sakne, 60);  System.out.println('Modificētā Splay koka priekšpasūtīšana:');  preOrder(root);  } } // Šī koda autors ir 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>atslēga: ja root.left ir Nav: atgriezt sakni if ​​root.left.key> atslēga: 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>taustiņš: 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>atslēga: node.right = root node.left = root.left root.left = Nekas cits: node.left = saknes node.right = root.right root.right = Nav atgriezt mezglu def pre_order(node): ja mezgls: drukāt (node.key, end=' ') pre_order(node.left) pre_order(node.right) if __name__ == '__galvenais__': root = Nav root = ievietot(sakne, 100) sakne = ievietot(sakne , 50) root = insert(root, 200) root = insert(root, 40) root = insert(root, 60) print('Modificētā Splay koka priekšpasūtīšana:') 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>taustiņš) { if (root.left == null) return root;  if (root.left.key> taustiņš) { root.left.left = splay(root.left.left, key);  sakne = pa labiPagriezt(sakne);  } 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>taustiņš) { 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>atslēga) { node.right = sakne;  node.left = root.left;  root.left = null;  } else { node.left = sakne;  node.right = root.right;  root.right = null;  } atgriešanas mezgls;  } static void preOrder(Node node) { if (mezgls != null) { Console.Write(node.key + ' ');  preOrder(node.left);  preOrder(node.right);  } } public static void Main(string[] args) { Mezgla sakne = null;  sakne = ievietot(sakne, 100);  sakne = ievietot(sakne, 50);  sakne = ievietot(sakne, 200);  sakne = ievietot(sakne, 40);  sakne = ievietot(sakne, 60);  Console.WriteLine( 'Iepriekšpasūtīt modificētā Splay koka šķērsošanu:');  preOrder(root);  } } // Šo kodu ir sagatavojis princis Kumars>>Javascript>  
  Izvade      Nelīdzsvaroti koki:    Atkārtoti pagriežot koku vienā virzienā, koki var kļūt nelīdzsvaroti un neefektīvi.
  •     Atmiņas lietojums:    Splay koki var izmantot daudz atmiņas, salīdzinot ar citām datu struktūrām, jo ​​katrs mezgls satur papildu informāciju.
  •     Sarežģītība:    Atvēršanas koki var būt ļoti sarežģīti pamata darbībām, piemēram, ievietošanai un dzēšanai, jo koki ir jāpārkārto pēc katras darbības.
  •     Reorganizācijas pieskaitāmās izmaksas:    Katrai darbībai nepieciešamā izgriešanas darbība var būt laikietilpīga un radīt lielas pieskaitāmās izmaksas.
  •     Ierobežotas lietošanas gadījumi    : Splay koki nav piemēroti visām datu struktūrām, un to izmantošanas gadījumi ir ierobežoti, jo tie efektīvi neapstrādā dublētās atslēgas.
    • Splay koka pielietojumi:
    •     Kešatmiņa    : Splay kokus var izmantot, lai ieviestu kešatmiņas pārvaldību, kur visbiežāk pieejamie vienumi tiek pārvietoti uz koka augšdaļu, lai nodrošinātu ātrāku piekļuvi.
    •     Datu bāzes indeksācija    : Splay kokus var izmantot datu bāzu indeksēšanai ātrākai datu meklēšanai un izguvei.
    •     Failu sistēmas    : Splay kokus var izmantot, lai saglabātu failu sistēmas metadatus, piemēram, sadales tabulu, direktoriju struktūru un faila atribūtus.
    •     Datu saspiešana:    Splay kokus var izmantot, lai saspiestu datus, identificējot un kodējot atkārtotus modeļus.
    •     Teksta apstrāde    : Atvēršanas kokus var izmantot teksta apstrādes lietojumprogrammās, piemēram, pareizrakstības pārbaudītājos, kur vārdi tiek glabāti izrunāšanas kokā ātrai meklēšanai un izguvei.
    •     Grafiku algoritmi:    Izvēršanas kokus var izmantot, lai ieviestu grafiku algoritmus, piemēram, atrastu īsāko ceļu svērtā grafikā.
    •     Tiešsaistes spēles:    Spēļu kokus var izmantot tiešsaistes spēlēs, lai saglabātu un pārvaldītu labākos rezultātus, līderu sarakstus un spēlētāju statistiku.
    Protams, šeit ir dažas plīsuma koku priekšrocības un trūkumi, kā arī dažas ieteicamās grāmatas, lai uzzinātu vairāk par šo tēmu:
    saliktā primārā atslēga

     
    Splay koku priekšrocības:
    Splay koki ir amortizējuši laika sarežģītību O(log n) daudzām operācijām, padarot tās ātrākas par daudzām citām līdzsvarotām koku datu struktūrām.  
    Spray koki ir pašregulējoši, kas nozīmē, ka tie automātiski līdzsvaro sevi, kad tiek ievietoti un izņemti priekšmeti. Tas var palīdzēt izvairīties no veiktspējas pasliktināšanās, kas var rasties, ja koks kļūst nelīdzsvarots.
     
    Splay koku trūkumi:
    Izkliedētajiem kokiem var būt sliktākā gadījuma laika sarežģītība O(n) dažām operācijām, padarot tās mazāk paredzamas nekā citām līdzsvarotām koku datu struktūrām, piemēram, AVL kokiem vai sarkanmelniem kokiem.  
    Splay koki var nebūt piemēroti noteiktiem lietojumiem, kur nepieciešama paredzama veiktspēja.
     
    Ieteicamās grāmatas par Splay Trees:
    Datu struktūru un algoritmu analīze Java valodā, Marks Allens Veiss  
    Tomasa H. Kormena, Čārlza E. Leizersona, Ronalda L. Rivesta un Kliforda Steina ievads algoritmos  
    Datu struktūras un algoritmi valodā C++, Michael T. Goodrich un Roberto Tamassia
     
    Secinājums:
    Noslēgumā jāsaka, ka Splay Trees ir dinamiska pašbalansējoša binārā meklēšanas koka datu struktūra, kas nodrošina efektīvu elementu meklēšanas, ievietošanas un dzēšanas veidu. Tie atšķiras no tradicionālajiem līdzsvarotajiem binārajiem meklēšanas kokiem, piemēram, AVL un sarkanmelnajiem kokiem, jo ​​tie pārkārto koku pēc katras darbības, lai nesen piekļūtu mezglu novirzītu uz sakni. Tas palīdz samazināt koka augstumu un nodrošina ātrāku darbību. Splay Trees ir ļoti elastīgas un var tikt pielāgotas dažādiem lietošanas gadījumiem. Lai gan tiem var būt lielāka pieskaitāmā vērtība rotācijas ziņā, to vienkāršība un daudzpusība padara tos par noderīgiem rīkiem dažādu problēmu risināšanai.