Arborele Splay sunt arbori de căutare binari auto-echilibrați sau auto-ajustați. Cu alte cuvinte, putem spune că arborii splay sunt variantele arborilor de căutare binari. Condiția prealabilă pentru arborii splay pe care ar trebui să o cunoaștem despre arborii de căutare binari.

După cum știm deja, complexitatea de timp a unui arbore de căutare binar în fiecare caz. Complexitatea de timp a unui arbore de căutare binar în cazul mediu este O(logn) iar complexitatea timpului în cel mai rău caz este O(n). Într-un arbore de căutare binar, valoarea subarborelui din stânga este mai mică decât nodul rădăcină, iar valoarea subarborelui din dreapta este mai mare decât nodul rădăcină; în acest caz, complexitatea timpului ar fi O(logn) . Dacă arborele binar este declinat la stânga sau la dreapta, atunci complexitatea timpului ar fi O(n). Pentru a limita asimetria, AVL și arbore roșu-negru a intrat în imagine, având O(logn ) complexitatea timpului pentru toate operațiunile în toate cazurile. De asemenea, putem îmbunătăți această complexitate a timpului prin implementări mai practice, deci noul Arbore Ce este un Arbore Splay?

Un copac splay este un copac auto-echilibrator, dar Copacii AVL și Red-Black sunt, de asemenea, arbori autoechilibrați atunci. Ceea ce face ca arborele splay să fie unici doi copaci. Are o proprietate suplimentară care îl face unic este întinderea.

Un arbore splay conține aceleași operații ca și a Arborele de căutare binar , adică inserare, ștergere și căutare, dar conține și încă o operație, adică splaying. Asa de. toate operațiunile din arborele splay sunt urmate de splaying.

Copacii Splay nu sunt arbori strict echilibrați, dar sunt arbori aproximativ echilibrați. Să înțelegem operația de căutare în arborele splay.

Să presupunem că vrem să căutăm 7 elemente în arbore, care este prezentat mai jos:

Pentru a căuta orice element din arborele splay, mai întâi, vom efectua operația standard de arbore de căutare binar. Deoarece 7 este mai puțin de 10, vom ajunge la stânga nodului rădăcină. După efectuarea operației de căutare, trebuie să efectuăm splaying. Aici splaying înseamnă că operația pe care o realizăm pe orice element ar trebui să devină nodul rădăcină după efectuarea unor rearanjamente. Rearanjarea arborelui se va face prin rotații.

Notă: Arborele splay poate fi definit ca arborele auto-ajustat în care orice operație efectuată asupra elementului ar rearanja arborele astfel încât elementul pe care a fost efectuată operația să devină nodul rădăcină al arborelui.

Rotații

Există șase tipuri de rotații utilizate pentru întindere:

1. Rotire zig (rotație la dreapta)
2. Rotire Zag (Rotire la stânga)
3. Zig zag (Zig urmat de zag)
4. Zag zig (Zag urmat de zig)
5. Zig zig (două rotații la dreapta)
6. Zag zag (două rotații la stânga)

Factori necesari pentru selectarea unui tip de rotație

Următorii sunt factorii utilizați pentru selectarea unui tip de rotație:

• Nodul pe care încercăm să-l rotim are un bunic?
• Nodul este copilul stânga sau dreapta al părintelui?
• Nodul este copilul stânga sau dreapta al bunicului?

Cazuri pentru rotații

Cazul 1: Dacă nodul nu are un bunic, iar dacă este copilul drept al părintelui, atunci efectuăm rotația din stânga; în caz contrar, se efectuează rotația dreaptă.

Cazul 2: Dacă nodul are un bunic, atunci pe baza următoarelor scenarii; rotația ar fi efectuată:

Scenariul 1: Dacă nodul este dreptul părintelui și părintele este, de asemenea, dreptul părintelui său, atunci zig zig dreapta dreapta rotatie se efectuează.

Scenariul 2: Dacă nodul este la stânga unui părinte, dar părintele este la dreapta părintelui său, atunci zig zag rotire dreapta stanga se efectuează.

Scenariul 3: Dacă nodul este dreptul părintelui și părintele are dreptul părintelui său, atunci zig zig stânga stânga rotație se efectuează.

Scenariul 4: Dacă nodul este la dreapta unui părinte, dar părintele este la stânga părintelui său, atunci rotație în zig-zag dreapta-stânga se efectuează.

Acum, să înțelegem rotațiile de mai sus cu exemple.

Pentru a rearanja copacul, trebuie să facem câteva rotații. Următoarele sunt tipurile de rotații în arborele splay:

