Splay-puut ovat itsetasapainottavia tai itsesäätyviä binäärihakupuita. Toisin sanoen voidaan sanoa, että splay-puut ovat muunnelmia binäärihakupuista. Splay-puiden edellytys, joka meidän pitäisi tietää binäärihakupuista.
Kuten jo tiedämme, binaarihakupuun aika monimutkaisuus joka tapauksessa. Binaarihakupuun aikamonimutkaisuus keskimääräisessä tapauksessa on O (kirjaudu sisään) ja aika monimutkaisuus pahimmassa tapauksessa on O(n). Binäärihakupuussa vasemman alipuun arvo on pienempi kuin juurisolmun ja oikean alipuun arvo on suurempi kuin juurisolmun; tässä tapauksessa aika monimutkaisuus olisi O (kirjaudu sisään) . Jos binääripuu on vasemmalle tai oikealle vino, niin aikamonimutkaisuus olisi O(n). Vinouden rajoittamiseksi AVL ja punainen-musta puu tuli kuvaan, ottaa O(logn ) aika monimutkaisuus kaikissa toiminnoissa kaikissa tapauksissa. Voimme myös parantaa tämän ajan monimutkaisuutta tekemällä käytännönläheisempiä toteutuksia, joten uusi Tree Mikä on Splay Tree?
Splay-puu on itsetasapainottava puu, mutta AVL- ja Red-Black-puut ovat silloin myös itsetasapainottavia puita. Mikä tekee splay-puusta ainutlaatuisen kaksi puuta. Siinä on yksi ylimääräinen ominaisuus, joka tekee siitä ainutlaatuisen, on splaying.
Splay-puu sisältää samat toiminnot kuin a Binäärihakupuu , eli lisäys, poisto ja haku, mutta se sisältää myös yhden lisätoiminnon, eli toiston. Niin. kaikkia leikkauspuun toimintoja seuraa splay.
Splay-puut eivät ole tiukasti tasapainotettuja puita, mutta ne ovat karkeasti tasapainotettuja puita. Ymmärretään hakutoiminto splay-puussa.
Oletetaan, että haluamme etsiä 7 elementtiä puusta, joka näkyy alla:
Jos haluat etsiä mitä tahansa elementtiä esityspuussa, suoritamme ensin tavallisen binaarihakupuun toiminnon. Koska 7 on pienempi kuin 10, tulemme juurisolmun vasemmalle puolelle. Hakutoiminnon suorittamisen jälkeen meidän on suoritettava toisto. Tässä splaying tarkoittaa sitä, että mille tahansa elementille suorittamamme toiminnon tulisi tulla juurisolmuksi joidenkin uudelleenjärjestelyjen jälkeen. Puun uudelleenjärjestely tehdään kiertojen avulla.
Huomautus: Splay-puu voidaan määritellä itsesäätyväksi puuksi, jossa kaikki elementille suoritettavat toiminnot järjestäisivät puun uudelleen siten, että elementistä, jolle toimenpide on suoritettu, tulee puun juurisolmu.
Pyörityksiä
Kiertoon käytetään kuutta tyyppiä:
- Zig-kierto (oikea kierto)
- Zag-kierto (vasemmalle)
- Siksak (siksak ja sen jälkeen sik)
- Zag zig (Zag ja sen jälkeen zig)
- Zig zig (kaksi oikeaa kiertoa)
- Zag zag (kaksi kiertoa vasemmalle)
Pyörimistyypin valinnassa tarvittavat tekijät
Seuraavia tekijöitä käytetään kiertotyypin valinnassa:
- Onko solmulla, jota yritämme kiertää, isovanhempi?
- Onko solmu vanhemman vasen vai oikea lapsi?
- Onko solmu isovanhemman vasen vai oikea lapsi?
Rotaatioiden kotelot
Tapaus 1: Jos solmulla ei ole isovanhempaa ja jos se on vanhemman oikea lapsi, suoritamme vasemman kierron; muussa tapauksessa suoritetaan oikea kierto.
Tapaus 2: Jos solmulla on isovanhempi, seuraavien skenaarioiden perusteella; kierto suoritetaan:
Skenaario 1: Jos solmu on vanhemman oikeus ja vanhempi on myös vanhemman oikeus, niin zig zig oikea oikea kierto on esitetty.
Skenaario 2: Jos solmu on vanhemman vasemmalla, mutta vanhempi on vanhemman oikealla puolella, silloin siksak kierto oikealle vasemmalle on esitetty.
Skenaario 3: Jos solmu on vanhemman oikeassa ja emo on vanhemman oikeassa, niin zig zig vasemmalle vasemmalle kierto on esitetty.
Skenaario 4: Jos solmu on vanhemman oikealla puolella, mutta vanhempi on vanhemman vasen, niin siksak-kierto oikealle-vasemmalle on esitetty.
Ymmärretään nyt yllä olevat kierrokset esimerkkien avulla.
Puun järjestämiseksi uudelleen meidän on suoritettava kiertoja. Seuraavat ovat pyöritystyypit splay-puussa:
Zig-kierroksia käytetään, kun haettava kohde on joko juurisolmu tai juurisolmun ali (eli vasen tai oikea ali).
Seuraavat ovat tapauksia, jotka voivat esiintyä esityspuussa haun aikana:
Tapaus 1: Jos hakukohde on puun juurisolmu.
Tapaus 2: Jos hakukohde on juurisolmun ali, siellä on kaksi skenaariota:
- Jos lapsi on vasen lapsi, suoritettaisiin oikea kierto, joka tunnetaan nimellä zig-oikea kierto.
- Jos lapsi on oikea lapsi, kääntö vasemmalle, joka tunnetaan nimellä zig-vasen kierto.
Katsotaanpa yllä olevia kahta skenaariota esimerkin kautta.
Harkitse alla olevaa esimerkkiä:
Yllä olevassa esimerkissä meidän on etsittävä 7 elementtiä puusta. Noudatamme alla olevia vaiheita:
Vaihe 1: Ensin vertaamme 7:ää juurisolmuun. Koska 7 on pienempi kuin 10, niin se on juurisolmun vasen lapsi.
Vaihe 2: Kun elementti on löydetty, suoritamme leikkaus. Oikea kierto suoritetaan niin, että 7:stä tulee puun juurisolmu alla olevan kuvan mukaisesti:
Tarkastellaanpa toista esimerkkiä.
Yllä olevassa esimerkissä meidän on etsittävä 20 elementtiä puusta. Noudatamme alla olevia vaiheita:
Vaihe 1: Ensin vertaamme 20:tä juurisolmuun. Koska 20 on suurempi kuin juurisolmu, se on juurisolmun oikea lapsi.
Vaihe 2: Kun elementti on löydetty, suoritamme leikkaus. Vasen kierto suoritetaan siten, että 20 elementistä tulee puun juurisolmu.
Joskus syntyy tilanne, kun etsittävällä esineellä on sekä vanhempi että isovanhempi. Tässä tapauksessa meidän on suoritettava neljä kierrosta levitystä varten.
Ymmärretään tämä tapaus esimerkin kautta.
Oletetaan, että meidän on etsittävä 1 elementti puusta, joka näkyy alla:
Vaihe 1: Ensin meidän on suoritettava standardi BST-hakutoiminto, jotta voimme etsiä 1-elementin. Koska 1 on pienempi kuin 10 ja 7, niin se on solmun 7 vasemmalla puolella. Siksi elementillä 1 on vanhempi eli 7 sekä isovanhempi, eli 10.
Vaihe 2: Tässä vaiheessa meidän on suoritettava splaying. Meidän on tehtävä solmu 1 juurisolmuksi joidenkin rotaatioiden avulla. Tässä tapauksessa emme voi yksinkertaisesti suorittaa sik- tai sak-kiertoa; meidän on toteutettava zig zig -kierto.
Jotta solmu 1 voidaan tehdä juurisolmuksi, meidän on suoritettava kaksi oikeaa kiertoa, jotka tunnetaan nimellä zig zig -rotaatiot. Kun suoritamme oikean kierron, 10 liikkuu alaspäin ja solmu 7 nousee ylöspäin alla olevan kuvan mukaisesti:
Teemme jälleen zig-kiertoa oikealle, solmu 7 liikkuu alaspäin ja solmu 1 nousee ylöspäin alla olevan kuvan mukaisesti:
Kuten yllä olevassa kuvassa havaitsemme, solmusta 1 on tullut puun juurisolmu; siksi haku on valmis.
Oletetaan, että haluamme etsiä 20 alla olevasta puusta.
Jotta voisimme etsiä 20, meidän on suoritettava kaksi kiertoa vasemmalle. Seuraavat vaiheet vaaditaan 20 solmun etsimiseen:
Vaihe 1: Ensin suoritamme tavallisen BST-hakutoiminnon. Koska 20 on suurempi kuin 10 ja 15, niin se on solmun 15 oikealla puolella.
Vaihe 2: Toinen vaihe on pelaaminen. Tässä tapauksessa suoritettaisiin kaksi kiertoa vasemmalle. Ensimmäisessä kierrossa solmu 10 liikkuu alaspäin ja solmu 15 liikkuisi ylöspäin alla olevan kuvan mukaisesti:
Toisessa vasemmassa kierrossa solmu 15 liikkuu alaspäin ja solmu 20 tulee puun juurisolmuksi, kuten alla on esitetty:
Kuten olemme havainneet, suoritetaan kaksi kiertoa vasemmalle; joten se tunnetaan zig-zig-kiertona.
Tähän mennessä olemme lukeneet, että sekä vanhempi että isovanhempi ovat joko RR- tai LL-suhteessa. Nyt näemme RL- tai LR-suhteen vanhemman ja isovanhemman välillä.
Ymmärretään tämä tapaus esimerkin kautta.
Oletetaan, että haluamme etsiä 13 elementtiä alla näkyvästä puusta:
Vaihe 1: Ensin suoritamme tavallisen BST-hakutoiminnon. Koska 13 on suurempi kuin 10, mutta pienempi kuin 15, solmu 13 on solmun 15 vasen lapsi.
Vaihe 2: Koska solmu 13 on solmun 15 vasemmalla puolella ja solmu 15 on solmun 10 oikealla puolella, RL-suhde on olemassa. Ensin suoritamme oikean kierron solmulle 15, ja 15 liikkuu alaspäin ja solmu 13 nousee ylöspäin, kuten alla on esitetty:
Silti solmu 13 ei ole juurisolmu, ja 13 on juurisolmun oikealla puolella, joten suoritamme kiertoa vasemmalle, joka tunnetaan nimellä zag-kierto. Solmu 10 liikkuu alaspäin ja 13:sta tulee juurisolmu alla esitetyllä tavalla:
Kuten voimme havaita yllä olevassa puussa, että solmusta 13 on tullut juurisolmu; siksi haku on valmis. Tässä tapauksessa olemme ensin suorittaneet zig-kierron ja sitten zag-kierron; joten se tunnetaan siksak-kiertona.
Ymmärretään tämä tapaus esimerkin kautta.
Oletetaan, että haluamme etsiä 9 elementtiä puusta, joka näkyy alla:
Vaihe 1: Ensin suoritamme tavallisen BST-hakutoiminnon. Koska 9 on pienempi kuin 10 mutta suurempi kuin 7, se on solmun 7 oikea lapsi.
Vaihe 2: Koska solmu 9 on solmun 7 oikealla puolella ja solmu 7 on solmun 10 vasemmalla puolella, LR-suhde on olemassa. Suoritamme ensin kierron vasemmalle solmulle 7. Solmu 7 liikkuu alaspäin ja solmu 9 liikkuu ylöspäin alla olevan kuvan mukaisesti:
Silti solmu 9 ei ole juurisolmu, ja 9 on juurisolmun vasemmalla puolella, joten suoritamme oikean kierron, joka tunnetaan nimellä zig-rotaatio. Kun olet suorittanut oikean kierron, solmusta 9 tulee juurisolmu, kuten alla on esitetty:
Kuten voimme havaita yllä olevassa puussa, että solmu 13 on juurisolmu; siksi haku on valmis. Tässä tapauksessa olemme ensin suorittaneet zig-kierron (vasemmalle), ja sitten suoritetaan sik-kierto (oikea-kierto), joten se tunnetaan zig-kiertona.
Splay-puun edut
- Splay-puussa meidän ei tarvitse tallentaa ylimääräisiä tietoja. Sitä vastoin AVL-puissa meidän on tallennettava jokaisen lisätilaa vaativan solmun tasapainokerroin, ja puna-mustat puut edellyttävät myös yhden ylimääräisen tiedon tallentamista, joka ilmaisee solmun värin, joko punaisen tai mustan.
- Se on nopein binaarihakupuutyyppi erilaisiin käytännön sovelluksiin. Sitä käytetään Windows NT- ja GCC-kääntäjät .
- Se tarjoaa paremman suorituskyvyn, koska usein käytetyt solmut siirtyvät lähemmäs juurisolmua, minkä ansiosta elementit voidaan käyttää nopeasti splay-puissa. Sitä käytetään välimuistitoteutuksessa, koska äskettäin käsitellyt tiedot tallennetaan välimuistiin, joten meidän ei tarvitse mennä muistiin tietojen saamiseksi ja se vie vähemmän aikaa.
Splay-puun haittapuoli
Splay-puun suurin haittapuoli olisi, että puut eivät ole tiukasti tasapainossa, eli ne ovat karkeasti tasapainotettuja. Joskus leikkauspuut ovat lineaarisia, joten se kestää O(n) ajan monimutkaisuutta.
Lisäystoiminto Splay-puussa
Vuonna lisäys -toiminnolla lisäämme elementin ensin puuhun ja sitten suoritamme lisätyn elementin esittelytoiminnon.
15, 10, 17, 7
Vaihe 1: Ensin lisäämme solmun 15 puuhun. Lisäämisen jälkeen meidän on suoritettava leikkaus. Koska 15 on juurisolmu, meidän ei tarvitse suorittaa toistoa.
Vaihe 2: Seuraava elementti on 10. Koska 10 on pienempi kuin 15, niin solmu 10 on solmun 15 vasen lapsi, kuten alla on esitetty:
Nyt esiintyy splaying . Jotta 10 olisi juurisolmu, suoritamme oikean kierron alla olevan kuvan mukaisesti:
Vaihe 3: Seuraava elementti on 17. Koska 17 on suurempi kuin 10 ja 15, siitä tulee solmun 15 oikea lapsi.
Nyt suoritamme pelin. Koska 17-vuotiaalla on sekä vanhempi että isovanhempi, niin teemme sik-sik-kiertoja.
Yllä olevassa kuvassa voimme havaita, että 17:stä tulee puun juurisolmu; siksi lisäys on valmis.
Vaihe 4: Seuraava elementti on 7. Koska 7 on pienempi kuin 17, 15 ja 10, niin solmu 7 jätetään 10:n lapsiksi.
Nyt meidän on leikattava puu. Koska 7:llä on sekä vanhempi että isovanhempi, teemme kaksi oikeaa kiertoa alla olevan kuvan mukaisesti:
Silti solmu 7 ei ole juurisolmu, se on juurisolmun vasen lapsi, eli 17. Joten meidän on suoritettava vielä yksi oikea kierto, jotta solmu 7 saadaan juurisolmuksi, kuten alla on esitetty:
Lisäystoiminnon algoritmi
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)
Yllä olevassa algoritmissa T on puu ja n on solmu, jonka haluamme lisätä. Olemme luoneet temp-muuttujan, joka sisältää juurisolmun osoitteen. Ajetaan while-silmukkaa, kunnes temp-arvosta tulee NULL.
Kun lisäys on valmis, leikkaus suoritetaan
Esitystoiminnan algoritmi
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
Yllä olevassa toteutuksessa x on solmu, jossa kierto suoritetaan, kun taas y on solmun x vasen lapsi.
Vasen.rotation(T, x) toteutus
left.rotation(T, x) y=x->right x->right = y->left y->left = x return y
Yllä olevassa toteutuksessa x on solmu, jossa kierto suoritetaan, ja y on solmun x oikea lapsi.
Poisto Splay-puussa
Kuten tiedämme, että splay-puut ovat muunnelmia binaarihakupuusta, joten poistotoiminto splay-puussa olisi samanlainen kuin BST, mutta ainoa ero on, että poistotoimintoa seuraa splay-puissa splay-toiminto.
Poistotyypit:
Splay-puissa on kahdentyyppisiä poistoja:
- Alhaalta ylöspäin splaying
- Ylhäältä alas pelaaminen
Alhaalta ylöspäin splaying
Alhaalta ylös -toistossa poistamme ensin elementin puusta ja sitten suoritamme toiston poistetulle solmulle.
Ymmärretään poisto Splay-puussa.
Oletetaan, että haluamme poistaa 12, 14 alla olevasta puusta:
hakemiston nimeäminen uudelleen
- Ensin yksinkertaisesti suoritamme tavallisen BST-poistotoiminnon 12 elementin poistamiseksi. Koska 12 on lehtisolmu, poistamme solmun puusta.
Poistaminen ei ole vieläkään valmis. Meidän on levitettävä poistetun solmun vanhempi, eli 10. Meidän on suoritettava Peli (10) puussa. Kuten yllä olevasta puusta voidaan havaita, että 10 on solmun 7 oikealla puolella ja solmu 7 on solmun 13 vasemmalla puolella. Suoritamme siis ensin kierron vasemmalle solmulle 7 ja sitten oikealle solmulle. 13, kuten alla näkyy:
Silti solmu 10 ei ole juurisolmu; solmu 10 on juurisolmun vasen lapsi. Joten meidän on suoritettava oikea rotaatio juurisolmulle, eli 14, jotta solmusta 10 tulee juurisolmu, kuten alla on esitetty:
- Nyt meidän on poistettava 14 elementti puusta, joka näkyy alla:
Kuten tiedämme, emme voi yksinkertaisesti poistaa sisäistä solmua. Korvaamme solmun arvon joko käyttämällä tilauksen edeltäjä tai järjestyksen seuraaja . Oletetaan, että käytämme järjestyksen seuraajaa, jossa korvaamme arvon pienimmällä arvolla, joka on oikeassa alipuussa. Pienin arvo solmun 14 oikeanpuoleisessa alipuussa on 15, joten korvaamme arvon 14 15:llä. Koska solmusta 14 tulee lehtisolmu, voimme yksinkertaisesti poistaa sen alla olevan kuvan mukaisesti:
Silti poisto ei ole vielä valmis. Meidän on suoritettava vielä yksi operaatio, eli splaying, jossa meidän on tehtävä poistetun solmun emo pääsolmuksi. Ennen poistamista solmun 14 emo oli juurisolmu eli 10, joten tässä tapauksessa meidän on suoritettava kaikki toistot.
Ylhäältä alas pelaaminen
Ylhäältä alas -toistossa suoritamme ensin toiston, jossa poisto tehdään, ja sitten poistamme solmun puusta. Kun elementti on poistettu, suoritamme liitostoiminnon.
Ymmärretään ylhäältä alas -pelaaminen esimerkin kautta.
Oletetaan, että haluamme poistaa 16 alla näkyvästä puusta:
Vaihe 1: Ylhäältä alas -peleissä suoritamme ensin toiston solmulle 16. Solmulla 16 on sekä emo- että isovanhempi. Solmu 16 on vanhemman oikealla puolella ja emosolmu on myös vanhemman oikealla puolella, joten tämä on sakka-sak-tilanne. Tässä tapauksessa suoritamme ensin kierron vasemmalle solmulle 13 ja sitten 14 alla olevan kuvan mukaisesti:
Solmu 16 ei edelleenkään ole juurisolmu, vaan se on juurisolmun oikea lapsi, joten meidän on suoritettava kierto vasemmalle solmulle 12 tehdäksemme solmusta 16 juurisolmuksi.
Kun solmusta 16 tulee juurisolmu, poistamme solmun 16 ja saamme kaksi erilaista puuta, eli vasemman alipuun ja oikean alipuun alla olevan kuvan mukaisesti:
Kuten tiedämme, vasemman alipuun arvot ovat aina pienempiä kuin oikean alipuun arvot. Vasemman alipuun juuri on 12 ja oikean alipuun juuri on 17. Ensimmäinen askel on löytää maksimielementti vasemmasta alipuusta. Vasemmassa alipuussa suurin elementti on 15, ja sitten meidän on suoritettava toistotoiminto 15:lle.
Kuten voimme havaita yllä olevasta puusta, että elementillä 15 on sekä vanhempi että isovanhempi. Solmu on emosolmunsa oikealla puolella ja emosolmu on myös vanhemman oikealla puolella, joten meidän on suoritettava kaksi kiertoa vasemmalle tehdäksemme solmusta 15 juurisolmun alla olevan kuvan mukaisesti:
Kun puulle on tehty kaksi kiertoa, solmusta 15 tulee juurisolmu. Kuten näemme, luvun 15 oikea lapsi on NULL, joten liitämme solmun 17 15:n oikeaan osaan alla olevan kuvan mukaisesti, ja tämä operaatio tunnetaan nimellä liittyä seuraan operaatio.
Huomautus: Jos elementtiä ei ole poistettavassa esityspuussa, toisto suoritetaan. Splaying suoritettaisiin viimeksi käytetylle elementille ennen NULL-arvon saavuttamista.
Poistotoiminnon algoritmi
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
Yllä olevassa algoritmissa tarkistamme ensin, onko juuri nolla vai ei; jos juuri on NULL tarkoittaa, että puu on tyhjä. Jos puu ei ole tyhjä, suoritamme toistotoiminnon poistettavalle elementille. Kun toisto on valmis, vertaamme juuritietoja poistettavaan elementtiin; jos molemmat eivät ole samanarvoisia, se tarkoittaa, että elementtiä ei ole puussa. Jos ne ovat yhtä suuret, seuraavat tapaukset voivat tapahtua:
Tapaus 1 : Juuren vasen on NULL, juuren oikeasta tulee juurisolmu.
Tapaus 2 : Jos sekä vasen että oikea ovat olemassa, leikataan maksimielementti vasemmassa alipuussa. Kun toisto on valmis, maksimielementistä tulee vasemman alipuun juuri. Oikeasta alipuusta tulisi vasemman alipuun juuren oikea lapsi.