SPLAY MEDŽIO DUOMENŲ STRUKTŪROS ĮVADAS – TECHCODEVIEW.COM

Splay medis yra savaime besireguliuojanti dvejetainė paieškos medžio duomenų struktūra, o tai reiškia, kad medžio struktūra koreguojama dinamiškai pagal pasiekiamus arba įterptus elementus. Kitaip tariant, medis automatiškai persitvarko taip, kad dažnai pasiekiami arba įterpiami elementai priartėtų prie šakninio mazgo.

Išsklaidymo medį pirmą kartą pristatė Daniel Dominic Sleator ir Robert Endre Tarjan 1985 m. Jis turi paprastą ir efektyvų įgyvendinimą, leidžiantį atlikti paieškos, įterpimo ir ištrynimo operacijas O(log n) amortizuota laiko sudėtingumu, kur n yra elementų skaičius medyje.
Pagrindinė išsklaidytų medžių idėja yra atnešti vėliausiai pasiektą arba įterptą elementą prie medžio šaknies, atliekant medžio pasukimų seką, vadinamą išmetimu. Išsklaidymas – tai medžio restruktūrizavimo procesas, paverčiant naujausią prieigą arba įterptą elementą nauja šaknimi ir palaipsniui perkeliant likusius mazgus arčiau šaknies.
Dėl savaime besireguliuojančio pobūdžio medžiai yra labai veiksmingi, o tai sumažina bendrą dažnai pasiekiamų elementų prieigos laiką. Dėl to jie yra geras pasirinkimas programoms, kurioms reikalingos greitos ir dinamiškos duomenų struktūros, pvz., talpyklos sistemos, duomenų glaudinimas ir tinklo maršruto parinkimo algoritmai.
Tačiau pagrindinis išsibarsčiusių medžių trūkumas yra tas, kad jie negarantuoja subalansuotos medžio struktūros, o tai blogiausiu atveju gali pabloginti našumą. Be to, išsklaidymo medžiai netinka programoms, kurioms reikalingas garantuotas blogiausias veikimas, pvz., realaus laiko sistemos arba saugai svarbios sistemos.

Apskritai, skleidžiami medžiai yra galinga ir universali duomenų struktūra, suteikianti greitą ir efektyvią prieigą prie dažnai pasiekiamų arba įterptų elementų. Jie plačiai naudojami įvairiose srityse ir suteikia puikų kompromisą tarp našumo ir paprastumo.

Išsklaidymo medis yra savaime balansuojantis dvejetainis paieškos medis, sukurtas veiksmingai prieigai prie duomenų elementų, remiantis jų pagrindinėmis reikšmėmis.

Pagrindinis išskleidimo medžio bruožas yra tas, kad kiekvieną kartą, kai pasiekiamas elementas, jis perkeliamas į medžio šaknį, sukuriant labiau subalansuotą struktūrą vėlesnėms prieigoms.
Plyšiniai medžiai pasižymi rotacijų naudojimu, tai yra lokalios medžio transformacijos, keičiančios jo formą, bet išsaugančios elementų tvarką.
Pasukimai naudojami norint pasiekti elementą prie medžio šaknies, taip pat subalansuoti medį, jei po kelių priėjimų jis išsibalansuoja.

Veiksmai svaidymo medyje:

Įterpimas: Norėdami į medį įterpti naują elementą, pradėkite atlikdami įprastą dvejetainės paieškos medžio įterpimą. Tada pasukite, kad naujai įdėtas elementas būtų prie medžio šaknies.
Ištrynimas : Norėdami ištrinti elementą iš medžio, pirmiausia suraskite jį naudodami dvejetainę paieškos medžio paiešką. Tada, jei elementas neturi vaikų, tiesiog jį pašalinkite. Jei jis turi vieną vaiką, paaukštinkite jį į vietą medyje. Jei jis turi du antrinius elementus, suraskite elemento įpėdinį (mažiausias elementas dešiniajame pomedyje), sukeiskite jo raktą su elementu, kurį norite ištrinti, ir ištrinkite įpėdinį.
Paieška : Norėdami ieškoti elemento medyje, pradėkite atlikdami dvejetainę medžio paiešką. Jei elementas rastas, pasukite jį, kad nuvestumėte jį prie medžio šaknies. Jei jo nerasta, taikykite pasukimus paskutiniam paieškoje aplankytam mazgui, kuris tampa nauja šaknimi.
Rotacija : Pasukimų medyje naudojami Zig arba Zig-Zig pasukimai. Zig pasukimas naudojamas, kad mazgas būtų nukreiptas į šaknį, o Zig-Zig sukimas naudojamas medžiui subalansuoti po kelių priėjimų prie to paties pomedžio elementų.

Štai žingsnis po žingsnio paaiškinimas apie sukimosi operacijas:

Zig rotacija : Jei mazgas turi tinkamą antrinį elementą, atlikite tinkamą sukimąsi, kad jis būtų nukreiptas į šaknį. Jei vaikas turi kairę, atlikite sukimąsi į kairę.
Zig-Zig sukimasis: Jei mazgas turi anūką, kuris taip pat yra jo vaiko dešinysis arba kairysis vaikas, atlikite dvigubą sukimąsi, kad subalansuotumėte medį. Pavyzdžiui, jei mazgas turi dešinįjį, o dešinįjį - kairįjį, atlikite sukimąsi į dešinę į kairę. Jei mazgas turi kairįjį vaiką, o kairysis vaikas turi dešinįjį, atlikite sukimąsi į kairę į dešinę.
Pastaba: Konkrečios įgyvendinimo detalės, įskaitant tikslius naudojamus pasukimus, gali skirtis, atsižvelgiant į tikslią išskleidimo medžio formą.

Pasukimai „Splay Tree“.

Zig rotacija
Zag Rotation
Zig – Zig Rotation
Zag – Zag Rotation
Zig – Zag Rotation
Zag – Zig Rotation

1) Zig sukimasis:

„Zig Rotation“ pasukimo medžiuose veikia panašiai kaip vienas sukimas į dešinę AVL medžio sukimosi metu. Dėl šio sukimosi mazgai perkeliami viena padėtimi į dešinę nuo dabartinės vietos. Pavyzdžiui, apsvarstykite šį scenarijų:

Zig rotacija (vienas sukimas)

2) Zag Rotation:

„Zag Rotation“ sukibimo medžiuose veikia panašiai kaip vienas sukimas į kairę AVL medžio pasukimuose. Šio sukimosi metu mazgai pasislenka viena padėtimi į kairę nuo dabartinės vietos. Pavyzdžiui, apsvarstykite šią iliustraciją:

žaidimas balandis android

Zag Rotation (vienas pasukimas į kairę)

3) Zig-Zig sukimasis:

„Zig-Zig“ sukimasis medžiuose yra dvigubas „zig“ sukimasis. Dėl šio sukimosi mazgai pasislenka dviem pozicijomis į dešinę nuo dabartinės vietos. Norėdami geriau suprasti, pažiūrėkite į šį pavyzdį:

Zig-Zig sukimas (dvigubas pasukimas į dešinę)

blokuoti „YouTube“ skelbimus „Android“.

4) Zag-Zag rotacija:

Išsiskleidusiuose medžiuose Zag-Zag Rotation yra dvigubas zaginis sukimasis. Dėl šio sukimosi mazgai iš dabartinės padėties pasislenka dviem pozicijomis į kairę. Pavyzdžiui:

„Zag-Zag“ pasukimas (dvigubas pasukimas į kairę)

5) Zig-Zag sukimasis:

„Zig-Zag“ sukimasis medžiuose yra ziginio sukimosi, po kurio seka „zag“ sukimosi, derinys. Dėl šio sukimosi mazgai iš dabartinės vietos pasislenka viena padėtimi į dešinę, o paskui – į kairę. Šioje iliustracijoje pateikiama vizualiai pavaizduota ši koncepcija:

Zig-Zag sukimasis

6) Zag-Zig pasukimas:

„Zag-Zig“ sukimasis medžiuose yra zaginių sukimų, po kurių seka zig sukimas, serija. Dėl to mazgai pasislenka viena padėtimi į kairę, o po to pasislenka viena padėtimi į dešinę nuo dabartinės vietos. Šioje iliustracijoje pateikiama vizualiai pavaizduota ši koncepcija:

Zag-Zig rotacija

Žemiau yra C++ kodas, skirtas sukimuisi Splay medyje:

C++

 #include  using namespace std; struct Node {  int key;  Node *left, *right; }; Node* newNode(int key) {  Node* node = new Node();  node->raktas = raktas;  mazgas->kairė = mazgas->dešinė = nullptr;  grąžinimo mazgas; } Mazgas* dešinėnPasukti(Magas* x) { Mazgas* y = x->kairėn;  x->kairė = y->dešinė;  y->dešinė = x;  grąžinti y; } Mazgas* į kairęPasukti(Magas* x) { Mazgas* y = x->į dešinę;  x->dešinė = y->kairė;  y->kairė = x;  grąžinti y; } Mazgas* splay(Node* root, int raktas) { if (root == nullptr || root->key == raktas) 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);  šaknis = dešinėnPasukti(šaknis);  } else if (root->left->key< key) {  root->kairė->dešinė = splay(šaknis->kairė->dešinė, klavišas);  if (root->left->right != nullptr) root->left = leftRotate(root->left);  } return (root->left == nullptr) ? šaknis : dešinėnPasukti(šaknis);  } 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 = rightPasukti(šaknis->dešinėn);  } else if (root->right->key< key) {  root->dešinė->dešinė = splay(root->right->right, key);  šaknis = leftPasukti(šaknis);  } return (root->right == nullptr) ? šaknis : leftPasukti(šaknis);  } } Mazgas* įterpti(Mazgas* root, int raktas) { if (root == nullptr) return newMazgas(raktas);  šaknis = splay(šaknis, raktas);  if (root->key == raktas) return root;  Mazgas* mazgas = naujasMazgas(raktas);  if (root->key> key) { mazgas->dešinė = root;  mazgas->kairė = root->left;  šaknis->kairė = nullptr;  } else { mazgas->kairė = šaknis;  mazgas->dešinė = root->right;  root->right = nullptr;  } grąžinimo mazgas; } void preOrder(Magas* mazgas) { if (mazgas != nullptr) { cout<< node->Raktas<< ' ';  preOrder(node->kairėje);  preOrder(mazgas->dešinėn);  } } int main() { Mazgas* root = nullptr;  šaknis = įterpti(šaknis, 100);  šaknis = įterpti(šaknis, 50);  šaknis = įterpti(šaknis, 200);  šaknis = įterpti(šaknis, 40);  šaknis = įterpti(šaknis, 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>raktas) { if (root.left == null) return šaknis;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  šaknis = dešinėnPasukti(šaknis);  } 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>raktas) { 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>raktas) { mazgas.dešinė = šaknis;  mazgas.left = root.left;  root.left = null;  } else { mazgas.left = root;  mazgas.dešinė = root.right;  root.right = null;  } grąžinimo mazgas;  } static void preOrder(Node node) { if (mazgas != null) { System.out.println();  System.out.print(mazgas.key + ' ');  preOrder(mazgas.kairėje);  preOrder(mazgas.dešinė);  } } public static void main(String[] args) { Mazgo šaknis = null;  šaknis = įterpti(šaknis, 100);  šaknis = įterpti(šaknis, 50);  šaknis = įterpti(šaknis, 200);  šaknis = įterpti(šaknis, 40);  šaknis = įterpti(šaknis, 60);  System.out.println('Išankstinis modifikuoto Splay medžio perėjimas:');  preOrder(root);  } } // Šį kodą sukūrė 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>raktas: jei root.left yra Nėra: grąžinti šaknį if root.left.key> raktas: 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>raktas: root.right.left = splay(root.right.left, raktas) if root.right.left: root.right = dešinėn_pasukti(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>raktas: node.right = šakninis mazgas.left = root.left root.left = Niekas kitas: node.left = root node.right = root.right root.right = Nėra grąžinti mazgo def pre_order(mazgas): jei mazgas: spausdinti (mazgas.key, end=' ') pre_order(mazgas.kairėje) pre_order(mazgas.right) if __name__ == '__main__': root = Nėra šaknis = įterpti(šaknis, 100) root = įterpti(šaknis , 50) šaknis = įterpti(šaknis, 200) šaknis = įterpti(šaknis, 40) šaknis = įterpti(šaknis, 60) print('Išankstinis užsakymas modifikuoto Splay medžio:') 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>raktas) { if (root.left == null) return šaknis;  if (root.left.key> key) { root.left.left = splay(root.left.left, key);  šaknis = dešinėnPasukti(šaknis);  } 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>raktas) { 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>raktas) { mazgas.dešinė = šaknis;  mazgas.left = root.left;  root.left = null;  } else { mazgas.left = root;  mazgas.dešinė = root.right;  root.right = null;  } grąžinimo mazgas;  } static void preOrder(Node node) { if (mazgas != null) { Console.Write(mazgas.key + ' ');  preOrder(mazgas.kairėje);  preOrder(mazgas.dešinė);  } } public static void Main(string[] args) { Mazgo šaknis = null;  šaknis = įterpti(šaknis, 100);  šaknis = įterpti(šaknis, 50);  šaknis = įterpti(šaknis, 200);  šaknis = įterpti(šaknis, 40);  šaknis = įterpti(šaknis, 60);  Console.WriteLine( 'Išankstinis modifikuoto Splay medžio perėjimas:');  preOrder(root);  } } // Šį kodą sukūrė princas Kumaras>>Javascript>  
  Išvestis      Nesubalansuoti medžiai:    Medžiai gali tapti nesubalansuoti ir neefektyvūs, jei medį pakartotinai pasuksite ta pačia kryptimi.    Atminties naudojimas:    „Splay“ medžiai gali naudoti daug atminties, palyginti su kitomis duomenų struktūromis, nes kiekviename mazge yra papildomos informacijos.
    Sudėtingumas:    Atliekant pagrindines operacijas, pvz., įterpimą ir ištrynimą, medžiai gali būti labai sudėtingi, nes medžius reikia pertvarkyti po kiekvienos operacijos.
    Reorganizavimo išlaidos:    Atliekant kiekvieną operaciją reikalingas pjovimo procesas gali užtrukti daug laiko ir sukelti didelių išlaidų.
    Riboto naudojimo atvejai    : „Splay“ medžiai netinka visoms duomenų struktūroms ir jų naudojimo atvejai yra riboti, nes jie efektyviai neapdoroja pasikartojančių raktų.