Rotații în zig

Rotațiile zig sunt utilizate atunci când elementul care trebuie căutat este fie un nod rădăcină, fie copilul unui nod rădăcină (adică, copilul stânga sau dreapta).

Următoarele sunt cazurile care pot exista în arborele splay în timpul căutării:

Cazul 1: Dacă elementul de căutare este un nod rădăcină al arborelui.

Cazul 2: Dacă elementul de căutare este un copil al nodului rădăcină, atunci cele două scenarii vor fi acolo:

1. Dacă copilul este un copil stâng, se va efectua rotația la dreapta, cunoscută sub numele de rotație în zig la dreapta.
2. Dacă copilul este un copil drept, se va efectua rotația la stânga, cunoscută sub numele de rotație în zig stânga.

Să ne uităm la cele două scenarii de mai sus printr-un exemplu.

Luați în considerare exemplul de mai jos:

În exemplul de mai sus, trebuie să căutăm 7 elemente în arbore. Vom urma pașii de mai jos:

Pasul 1: Mai întâi, comparăm 7 cu un nod rădăcină. Deoarece 7 este mai mic decât 10, deci este un copil stâng al nodului rădăcină.

Pasul 2: Odată ce elementul este găsit, vom efectua splaying. Rotația dreaptă este efectuată astfel încât 7 să devină nodul rădăcină al arborelui, așa cum se arată mai jos:

Să luăm în considerare un alt exemplu.

În exemplul de mai sus, trebuie să căutăm 20 de elemente în arbore. Vom urma pașii de mai jos:

Pasul 1: În primul rând, comparăm 20 cu un nod rădăcină. Deoarece 20 este mai mare decât nodul rădăcină, deci este un copil drept al nodului rădăcină.

Pasul 2: Odată ce elementul este găsit, vom efectua splaying. Rotația la stânga este efectuată astfel încât 20 de elemente să devină nodul rădăcină al arborelui.

Zig zig rotații

Uneori apare situația când elementul care trebuie căutat are atât un părinte, cât și un bunic. În acest caz, trebuie să efectuăm patru rotații pentru împrăștiere.

Să înțelegem acest caz printr-un exemplu.

Să presupunem că trebuie să căutăm un element în arbore, care este prezentat mai jos:

Pasul 1: În primul rând, trebuie să efectuăm o operație standard de căutare BST pentru a căuta elementul 1. Deoarece 1 este mai mic decât 10 și 7, deci va fi în stânga nodului 7. Prin urmare, elementul 1 are un părinte, adică 7, precum și un bunic, adică 10.

Pasul 2: În acest pas, trebuie să efectuăm splaying. Trebuie să facem nodul 1 ca nod rădăcină cu ajutorul unor rotații. În acest caz, nu putem efectua pur și simplu o rotație în zig sau în zag; trebuie să implementăm rotația zig zig.

Pentru a face nodul 1 ca nod rădăcină, trebuie să efectuăm două rotații la dreapta cunoscute sub numele de rotații zig zig. Când efectuăm rotația corectă, atunci 10 se va deplasa în jos, iar nodul 7 va veni în sus, așa cum se arată în figura de mai jos:

Din nou, vom efectua rotația în zig la dreapta, nodul 7 se va deplasa în jos, iar nodul 1 va veni în sus, așa cum se arată mai jos:

După cum observăm în figura de mai sus, că nodul 1 a devenit nodul rădăcină al arborelui; prin urmare, căutarea este finalizată.

Să presupunem că vrem să căutăm 20 în arborele de mai jos.

Pentru a căuta 20, trebuie să facem două rotații la stânga. Următorii sunt pașii necesari pentru a căuta 20 de noduri:

Pasul 1: Mai întâi, efectuăm operația standard de căutare BST. Deoarece 20 este mai mare decât 10 și 15, deci va fi în dreapta nodului 15.

Pasul 2: Al doilea pas este să efectuați splaying. În acest caz, ar fi efectuate două rotații la stânga. În prima rotație, nodul 10 se va deplasa în jos, iar nodul 15 se va deplasa în sus, așa cum se arată mai jos:

În a doua rotație din stânga, nodul 15 se va deplasa în jos, iar nodul 20 devine nodul rădăcină al arborelui, așa cum se arată mai jos:

După cum am observat că se efectuează două rotații la stânga; deci este cunoscut sub numele de rotație la stânga zig zig.

Rotații în zig-zag

