Splay drevesa so samouravnotežena ali samonastavljena binarna iskalna drevesa. Z drugimi besedami, lahko rečemo, da so razpršena drevesa različice binarnih iskalnih dreves. Predpogoj za splay drevesa, ki bi ga morali vedeti o binarnih iskalnih drevesih.
Kot že vemo, je časovna kompleksnost binarnega iskalnega drevesa v vsakem primeru. Časovna zahtevnost binarnega iskalnega drevesa v povprečnem primeru je O (prijava) in časovna kompleksnost v najslabšem primeru je O(n). V binarnem iskalnem drevesu je vrednost levega poddrevesa manjša od korenskega vozlišča, vrednost desnega poddrevesa pa večja od korenskega vozlišča; v tem primeru bi bila časovna zapletenost O (prijava) . Če je binarno drevo nagnjeno levo ali desno, bi bila časovna kompleksnost O(n). Za omejitev asimetrije, AVL in rdeče-črno drevo prišel v sliko, ob O(prijava ) časovna zahtevnost za vse operacije v vseh primerih. To časovno zapletenost lahko izboljšamo tudi z več praktičnimi izvedbami, tako da novo drevo Kaj je drevo razcepa?
Drevo, ki se razteza, je samouravnotežno drevo, vendar Drevesi AVL in Rdeče-črna sta torej tudi drevesi, ki se samouravnotežita. Kaj naredi splay drevo edinstveno dve drevesi. Ima eno dodatno lastnost, zaradi katere je edinstven, in sicer razpršenost.
Splay drevo vsebuje enake operacije kot a Binarno iskalno drevo , to je vstavljanje, brisanje in iskanje, vsebuje pa še eno operacijo, to je razprševanje. torej. vsem operacijam v splay drevesu sledi splaying.
Splay drevesa niso strogo uravnotežena drevesa, vendar so približno uravnotežena drevesa. Razumejmo operacijo iskanja v splay-drevu.
Recimo, da želimo iskati 7 elementov v drevesu, ki je prikazano spodaj:
Za iskanje katerega koli elementa v splay drevesu bomo najprej izvedli standardno operacijo binarnega iskalnega drevesa. Ker je 7 manj kot 10, bomo prišli levo od korenskega vozlišča. Po izvedbi iskanja moramo izvesti razprtje. Tukaj razprtje pomeni, da mora operacija, ki jo izvajamo na katerem koli elementu, po izvedbi nekaterih preureditev postati korensko vozlišče. Preureditev drevesa bo izvedena z kolobarjenjem.
Opomba: Razmaknjeno drevo je mogoče definirati kot samoprilagojeno drevo, v katerem bi katera koli operacija, izvedena na elementu, prerazporedila drevo, tako da element, na katerem je bila izvedena operacija, postane korensko vozlišče drevesa.
Rotacije
Obstaja šest vrst vrtenja, ki se uporabljajo za razpenjanje:
- Zig rotacija (desna rotacija)
- Zag vrtenje (Levo vrtenje)
- Cik cak (Cik, ki mu sledi cak)
- Zag zig (Zag, ki mu sledi zig)
- Zig zig (dva zasuka v desno)
- Zag zag (dve levi rotaciji)
Dejavniki, potrebni za izbiro vrste rotacije
Za izbiro vrste rotacije se uporabljajo naslednji dejavniki:
- Ali ima vozlišče, ki ga poskušamo zasukati, starega starša?
- Ali je vozlišče levi ali desni otrok nadrejenega?
- Je vozlišče levi ali desni otrok starega starša?
Etuiji za rotacije
1. primer: Če vozlišče nima starega starša in če je desni otrok starša, potem izvedemo levo rotacijo; sicer se izvede prava rotacija.
2. primer: Če ima vozlišče starega starša, potem na podlagi naslednjih scenarijev; rotacija bi bila izvedena:
1. scenarij: Če je vozlišče desno od nadrejenega in je nadrejeni prav tako desno od svojega nadrejenega, potem cik cik desno desno vrtenje se izvaja.
Scenarij 2: Če je vozlišče levo od nadrejenega, vendar je nadrejeni desno od svojega nadrejenega, potem cik cak desno levo vrtenje se izvaja.
Scenarij 3: Če je vozlišče desno od nadrejenega in je nadrejeni desno od svojega nadrejenega, potem cik cik levo levo vrtenje se izvaja.
Scenarij 4: Če je vozlišče desno od nadrejenega, vendar je nadrejeni levo od svojega nadrejenega, potem cik cak rotacija desno-levo se izvaja.
Zdaj pa poglejmo zgornje rotacije s primeri.
Za preureditev drevesa moramo izvesti nekaj vrtljajev. Naslednje so vrste vrtenja v drevesu raztezanja:
Cik rotacije se uporabljajo, kadar je element, ki ga je treba iskati, korensko vozlišče ali podrejeni del korenskega vozlišča (tj. levi ali desni podrejeni).
Spodaj so primeri, ki lahko obstajajo v drevesu splay med iskanjem:
1. primer: Če je iskalni element korensko vozlišče drevesa.
2. primer: Če je iskalni element podrejeni korenskemu vozlišču, bosta tam dva scenarija:
- Če je otrok levi otrok, se izvede desna rotacija, znana kot cik desna rotacija.
- Če je otrok desni otrok, bo izvedena rotacija v levo, znana kot cik rotacija v levo.
Oglejmo si zgornja dva scenarija na primeru.
Razmislite o spodnjem primeru:
V zgornjem primeru moramo iskati 7 elementov v drevesu. Sledili bomo spodnjim korakom:
Korak 1: Najprej primerjamo 7 s korenskim vozliščem. Ker je 7 manj kot 10, je levi otrok korenskega vozlišča.
2. korak: Ko najdemo element, bomo izvedli razprševanje. Desna rotacija se izvede tako, da 7 postane korensko vozlišče drevesa, kot je prikazano spodaj:
Poglejmo še en primer.
V zgornjem primeru moramo iskati 20 elementov v drevesu. Sledili bomo spodnjim korakom:
Korak 1: Najprej primerjamo 20 s korenskim vozliščem. Ker je 20 večje od korenskega vozlišča, je desni otrok korenskega vozlišča.
2. korak: Ko najdemo element, bomo izvedli razprševanje. Leva rotacija se izvede tako, da 20 element postane korensko vozlišče drevesa.
Včasih pride do situacije, ko ima predmet, ki ga je treba preiskati, starša in starega starša. V tem primeru moramo za razpenjanje izvesti štiri rotacije.
Razumejmo ta primer s primerom.
Recimo, da moramo iskati 1 element v drevesu, ki je prikazan spodaj:
Korak 1: Najprej moramo izvesti standardno operacijo iskanja BST, da poiščemo element 1. Ker je 1 manjši od 10 in 7, bo levo od vozlišča 7. Zato ima element 1 nadrejenega, tj. 7, pa tudi starega starša, tj. 10.
2. korak: V tem koraku moramo izvesti razpenjanje. Vozlišče 1 moramo narediti kot korensko vozlišče s pomočjo nekaj rotacij. V tem primeru ne moremo preprosto izvesti cik ali cak vrtenja; izvajati moramo cik cik rotacijo.
Da naredimo vozlišče 1 kot korensko vozlišče, moramo izvesti dve desni rotaciji, znani kot cik cik rotacije. Ko izvedemo pravo rotacijo, se bo 10 pomaknilo navzdol, vozlišče 7 pa navzgor, kot je prikazano na spodnji sliki:
Spet bomo izvedli cik desno rotacijo, vozlišče 7 se bo premaknilo navzdol, vozlišče 1 pa se bo dvignilo, kot je prikazano spodaj:
Kot opazimo na zgornji sliki, je vozlišče 1 postalo korensko vozlišče drevesa; torej je iskanje končano.
Recimo, da želimo poiskati 20 v spodnjem drevesu.
Za iskanje 20 moramo izvesti dve levi rotaciji. Za iskanje vozlišča 20 so potrebni naslednji koraki:
Korak 1: Najprej izvedemo standardno operacijo iskanja BST. Ker je 20 večje od 10 in 15, bo desno od vozlišča 15.
2. korak: Drugi korak je izvedba razpršitve. V tem primeru bi se izvedli dve levi rotaciji. Pri prvi rotaciji se bo vozlišče 10 premaknilo navzdol, vozlišče 15 pa navzgor, kot je prikazano spodaj:
Pri drugi levi rotaciji se vozlišče 15 premakne navzdol, vozlišče 20 pa postane korensko vozlišče drevesa, kot je prikazano spodaj:
Kot smo opazili, se izvajata dve levi rotaciji; zato je znana kot cik cik rotacija v levo.
Do zdaj smo prebrali, da sta oba starša in stari starš v razmerju RR ali LL. Zdaj bomo videli odnos RL ali LR med staršem in starim staršem.
Razumejmo ta primer s primerom.
Recimo, da želimo iskati 13 elementov v drevesu, ki je prikazano spodaj:
Korak 1: Najprej izvedemo standardno operacijo iskanja BST. Ker je 13 večje od 10, a manjše od 15, bo vozlišče 13 levi otrok vozlišča 15.
2. korak: Ker je vozlišče 13 levo od 15 in vozlišče 15 desno od vozlišča 10, torej obstaja razmerje RL. Najprej izvedemo desno rotacijo na vozlišču 15 in 15 se bo premaknilo navzdol, vozlišče 13 pa se bo dvignilo navzgor, kot je prikazano spodaj:
Kljub temu vozlišče 13 ni korensko vozlišče in 13 je desno od korenskega vozlišča, zato bomo izvedli levo rotacijo, znano kot zag rotacija. Vozlišče 10 se bo premaknilo navzdol, 13 pa bo postalo korensko vozlišče, kot je prikazano spodaj:
Kot lahko opazimo v zgornjem drevesu, je vozlišče 13 postalo korensko vozlišče; torej je iskanje končano. V tem primeru smo najprej izvedli cik rotacijo in nato zak rotacijo; zato je znana kot cik cak rotacija.
Razumejmo ta primer s primerom.
Recimo, da želimo iskati 9 elementov v drevesu, ki je prikazano spodaj:
Korak 1: Najprej izvedemo standardno operacijo iskanja BST. Ker je 9 manjše od 10, vendar večje od 7, bo to pravi podrejeni element vozlišča 7.
2. korak: Ker je vozlišče 9 desno od vozlišča 7, vozlišče 7 pa levo od vozlišča 10, torej obstaja razmerje LR. Najprej izvedemo levo rotacijo na vozlišču 7. Vozlišče 7 se bo premaknilo navzdol, vozlišče 9 pa navzgor, kot je prikazano spodaj:
Kljub temu vozlišče 9 ni korensko vozlišče in 9 je levo od korenskega vozlišča, zato bomo izvedli desno rotacijo, znano kot cik rotacija. Po izvedbi pravilne rotacije vozlišče 9 postane korensko vozlišče, kot je prikazano spodaj:
Kot lahko opazimo v zgornjem drevesu, je vozlišče 13 korensko vozlišče; torej je iskanje končano. V tem primeru smo najprej izvedli zag rotacijo (levo rotacijo), nato pa se izvede cik rotacija (desna rotacija), zato jo poznamo kot zag cik rotacijo.
Prednosti drevesa Splay
- V splay drevesu nam ni treba shranjevati dodatnih informacij. Nasprotno pa moramo v drevesih AVL shraniti faktor ravnotežja vsakega vozlišča, ki zahteva dodaten prostor, rdeče-črna drevesa pa zahtevajo tudi shranjevanje enega dodatnega bita informacije, ki označuje barvo vozlišča, bodisi rdečo bodisi črno.
- Je najhitrejši tip binarnega iskalnega drevesa za različne praktične aplikacije. Uporablja se v Prevajalniki Windows NT in GCC .
- Zagotavlja boljšo zmogljivost, saj se bodo pogosto dostopna vozlišča premaknila bližje korenskemu vozlišču, zaradi česar je mogoče hitro dostopati do elementov v razmaknjenih drevesih. Uporablja se v izvedbi predpomnilnika, saj se podatki, do katerih smo nedavno dostopali, shranijo v predpomnilnik, tako da nam za dostop do podatkov ni treba iti v pomnilnik, in traja manj časa.
Pomanjkljivost drevesa Splay
Največja pomanjkljivost raztegnjenega drevesa bi bila, da drevesa niso strogo uravnotežena, tj. so približno uravnotežena. Včasih so raztegnjena drevesa linearna, zato bo trajalo O(n) časovno kompleksno.
Operacija vstavljanja v drevo Splay
V vstavljanje najprej vstavimo element v drevo in nato izvedemo operacijo razpršitve na vstavljenem elementu.
15, 10, 17, 7
Korak 1: Najprej v drevo vstavimo vozlišče 15. Po vstavitvi moramo izvesti razpenjanje. Ker je 15 korensko vozlišče, nam ni treba izvajati razpršitve.
2. korak: Naslednji element je 10. Ker je 10 manj kot 15, bo vozlišče 10 levi podrejeni element vozlišča 15, kot je prikazano spodaj:
Zdaj nastopamo raztezanje . Da naredimo 10 kot korensko vozlišče, bomo izvedli pravo rotacijo, kot je prikazano spodaj:
3. korak: Naslednji element je 17. Ker je 17 večji od 10 in 15, bo postal desni podrejeni element vozlišča 15.
Zdaj bomo izvedli razpenjanje. Ker ima 17 starša, pa tudi starega starša, bomo izvajali cik cik rotacije.
Na zgornji sliki lahko opazimo, da 17 postane korensko vozlišče drevesa; zato je vstavljanje končano.
4. korak: Naslednji element je 7. Ker je 7 manj kot 17, 15 in 10, bo vozlišče 7 ostalo podrejeno od 10.
Zdaj pa moramo drevo razpokati. Ker ima 7 starša in starega starša, bomo izvedli dve desni rotaciji, kot je prikazano spodaj:
Kljub temu vozlišče 7 ni korensko vozlišče, je levi otrok korenskega vozlišča, tj. 17. Torej, moramo izvesti še eno desno rotacijo, da naredimo vozlišče 7 kot korensko vozlišče, kot je prikazano spodaj:
Algoritem za operacijo vstavljanja
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)
V zgornjem algoritmu je T drevo, n pa vozlišče, ki ga želimo vstaviti. Ustvarili smo začasno spremenljivko, ki vsebuje naslov korenskega vozlišča. Zanko while bomo izvajali, dokler vrednost temp ne postane NULL.
Ko je vstavljanje končano, se izvede raztezanje
Algoritem za operacijo predvajanja
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
V zgornji izvedbi je x vozlišče, na katerem se izvaja rotacija, medtem ko je y levi otrok vozlišča x.
Implementacija left.rotation(T, x)
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
V zgornji izvedbi je x vozlišče, na katerem se izvaja rotacija, y pa desni podrejeni otrok vozlišča x.
Izbris v drevesu Splay
Ker vemo, da so razmaknjena drevesa različice binarnega iskalnega drevesa, bi bila operacija brisanja v razmaknjenem drevesu podobna BST, vendar je edina razlika ta, da operaciji brisanja v razmaknjenih drevesih sledi operacija razpršitve.
Vrste izbrisa:
Obstajata dve vrsti izbrisov v splay drevesih:
- Šivanje od spodaj navzgor
- Šivanje od zgoraj navzdol
Šivanje od spodaj navzgor
Pri razprševanju od spodaj navzgor najprej izbrišemo element iz drevesa in nato izvedemo razprševanje na izbrisanem vozlišču.
Razumejmo brisanje v drevesu Splay.
Recimo, da želimo izbrisati 12, 14 iz drevesa, prikazanega spodaj:
zbirka podatkov
- Najprej preprosto izvedemo standardno operacijo brisanja BST, da izbrišemo 12 elementov. Ker je 12 listno vozlišče, ga preprosto izbrišemo iz drevesa.
Brisanje še vedno ni končano. Razširiti moramo nadrejeno vozlišče izbrisanega vozlišča, tj. 10. Izvesti moramo Raztegovanje (10) na drevesu. Kot lahko opazimo v zgornjem drevesu, je 10 desno od vozlišča 7, vozlišče 7 pa levo od vozlišča 13. Torej, najprej izvedemo levo rotacijo na vozlišču 7 in nato izvedemo desno rotacijo na vozlišču 13, kot je prikazano spodaj:
Kljub temu vozlišče 10 ni korensko vozlišče; vozlišče 10 je levi otrok korenskega vozlišča. Torej moramo izvesti pravo rotacijo na korenskem vozlišču, tj. 14, da bo vozlišče 10 postalo korensko vozlišče, kot je prikazano spodaj:
- Zdaj moramo izbrisati element 14 iz drevesa, ki je prikazano spodaj:
Kot vemo, notranjega vozlišča ne moremo preprosto izbrisati. Vrednost vozlišča bomo nadomestili z uporabo inorder predhodnik oz inorder naslednik . Recimo, da uporabimo naslednika po vrstnem redu, v katerem zamenjamo vrednost z najnižjo vrednostjo, ki obstaja v desnem poddrevesu. Najnižja vrednost v desnem poddrevesu vozlišča 14 je 15, zato vrednost 14 zamenjamo s 15. Ker vozlišče 14 postane listno vozlišče, ga lahko preprosto izbrišemo, kot je prikazano spodaj:
Kljub temu izbris še ni končan. Izvesti moramo še eno operacijo, tj. razširitev, pri kateri moramo nadrejeno vozlišče narediti za korensko vozlišče. Pred izbrisom je bilo nadrejeno vozlišče 14 korensko vozlišče, tj. 10, zato moramo v tem primeru izvesti kakršno koli razširjanje.
Šivanje od zgoraj navzdol
Pri širjenju od zgoraj navzdol najprej izvedemo širjenje, na katerem naj se izvede brisanje, nato pa izbrišemo vozlišče iz drevesa. Ko je element izbrisan, bomo izvedli operacijo pridružitve.
Razumejmo raztezanje od zgoraj navzdol na primeru.
Recimo, da želimo izbrisati 16 iz drevesa, ki je prikazano spodaj:
Korak 1: Pri širjenju od zgoraj navzdol najprej izvedemo širjenje na vozlišču 16. Vozlišče 16 ima tako nadrejenega kot tudi starega nadrejenega. Vozlišče 16 je na desni strani svojega nadrejenega in nadrejeno vozlišče je prav tako na desni strani svojega nadrejenega, tako da je to zag zag situacija. V tem primeru bomo najprej izvedli levo rotacijo na vozlišču 13 in nato 14, kot je prikazano spodaj:
Vozlišče 16 še vedno ni korensko vozlišče in je desni otrok korenskega vozlišča, zato moramo na vozlišču 12 izvesti levo rotacijo, da naredimo vozlišče 16 kot korensko vozlišče.
Ko vozlišče 16 postane korensko vozlišče, bomo izbrisali vozlišče 16 in dobili bomo dve različni drevesi, tj. levo poddrevo in desno poddrevo, kot je prikazano spodaj:
Kot vemo, so vrednosti levega poddrevesa vedno manjše od vrednosti desnega poddrevesa. Koren levega poddrevesa je 12, koren desnega poddrevesa pa 17. Prvi korak je najti največji element v levem poddrevesu. V levem poddrevesu je največji element 15, nato pa moramo izvesti operacijo razprševanja na 15.
Kot lahko opazimo v zgornjem drevesu, ima element 15 tako starša kot starega starša. Vozlišče je desno od svojega nadrejenega in nadrejeno vozlišče je prav tako desno od svojega nadrejenega, zato moramo izvesti dve rotaciji v levo, da naredimo vozlišče 15 korensko vozlišče, kot je prikazano spodaj:
Po izvedbi dveh rotacij na drevesu vozlišče 15 postane korensko vozlišče. Kot lahko vidimo, je desni otrok 15 NULL, zato pritrdimo vozlišče 17 na desni del 15, kot je prikazano spodaj, in ta operacija je znana kot pridruži se delovanje.
Opomba: Če element ni prisoten v drevesu razpršitve, ki ga je treba izbrisati, se bo izvedlo razprševanje. Razprševanje bi bilo izvedeno na zadnjem dostopanem elementu, preden bi dosegli NULL.
Algoritem delovanja Delete
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
V zgornjem algoritmu najprej preverimo, ali je koren nič ali ne; če je koren NULL, pomeni, da je drevo prazno. Če drevo ni prazno, bomo izvedli operacijo razpršitve na elementu, ki ga želimo izbrisati. Ko je operacija razprševanja končana, bomo korenske podatke primerjali z elementom, ki ga želimo izbrisati; če oba nista enaka, pomeni, da element ni prisoten v drevesu. Če sta enaka, lahko pride do naslednjih primerov:
Primer 1 : Levo od korena je NULL, desno od korena postane korensko vozlišče.
Primer 2 : Če obstajata tako leva kot desna, potem razširimo največji element v levem poddrevesu. Ko je razprševanje končano, največji element postane koren levega poddrevesa. Desno poddrevo bi postalo desni otrok korena levega poddrevesa.