Splay stabla su samo-balansirajuća ili samopodešena binarna stabla pretraživanja. Drugim riječima, možemo reći da su splay stabla varijante binarnih stabala pretraživanja. Preduvjet za splay stabla koji bismo trebali znati o stablima binarnog pretraživanja.
Kao što već znamo, vremenska složenost stabla binarnog pretraživanja u svakom slučaju. Vremenska složenost stabla binarnog pretraživanja u prosječnom slučaju je O (prijava) a vremenska složenost u najgorem slučaju je O(n). U stablu binarnog pretraživanja, vrijednost lijevog podstabla je manja od korijenskog čvora, a vrijednost desnog podstabla je veća od korijenskog čvora; u tom bi slučaju vremenska složenost bila O (prijava) . Ako je binarno stablo zakošeno lijevo ili desno, tada bi vremenska složenost bila O(n). Kako bi se ograničila zakrivljenost, AVL i crveno-crno drvo došao u sliku, imajući O(log ) vremenska složenost za sve operacije u svim slučajevima. Također možemo poboljšati ovu vremensku složenost radeći više praktičnih implementacija, tako da novo Stablo Što je Splay Tree?
Raskošeno stablo je stablo koje se samo uravnotežuje, ali AVL i crveno-crna stabla također su samo-balansirajuća stabla. Ono što čini stablo jedinstvenim dva stabla. Ima jedno dodatno svojstvo koje ga čini jedinstvenim, a to je raspršivanje.
Splay stablo sadrži iste operacije kao a Binarno stablo pretraživanja , tj. umetanje, brisanje i pretraživanje, ali sadrži i još jednu operaciju, tj. razvlačenje. Tako. nakon svih operacija u splay stablu slijedi splaying.
Šiljasta stabla nisu strogo uravnotežena stabla, ali su otprilike uravnotežena stabla. Hajdemo razumjeti operaciju pretraživanja u splay-stablu.
Pretpostavimo da želimo pretražiti 7 elemenata u stablu, koje je prikazano u nastavku:
Za pretraživanje bilo kojeg elementa u splay stablu, prvo ćemo izvesti standardnu operaciju binarnog stabla pretraživanja. Kako je 7 manje od 10, doći ćemo lijevo od korijenskog čvora. Nakon što smo izvršili operaciju traženja, trebamo izvršiti splaying. Ovdje širenje znači da bi operacija koju izvodimo na bilo kojem elementu trebala postati korijenski čvor nakon izvođenja nekih preuređivanja. Preuređenje stabla vršit će se kroz rotacije.
Bilješka: Stablo rasklapanja može se definirati kao samopodešeno stablo u kojem bi bilo koja operacija izvršena na elementu preuredila stablo tako da element na kojem je operacija izvedena postaje korijenski čvor stabla.
Rotacije
Postoji šest vrsta rotacija koje se koriste za raspršivanje:
- Zig rotacija (desna rotacija)
- Zag rotacija (lijeva rotacija)
- Cik cak (Cik praćen cak)
- Zag cik (Zag praćen cik)
- Zig zig (dva desna okreta)
- Zag zag (dvije rotacije ulijevo)
Čimbenici potrebni za odabir vrste rotacije
Sljedeći su faktori koji se koriste za odabir vrste rotacije:
- Ima li čvor koji pokušavamo rotirati baku i djeda?
- Je li čvor lijevi ili desni dijete roditelja?
- Je li čvor lijevi ili desni dijete bake i djeda?
Slučajevi za rotacije
Slučaj 1: Ako čvor nema djeda-roditelja i ako je to desno dijete roditelja, tada provodimo lijevu rotaciju; u protivnom se izvodi desna rotacija.
Slučaj 2: Ako čvor ima baku i djeda, onda na temelju sljedećih scenarija; rotacija bi se izvršila:
Scenarij 1: Ako je čvor desno od roditelja i roditelj je također desno od svog roditelja, tada zig zig desno desna rotacija izvodi se.
Scenarij 2: Ako je čvor lijevo od roditelja, ali je roditelj desno od svog roditelja, tada cik cak desno lijevo okretanje izvodi se.
Scenarij 3: Ako je čvor desno od roditelja i roditelj je desno od svog roditelja, tada zig zig lijevo lijevo rotacija izvodi se.
Scenarij 4: Ako je čvor desno od roditelja, ali je roditelj lijevo od svog roditelja, tada cik cak rotacija desno-lijevo izvodi se.
Razmotrimo sada gornje rotacije s primjerima.
Da bismo preuredili stablo, moramo izvršiti neke rotacije. Sljedeće su vrste rotacija u splay stablu:
Zig rotacije se koriste kada je stavka koju treba pretražiti korijenski čvor ili dijete korijenskog čvora (tj. lijevi ili desni dijete).
Slijede slučajevi koji mogu postojati u splay stablu tijekom pretraživanja:
Slučaj 1: Ako je stavka za pretraživanje korijenski čvor stabla.
Slučaj 2: Ako je stavka pretraživanja dijete korijenskog čvora, tada će biti prisutna dva scenarija:
- Ako je dijete lijevo dijete, izvršit će se desna rotacija, poznata kao zig desna rotacija.
- Ako je dijete desno dijete, izvršit će se lijeva rotacija, poznata kao cik lijeva rotacija.
Pogledajmo gornja dva scenarija kroz primjer.
Razmotrite primjer u nastavku:
U gornjem primjeru, moramo pretražiti 7 elemenata u stablu. Slijedit ćemo korake u nastavku:
Korak 1: Prvo, uspoređujemo 7 s korijenskim čvorom. Kako je 7 manje od 10, to je lijevo dijete korijenskog čvora.
Korak 2: Kada je element pronađen, izvršit ćemo raspršivanje. Desna rotacija se izvodi tako da 7 postaje korijenski čvor stabla, kao što je prikazano u nastavku:
Razmotrimo još jedan primjer.
U gornjem primjeru, moramo pretražiti 20 elemenata u stablu. Slijedit ćemo korake u nastavku:
Korak 1: Prvo, uspoređujemo 20 s korijenskim čvorom. Kako je 20 veći od korijenskog čvora, tako da je to desno dijete korijenskog čvora.
Korak 2: Kada je element pronađen, izvršit ćemo raspršivanje. Lijeva rotacija se izvodi tako da 20 element postaje korijenski čvor stabla.
Ponekad se dogodi situacija da predmet koji se pretražuje ima i roditelja i baku i djeda. U ovom slučaju moramo izvršiti četiri rotacije za širenje.
Razmotrimo ovaj slučaj kroz primjer.
Pretpostavimo da moramo pretražiti 1 element u stablu, koji je prikazan ispod:
Korak 1: Prvo moramo izvesti standardnu BST operaciju pretraživanja kako bismo pretražili 1 element. Kako je 1 manji od 10 i 7, tako da će biti lijevo od čvora 7. Prema tome, element 1 ima roditelja, tj. 7, kao i baku i djeda, tj. 10.
Korak 2: U ovom koraku moramo izvršiti razmicanje. Moramo napraviti čvor 1 kao korijenski čvor uz pomoć nekih rotacija. U ovom slučaju ne možemo jednostavno izvesti cik ili cak rotaciju; moramo implementirati zig zig rotaciju.
Kako bismo čvor 1 napravili kao korijenski čvor, moramo izvesti dvije desne rotacije poznate kao zig zig rotacije. Kada izvršimo desnu rotaciju tada će se 10 pomaknuti prema dolje, a čvor 7 će se pomaknuti prema gore kao što je prikazano na slici ispod:
Opet ćemo izvršiti cik desnu rotaciju, čvor 7 će se pomaknuti prema dolje, a čvor 1 će se podići prema gore kao što je prikazano u nastavku:
Kao što vidimo na gornjoj slici, čvor 1 je postao korijenski čvor stabla; dakle, pretraga je završena.
Pretpostavimo da želimo pretražiti 20 u donjem stablu.
Da bismo pretražili 20, moramo izvesti dvije rotacije ulijevo. Slijede koraci potrebni za pretraživanje 20 čvora:
Korak 1: Prvo izvodimo standardnu operaciju BST pretraživanja. Kako je 20 veće od 10 i 15, bit će desno od čvora 15.
Korak 2: Drugi korak je izvođenje razmaka. U tom slučaju bi se izvršile dvije lijeve rotacije. U prvoj rotaciji, čvor 10 će se pomaknuti prema dolje, a čvor 15 će se pomaknuti prema gore kao što je prikazano u nastavku:
U drugoj lijevoj rotaciji, čvor 15 će se pomaknuti prema dolje, a čvor 20 postaje korijenski čvor stabla, kao što je prikazano u nastavku:
Kao što smo primijetili da se izvode dvije lijeve rotacije; pa je poznata kao zig zig lijeva rotacija.
Do sada smo čitali da su i roditelj i baka ili djed u RR ili LL vezi. Sada ćemo vidjeti RL ili LR odnos između roditelja i bake i djeda.
Razmotrimo ovaj slučaj kroz primjer.
Pretpostavimo da želimo pretražiti 13 elemenata u stablu koje je prikazano u nastavku:
Korak 1: Prvo izvodimo standardnu operaciju BST pretraživanja. Kako je 13 veće od 10, ali manje od 15, tako će čvor 13 biti lijevi dijete čvora 15.
Korak 2: Budući da je čvor 13 lijevo od 15, a čvor 15 desno od čvora 10, tako da RL odnos postoji. Prvo izvodimo desnu rotaciju na čvoru 15, a 15 će se pomaknuti prema dolje, a čvor 13 će doći prema gore, kao što je prikazano u nastavku:
Ipak, čvor 13 nije korijenski čvor, a 13 je desno od korijenskog čvora, pa ćemo izvršiti lijevu rotaciju poznatu kao zag rotacija. Čvor 10 će se pomaknuti prema dolje, a 13 postaje korijenski čvor kao što je prikazano u nastavku:
Kao što možemo primijetiti u gornjem stablu da je čvor 13 postao korijenski čvor; dakle, pretraga je završena. U ovom slučaju, prvo smo izveli cik rotaciju, a zatim cak rotaciju; pa je to poznato kao cik-cak rotacija.
Razmotrimo ovaj slučaj kroz primjer.
Pretpostavimo da želimo pretražiti 9 elemenata u stablu, koje je prikazano u nastavku:
Korak 1: Prvo izvodimo standardnu operaciju BST pretraživanja. Kako je 9 manje od 10, ali veće od 7, to će biti pravo dijete čvora 7.
Korak 2: Pošto je čvor 9 desno od čvora 7, a čvor 7 je lijevo od čvora 10, tako da LR odnos postoji. Prvo izvodimo lijevu rotaciju na čvoru 7. Čvor 7 će se pomaknuti prema dolje, a čvor 9 prema gore kao što je prikazano u nastavku:
Ipak, čvor 9 nije korijenski čvor, a 9 je lijevo od korijenskog čvora, tako da ćemo izvesti desnu rotaciju poznatu kao zig rotacija. Nakon izvođenja prave rotacije, čvor 9 postaje korijenski čvor, kao što je prikazano u nastavku:
Kao što možemo primijetiti u gornjem stablu da je čvor 13 korijenski čvor; dakle, pretraga je završena. U ovom slučaju prvo smo izvršili cak rotaciju (lijeva rotacija), a zatim se izvodi cik rotacija (desna rotacija), pa je poznata kao cak cik rotacija.
Prednosti Splay stabla
- U splay stablu ne trebamo pohranjivati dodatne informacije. Nasuprot tome, u AVL stablima moramo pohraniti faktor ravnoteže svakog čvora koji zahtijeva dodatni prostor, a crveno-crna stabla također zahtijevaju pohranu jednog dodatnog bita informacija koje označavaju boju čvora, crvenu ili crnu.
- To je najbrži tip stabla binarnog pretraživanja za razne praktične primjene. Koristi se u Windows NT i GCC prevoditelji .
- Omogućuje bolju izvedbu budući da će se čvorovi kojima se često pristupa pomaknuti bliže korijenskom čvoru, zbog čega se elementima može brzo pristupiti u splay stablima. Koristi se u implementaciji predmemorije jer se nedavno pristupljeni podaci pohranjuju u predmemoriju tako da ne moramo ići u memoriju za pristup podacima, a potrebno je i manje vremena.
Nedostatak Splay stabla
Glavni nedostatak raštrkanog stabla bi bio da stabla nisu strogo uravnotežena, tj. grubo su uravnotežena. Ponekad su razmaknuta stabla linearna, pa će biti potrebno O(n) vremena složenosti.
Operacija umetanja u Splay stablo
u umetanje prvo umetnemo element u stablo, a zatim izvršimo operaciju raspršivanja na umetnutom elementu.
15, 10, 17, 7
Korak 1: Prvo u stablo umetnemo čvor 15. Nakon umetanja potrebno je izvršiti razmicanje. Kako je 15 korijenski čvor, tako da ne trebamo izvoditi razmicanje.
Korak 2: Sljedeći element je 10. Kako je 10 manje od 15, tako da će čvor 10 biti lijevi dijete čvora 15, kao što je prikazano u nastavku:
Sada, mi izvodimo razbacujući se . Da bismo napravili 10 kao korijenski čvor, izvršit ćemo desnu rotaciju, kao što je prikazano u nastavku:
Korak 3: Sljedeći element je 17. Kako je 17 veći od 10 i 15, on će postati pravo dijete čvora 15.
Sada ćemo izvesti razbacivanje. Kako 17 godina ima roditelja, kao i baku i djeda, izvodit ćemo cik-cik rotacije.
Na gornjoj slici možemo uočiti da 17 postaje korijenski čvor stabla; dakle, umetanje je završeno.
Korak 4: Sljedeći element je 7. Kako je 7 manje od 17, 15 i 10, tako da će čvor 7 biti lijevo dijete od 10.
Sada, moramo raširiti drvo. Kako 7 ima roditelja, kao i baku i djeda, izvršit ćemo dvije desne rotacije kao što je prikazano u nastavku:
Ipak, čvor 7 nije korijenski čvor, on je lijevi dijete korijenskog čvora, tj. 17. Dakle, moramo izvršiti još jednu rotaciju udesno da bi čvor 7 postao korijenski čvor kao što je prikazano u nastavku:
Algoritam za operaciju umetanja
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)
U gornjem algoritmu, T je stablo, a n je čvor koji želimo umetnuti. Stvorili smo privremenu varijablu koja sadrži adresu korijenskog čvora. Pokretat ćemo while petlju dok vrijednost temp ne postane NULL.
Nakon što je umetanje dovršeno, izvršit će se razmicanje
Algoritam za rad 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
U gornjoj implementaciji, x je čvor na kojem se izvodi rotacija, dok je y lijevi dijete čvora x.
Implementacija left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
U gornjoj implementaciji, x je čvor na kojem se izvodi rotacija, a y je desno dijete čvora x.
Brisanje u Splay stablu
Kao što znamo da su splay stabla varijante binarnog stabla pretraživanja, pa bi operacija brisanja u splay stablu bila slična BST-u, ali jedina razlika je u tome što nakon operacije brisanja u splay stablima slijedi operacija splayinga.
Vrste brisanja:
Postoje dvije vrste brisanja u splay stablima:
- Širenje odozdo prema gore
- Širenje odozgo prema dolje
Širenje odozdo prema gore
Kod odozdo prema gore, prvo brišemo element iz stabla, a zatim izvodimo širenje na izbrisanom čvoru.
Hajdemo razumjeti brisanje u Splay stablu.
Pretpostavimo da želimo izbrisati 12, 14 iz dolje prikazanog stabla:
u string metodu java
- Prvo, jednostavno izvodimo standardnu operaciju brisanja BST da obrišemo 12 elementa. Kako je 12 čvor lista, tako da jednostavno brišemo čvor iz stabla.
Brisanje još uvijek nije dovršeno. Moramo raširiti nadređeni čvor izbrisanog čvora, tj. 10. Moramo izvršiti Širenje (10) na stablu. Kao što možemo primijetiti u gornjem stablu da je 10 desno od čvora 7, a čvor 7 lijevo od čvora 13. Dakle, prvo izvodimo lijevu rotaciju na čvoru 7, a zatim izvodimo desnu rotaciju na čvoru 13, kao što je prikazano u nastavku:
Ipak, čvor 10 nije korijenski čvor; čvor 10 je lijevi dijete korijenskog čvora. Dakle, moramo izvršiti pravu rotaciju na korijenskom čvoru, tj. 14 da bi čvor 10 postao korijenski čvor kao što je prikazano u nastavku:
- Sada moramo izbrisati element 14 iz stabla, koji je prikazan ispod:
Kao što znamo, ne možemo jednostavno izbrisati unutarnji čvor. Zamijenit ćemo vrijednost čvora pomoću inorder prethodnik ili po redu nasljednik . Pretpostavimo da koristimo inorder nasljednika u kojem vrijednost zamjenjujemo najnižom vrijednošću koja postoji u desnom podstablu. Najniža vrijednost u desnom podstablu čvora 14 je 15, tako da vrijednost 14 zamjenjujemo s 15. Budući da čvor 14 postaje lisni čvor, možemo ga jednostavno izbrisati kao što je prikazano u nastavku:
Ipak, brisanje nije dovršeno. Moramo izvršiti još jednu operaciju, tj. splaying u kojoj trebamo roditelj izbrisanog čvora učiniti root čvorom. Prije brisanja, roditelj čvora 14 bio je korijenski čvor, tj. 10, tako da u ovom slučaju trebamo izvršiti bilo kakvo širenje.
Širenje odozgo prema dolje
Kod širenja odozgo prema dolje, prvo izvodimo širenje na kojem treba izvršiti brisanje, a zatim brišemo čvor iz stabla. Nakon što je element izbrisan, izvršit ćemo operaciju spajanja.
Razmotrimo širenje odozgo prema dolje kroz primjer.
Pretpostavimo da želimo izbrisati 16 iz stabla koje je prikazano u nastavku:
Korak 1: Kod širenja odozgo prema dolje, prvo izvodimo širenje na čvoru 16. Čvor 16 ima i roditelja i baku i djeda. Čvor 16 je s desne strane svog roditelja, a roditeljski čvor je također s desne strane svog roditelja, tako da je ovo zag zag situacija. U ovom slučaju, prvo ćemo izvesti lijevu rotaciju na čvoru 13, a zatim 14 kao što je prikazano u nastavku:
Čvor 16 još uvijek nije korijenski čvor, a desno je dijete korijenskog čvora, tako da moramo izvesti lijevu rotaciju na čvoru 12 da bi čvor 16 postao korijenski čvor.
Jednom kada čvor 16 postane korijenski čvor, izbrisat ćemo čvor 16 i dobit ćemo dva različita stabla, tj. lijevo podstablo i desno podstablo kao što je prikazano u nastavku:
Kao što znamo da su vrijednosti lijevog podstabla uvijek manje od vrijednosti desnog podstabla. Korijen lijevog podstabla je 12, a korijen desnog podstabla je 17. Prvi korak je pronaći najveći element u lijevom podstablu. U lijevom podstablu maksimalni element je 15, a zatim moramo izvršiti operaciju širenja na 15.
Kao što možemo vidjeti u gornjem stablu, element 15 ima roditelja kao i baku i djeda. Čvor je desno od svog roditelja, a roditeljski čvor je također desno od svog roditelja, tako da moramo izvesti dvije rotacije ulijevo da čvor 15 postane korijenski čvor kao što je prikazano u nastavku:
Nakon izvođenja dvije rotacije na stablu, čvor 15 postaje korijenski čvor. Kao što vidimo, desno dijete od 15 je NULL, tako da prilažemo čvor 17 na desni dio od 15 kao što je prikazano u nastavku, a ova operacija je poznata kao pridružiti operacija.
Napomena: Ako element nije prisutan u splay stablu, koji se želi izbrisati, tada će se izvršiti splaying. Širenje bi se izvršilo na posljednjem pristupljenom elementu prije dostizanja NULL.
Algoritam operacije brisanja
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
U gornjem algoritmu prvo provjeravamo je li korijen Null ili ne; ako je korijen NULL znači da je stablo prazno. Ako stablo nije prazno, izvršit ćemo operaciju raspršivanja na elementu koji treba izbrisati. Nakon što je operacija širenja dovršena, usporedit ćemo korijenske podatke s elementom koji treba izbrisati; ako oba nisu jednaka znači da element nije prisutan u stablu. Ako su jednaki, mogu se pojaviti sljedeći slučajevi:
Slučaj 1 : Lijevo od korijena je NULL, desno od korijena postaje korijenski čvor.
Slučaj 2 : Ako postoje i lijevo i desno, tada širimo maksimalni element u lijevom podstablu. Kada se raspršivanje završi, maksimalni element postaje korijen lijevog podstabla. Desno podstablo bi postalo desno dijete korijena lijevog podstabla.