„Splay“ medžio pritaikymas:
    Talpykla    : Splay medžiai gali būti naudojami talpyklos atminties valdymui įgyvendinti, kai dažniausiai pasiekiami elementai perkeliami į medžio viršų, kad būtų galima greičiau pasiekti.
    Duomenų bazės indeksavimas    : Splay medžiai gali būti naudojami duomenų bazėms indeksuoti, kad būtų galima greičiau ieškoti ir gauti duomenų.
    Failų sistemos    : „Splay“ medžiai gali būti naudojami failų sistemos metaduomenims, pvz., paskirstymo lentelei, katalogų struktūrai ir failo atributams, saugoti.
    Duomenų suspaudimas:    Splay medžiai gali būti naudojami duomenims suspausti identifikuojant ir koduojant pasikartojančius šablonus.
    Teksto apdorojimas    : Atskleidimo medžiai gali būti naudojami teksto apdorojimo programose, pvz., rašybos tikrinimo priemonėse, kur žodžiai išsaugomi sklaidos medyje, kad būtų galima greitai ieškoti ir gauti.
    Grafiko algoritmai:    Išsklaidymo medžiai gali būti naudojami grafiko algoritmams įgyvendinti, pavyzdžiui, surasti trumpiausią kelią svertiniame grafike.
    Internetiniai žaidimai:    Žaidimų medžiai gali būti naudojami internetiniuose žaidimuose, siekiant saugoti ir tvarkyti aukščiausius rezultatus, pirmaujančiųjų sąrašus ir žaidėjų statistiką.