Până acum, am citit că atât părintele, cât și bunicul sunt fie în relație RR, fie LL. Acum, vom vedea relația RL sau LR dintre părinte și bunic.

Să înțelegem acest caz printr-un exemplu.

Să presupunem că vrem să căutăm 13 elemente în arborele care este prezentat mai jos:

Pasul 1: În primul rând, efectuăm operația standard de căutare BST. Deoarece 13 este mai mare decât 10, dar mai mic de 15, nodul 13 va fi copilul din stânga al nodului 15.

Pasul 2: Deoarece nodul 13 este la stânga lui 15 și nodul 15 este la dreapta nodului 10, deci există relația RL. Mai întâi, efectuăm rotația corectă pe nodul 15, iar 15 se va deplasa în jos, iar nodul 13 va veni în sus, așa cum se arată mai jos:

Totuși, nodul 13 nu este nodul rădăcină, iar 13 este la dreapta nodului rădăcină, așa că vom efectua rotația la stânga cunoscută sub numele de rotație zag. Nodul 10 se va deplasa în jos, iar 13 devine nodul rădăcină, după cum se arată mai jos:

După cum putem observa în arborele de mai sus că nodul 13 a devenit nodul rădăcină; prin urmare, căutarea este finalizată. În acest caz, am efectuat mai întâi rotația în zig și apoi rotația în zag; deci, este cunoscută ca rotație în zig-zag.

Rotire în zig în zag

Să înțelegem acest caz printr-un exemplu.

Să presupunem că vrem să căutăm 9 elemente în arbore, care este prezentat mai jos:

Pasul 1: Mai întâi, efectuăm operația standard de căutare BST. Deoarece 9 este mai mic de 10, dar mai mare de 7, deci va fi copilul potrivit al nodului 7.

Pasul 2: Deoarece nodul 9 este la dreapta nodului 7, iar nodul 7 este la stânga nodului 10, deci există relația LR. Mai întâi, efectuăm rotația la stânga pe nodul 7. Nodul 7 se va deplasa în jos, iar nodul 9 se va mișca în sus, așa cum se arată mai jos:

Totuși, nodul 9 nu este un nod rădăcină, iar 9 este la stânga nodului rădăcină, așa că vom efectua rotația la dreapta cunoscută sub numele de rotație în zig. După efectuarea rotației corecte, nodul 9 devine nodul rădăcină, după cum se arată mai jos:

După cum putem observa în arborele de mai sus că nodul 13 este un nod rădăcină; prin urmare, căutarea este finalizată. În acest caz, am efectuat mai întâi rotația în zig (rotația la stânga), apoi se efectuează rotația în zig (rotația la dreapta), deci este cunoscută sub numele de rotație în zig zag.

Avantajele arborelui Splay

• În arborele splay, nu trebuie să stocăm informațiile suplimentare. În schimb, în ​​arborii AVL, trebuie să stocăm factorul de echilibru al fiecărui nod care necesită spațiu suplimentar, iar arborii roșu-negru necesită, de asemenea, să stocăm un bit suplimentar de informații care denotă culoarea nodului, fie roșu, fie negru.
• Este cel mai rapid tip de arbore de căutare binar pentru diverse aplicații practice. Este folosit în Compilatoare Windows NT și GCC .
• Oferă performanțe mai bune, deoarece nodurile accesate frecvent se vor deplasa mai aproape de nodul rădăcină, datorită căruia elementele pot fi accesate rapid în arbori splay. Este folosit în implementarea cache-ului deoarece datele recent accesate sunt stocate în cache, astfel încât să nu avem nevoie să mergem în memorie pentru a accesa datele și durează mai puțin timp.

Dezavantajul arborelui Splay

Dezavantajul major al arborelui splay ar fi că copacii nu sunt strict echilibrați, adică sunt aproximativ echilibrați. Uneori, arborii splay sunt liniari, deci va fi nevoie de complexitate în timp O(n).

Operație de inserare în arborele Splay

În inserare operație, mai întâi introducem elementul în arbore și apoi efectuăm operația de împrăștiere pe elementul inserat.

15, 10, 17, 7

Pasul 1: Mai întâi, inserăm nodul 15 în arbore. După inserare, trebuie să efectuăm întinderea. Deoarece 15 este un nod rădăcină, nu este nevoie să efectuăm splaying.

Pasul 2: Următorul element este 10. Deoarece 10 este mai mic decât 15, nodul 10 va fi copilul din stânga al nodului 15, după cum se arată mai jos:

Acum, facem performanță întinderea . Pentru a face 10 ca nod rădăcină, vom efectua rotația corectă, așa cum se arată mai jos:

Pasul 3: Următorul element este 17. Deoarece 17 este mai mare decât 10 și 15, va deveni copilul drept al nodului 15.

Acum, vom efectua splaying. Deoarece 17 are un părinte și un bunic, vom efectua rotații zig zig.

În figura de mai sus, putem observa că 17 devine nodul rădăcină al arborelui; prin urmare, inserarea este finalizată.

Pasul 4: Următorul element este 7. Deoarece 7 este mai mic decât 17, 15 și 10, deci nodul 7 va rămâne fiul lui 10.

Acum, trebuie să întindem copacul. Deoarece 7 are un părinte și un bunic, vom efectua două rotații la dreapta, așa cum se arată mai jos:

Totuși, nodul 7 nu este un nod rădăcină, este un copil stâng al nodului rădăcină, adică 17. Deci, trebuie să mai efectuăm o rotație la dreapta pentru a face nodul 7 ca nod rădăcină, așa cum se arată mai jos:

Algoritm pentru operația de inserare

 Insert(T, n) temp= T_root y=NULL while(temp!=NULL) y=temp if(n->data data) temp=temp->left else temp=temp->right n.parent= y if(y==NULL) T_root = n else if (n->data data) y->left = n else y->right = n Splay(T, n) 

În algoritmul de mai sus, T este arborele și n este nodul pe care dorim să-l inserăm. Am creat o variabilă temporară care conține adresa nodului rădăcină. Vom rula bucla while până când valoarea temp devine NULL.

Odată ce inserarea este finalizată, se va efectua împrăștierea

Algoritm pentru operația Splaying

 Splay(T, N) while(n->parent !=Null) if(n->parent==T->root) if(n==n->parent->left) right_rotation(T, n->parent) else left_rotation(T, n->parent) else p= n->parent g = p->parent if(n=n->parent->left && p=p->parent->left) right.rotation(T, g), right.rotation(T, p) else if(n=n->parent->right && p=p->parent->right) left.rotation(T, g), left.rotation(T, p) else if(n=n->parent->left && p=p->parent->right) right.rotation(T, p), left.rotation(T, g) else left.rotation(T, p), right.rotation(T, g) Implementation of right.rotation(T, x) right.rotation(T, x) y= x->left x->left=y->right y->right=x return y 

În implementarea de mai sus, x este nodul pe care este efectuată rotația, în timp ce y este copilul din stânga al nodului x.

Implementarea left.rotation(T, x)

 left.rotation(T, x) y=x->right x->right = y->left y->left = x return y 

În implementarea de mai sus, x este nodul pe care se efectuează rotația și y este copilul drept al nodului x.

Ștergerea în arborele Splay

După cum știm că arborele splay sunt variantele arborelui de căutare binar, astfel încât operația de ștergere în arborele splay ar fi similară cu BST, dar singura diferență este că operația de ștergere este urmată în arborele splay de operația de splaying.

Tipuri de ștergeri:

Există două tipuri de ștergeri în arborii de afișare:

1. Întindere de jos în sus
2. Splaying de sus în jos

Întindere de jos în sus

În splaying de jos în sus, mai întâi ștergem elementul din arbore și apoi executăm splaying-ul pe nodul șters.

Să înțelegem ștergerea din arborele Splay.

Să presupunem că vrem să ștergem 12, 14 din arborele prezentat mai jos:

comunicare analogică

• În primul rând, pur și simplu efectuăm operația standard de ștergere BST pentru a șterge 12 elemente. Deoarece 12 este un nod frunză, așa că pur și simplu ștergem nodul din arbore.

Ștergerea încă nu a fost finalizată. Trebuie să întindem părintele nodului șters, adică 10. Trebuie să efectuăm Splay(10) în copac. După cum putem observa în arborele de mai sus că 10 este la dreapta nodului 7, iar nodul 7 este la stânga nodului 13. Deci, mai întâi, efectuăm rotația la stânga pe nodul 7 și apoi efectuăm rotația la dreapta pe nodul. 13, după cum se arată mai jos:

Totuși, nodul 10 nu este un nod rădăcină; nodul 10 este copilul stâng al nodului rădăcină. Deci, trebuie să efectuăm rotația corectă pe nodul rădăcină, adică 14 pentru a face din nodul 10 un nod rădăcină, așa cum se arată mai jos:

• Acum, trebuie să ștergem elementul 14 din arbore, care este afișat mai jos:

După cum știm că nu putem șterge pur și simplu nodul intern. Vom înlocui valoarea nodului fie folosind predecesor în ordine sau succesor in ordine . Să presupunem că folosim succesor în ordine în care înlocuim valoarea cu cea mai mică valoare care există în subarborele din dreapta. Cea mai mică valoare din subarborele din dreapta al nodului 14 este 15, așa că înlocuim valoarea 14 cu 15. Deoarece nodul 14 devine nodul frunză, îl putem șterge pur și simplu așa cum se arată mai jos:

Totuși, ștergerea nu este finalizată. Trebuie să mai efectuăm o operațiune, adică splaying în care trebuie să facem ca părintele nodului șters ca nod rădăcină. Înainte de ștergere, părintele nodului 14 era nodul rădăcină, adică 10, așa că trebuie să efectuăm orice splaying în acest caz.

Splaying de sus în jos

În splaying de sus în jos, efectuăm mai întâi splaying-ul pe care urmează să fie efectuată ștergerea și apoi ștergem nodul din arbore. Odată ce elementul este șters, vom efectua operația de alăturare.

Să înțelegem împrăștierea de sus în jos printr-un exemplu.

Să presupunem că vrem să ștergem 16 din arborele care este afișat mai jos:

Pasul 1: În împrăștierea de sus în jos, mai întâi efectuăm împrăștierea pe nodul 16. Nodul 16 are atât părinte, cât și bunic. Nodul 16 este la dreapta părintelui său, iar nodul părinte este, de asemenea, la dreapta părintelui său, deci aceasta este o situație zag zag. În acest caz, mai întâi, vom efectua rotația la stânga pe nodul 13 și apoi 14, după cum se arată mai jos:

Nodul 16 nu este încă un nod rădăcină și este un copil drept al nodului rădăcină, așa că trebuie să efectuăm rotația la stânga pe nodul 12 pentru a face nodul 16 ca nod rădăcină.

Odată ce nodul 16 devine un nod rădăcină, vom șterge nodul 16 și vom obține doi arbori diferiți, adică subarborele stânga și subarborele din dreapta, așa cum se arată mai jos:

După cum știm că valorile subarborelui din stânga sunt întotdeauna mai mici decât valorile subarborelui din dreapta. Rădăcina subarborelui din stânga este 12, iar rădăcina subarborelui din dreapta este 17. Primul pas este să găsiți elementul maxim din subarborele din stânga. În subarborele din stânga, elementul maxim este 15, iar apoi trebuie să efectuăm operația de întindere pe 15.

După cum putem observa în arborele de mai sus, elementul 15 are atât un părinte, cât și un bunic. Un nod se află la dreapta părintelui său, iar nodul părinte este, de asemenea, la dreapta părintelui său, așa că trebuie să efectuăm două rotații la stânga pentru a face din nodul 15 un nod rădăcină, așa cum se arată mai jos:

După efectuarea a două rotații pe arbore, nodul 15 devine nodul rădăcină. După cum putem vedea, copilul drept al lui 15 este NULL, așa că atașăm nodul 17 în partea dreaptă a lui 15, așa cum se arată mai jos, iar această operație este cunoscută sub numele de a te alatura Operațiune.

Notă: Dacă elementul nu este prezent în arborele splay, care urmează să fie șters, atunci splay-ul va fi efectuat. Splaying-ul va fi efectuat pe ultimul element accesat înainte de a ajunge la NULL.

Algoritmul operației de ștergere

 If(root==NULL) return NULL Splay(root, data) If data!= root->data Element is not present If root->left==NULL root=root->right else temp=root Splay(root->left, data) root1->right=root->right free(temp) return root 

În algoritmul de mai sus, verificăm mai întâi dacă rădăcina este nulă sau nu; dacă rădăcina este NULL înseamnă că arborele este gol. Dacă arborele nu este gol, vom efectua operația de împrăștiere pe elementul care urmează să fie șters. Odată terminată operația de splaying, vom compara datele rădăcină cu elementul care urmează să fie șters; dacă ambele nu sunt egale înseamnă că elementul nu este prezent în arbore. Dacă sunt egale, pot apărea următoarele cazuri:

Cazul 1 : Stânga rădăcinii este NULL, dreapta rădăcinii devine nodul rădăcină.

Cazul 2 : Dacă există atât stânga cât și dreapta, atunci vom întinde elementul maxim în subarborele din stânga. Când împrăștierea este completă, elementul maxim devine rădăcina subarborelui din stânga. Subarborele din dreapta ar deveni copilul drept al rădăcinii subarborelui din stânga.