Žinoma, čia yra keletas skraidančių medžių privalumų ir trūkumų, taip pat keletas rekomenduojamų knygų, skirtų daugiau sužinoti šia tema:
 „Splay“ medžių pranašumai:
Splay medžiai amortizuoja O(log n) laiko sudėtingumą daugeliui operacijų, todėl kai kuriais atvejais jos yra greitesnės nei daugelis kitų subalansuotų medžio duomenų struktūrų.  
Sraigtiniai medžiai reguliuojasi savaime, o tai reiškia, kad jie automatiškai išsibalansuoja, kai elementai įdedami ir išimami. Tai gali padėti išvengti našumo pablogėjimo, kuris gali atsirasti, kai medis tampa nesubalansuotas.
 „Splay“ medžių trūkumai:
Atliekant kai kurias operacijas, kai kurių operacijų keitimo medžiai gali turėti blogiausio atvejo laiko sudėtingumą, todėl jie yra mažiau nuspėjami nei kitos subalansuotos medžio duomenų struktūros, pvz., AVL medžiai ar raudonai juodi medžiai.  
„Splay“ medžiai gali būti netinkami tam tikroms programoms, kai reikia nuspėjamo veikimo.
 Rekomenduojamos knygos apie „Splay Trees“:
„Java“ duomenų struktūrų ir algoritmų analizė, Mark Allen Weiss  
Thomaso H. Cormeno, Charleso E. Leisersono, Ronaldo L. Rivesto ir Cliffordo Steino įvadas į algoritmus  
Duomenų struktūros ir algoritmai C++, Michael T. Goodrich ir Roberto Tamassia
excel pašalinti pirmąjį simbolį
 Išvada:
Apibendrinant galima pasakyti, kad „Splay Trees“ yra dinamiška savaime balansuojanti dvejetainio paieškos medžio duomenų struktūra, suteikianti efektyvų elementų paieškos, įterpimo ir trynimo būdą. Jie skiriasi nuo tradicinių subalansuotų dvejetainių paieškos medžių, tokių kaip AVL ir raudonai juodi medžiai, nes jie pertvarko medį po kiekvienos operacijos, kad neseniai pasiektas mazgas būtų nukreiptas į šaknį. Tai padeda sumažinti medžio aukštį ir greičiau atlikti operacijas. „Splay Trees“ yra labai lankstūs ir gali būti pritaikyti įvairiems naudojimo atvejams. Nors sukimosi išlaidos gali būti didesnės, dėl jų paprastumo ir universalumo jie yra naudingi įrankiai sprendžiant įvairias problemas.

TechCodeview

Įvadas į Splay medžio duomenų struktūrą

Veiksmai svaidymo medyje:

Štai žingsnis po žingsnio paaiškinimas apie sukimosi operacijas:

Pasukimai „Splay Tree“.

1) Zig sukimasis:

2) Zag Rotation:

3) Zig-Zig sukimasis:

4) Zag-Zag rotacija:

5) Zig-Zag sukimasis:

6) Zag-Zig pasukimas:

„Splay“ medžio pritaikymas:

„Splay“ medžių pranašumai:

„Splay“ medžių trūkumai:

Rekomenduojamos knygos apie „Splay Trees“:

Išvada: