Splay-puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 8. syyskuuta 2016 tarkistetusta versiosta . tarkastukset vaativat 19 muokkausta .
laajeneva puu
Tyyppi Puu
Keksintövuosi 1985
Tekijä Daniel Slitor ja Robert Andre Tarjan
Monimutkaisuus O - symboleissa
Keskiverto Pahimmillaan
Muistin kulutus Päällä) Päällä)
Hae O(log n) O(log n)
Lisää O(log n) O(log n)
Poistaminen O(log n) O(log n)

Splay -  puu tai vinopuu on binäärihakupuu , joka ylläpitää tasapainoominaisuutta. Tämä puu kuuluu "itsesäätyvien puiden" luokkaan, jotka ylläpitävät tarvittavaa tasapainoa puun haarautumisessa varmistaakseen, että haut, lisäykset ja poistot voidaan suorittaa logaritmisessa ajassa tallennettujen elementtien lukumäärästä. Tämä tehdään ilman lisäkenttien käyttöä puun solmuissa (kuten esimerkiksi punamustissa tai AVL-puissa)., jossa kärjet tallentavat vastaavasti kärjen värin ja alipuun syvyyden). Sen sijaan leikkaustoiminto, johon kierrokset ovat osa, suoritetaan joka kerta, kun puuta käsitellään.

Kirjanpitokustannus yhtä puuta kohden on.

Laajenevan puun keksivät Robert Tarjan ja Daniel Slator vuonna 1983.

Toiminnot

Splay (laajennus)

Puun perustoiminto. Se koostuu kärkipisteen siirtämisestä juureen suorittamalla kolme operaatiota peräkkäin: Zig, Zig-Zig ja Zig-Zag. Merkitään se kärki, jonka juureen halutaan siirtää, muodossa x , sen emopiste - p ja emopiste p (jos sellainen on) - g .

Zig: suoritetaan, kun p on juuri. Puuta kierretään x :n ja p :n välistä reunaa pitkin . On olemassa vain reunatapauksena ja suoritetaan vain kerran lopussa, kun x :n alkusyvyys oli pariton.

Zig-Zig: Suoritetaan , kun sekä x että p ovat vasenta (tai oikeaa) poikia. Puuta kierretään g :n ja p :n välistä reunaa pitkin ja sitten p :n ja x :n välistä reunaa pitkin .

Zig-Zag: Toimii , kun x on oikea lapsi ja p  on vasen lapsi (tai päinvastoin). Puuta kierretään p :n ja x :n välistä reunaa pitkin ja sitten x :n ja g :n välistä reunaa pitkin .

Hae (hae elementti)

Haku suoritetaan kuten tavallisessa binäärihakupuussa. Kun elementti löytyy, käynnistämme sille Splayn.

Lisää (elementin lisääminen)

Suorita Split() lisättävälle elementille (katso Split(), muistutus: se käyttää olemassa olevan puun lähintä suurempaa tai yhtä suurta elementtiä) ja ripusta tuloksena olevat puut lisättävän elementin viereen.

Poista (elementin poistaminen)

Löydämme puusta elementin, teemme sille Splayn, teemme sen lapsista nykyisen yhdistämispuun.

Yhdistä (yhdistä kaksi puuta)

Yhdistääksemme puut T1 ja T2, joissa kaikki T1:n avaimet ovat pienempiä kuin T2:n avaimet, teemme Splayn T1:n maksimielementille, jolloin T1:n juurella ei ole oikeaa lapsia. Sen jälkeen teemme T2:sta T1:n oikean lapsen.

Split (puun jakaminen kahteen osaan)

Jos haluat jakaa puun x:llä, etsi pienin elementti, joka on suurempi tai yhtä suuri kuin x, ja tee sille jako. Sen jälkeen irrotetaan vasemman lapsen juuresta ja palautetaan 2 syntynyttä puuta.

Toteutus

Laajentuvan puun eräs toteutus olisi toteutus, joka käyttää 3 osoitinta kussakin kärjessä: osoitin oikealle ja vasemmalle alapuolelle ja myös vanhemmalle. Tämä välttää rekursiivisen toteutuksen, mikä puolestaan ​​säästää muistia. Haittapuolena tässä tapauksessa on suurempi määrä osoittimien päivitystehtäviä, mikä voi vaikuttaa lopulliseen suorituskykyyn.

Alla on toteutettu laajeneva puu, jossa käytetään 3 osoitinta solmua kohti. Myös tässä toteutuksessa Splay-toimintoa käytetään kaikissa puulle suoritettavissa perustoiminnoissa - lisättäessä, poistettaessa ja haettaessa puun paremman tasapainon saavuttamiseksi.

#ifndef SPLAYTREE_H #define SPLAYTREE_H malli < tyypinnimi T > luokka SplayTree { yksityinen : struct SplayNode { Solmu * vasenLapsi ; Solmu * oikeaLapsi Solmu * vanhempi ; T data ; Solmu ( jatkuva T & avain = T ()) : vasenLapsi ( nullptr ), oikeaLapsi ( nullptr ), vanhempi ( nullptr ), avain ( avain ) {} ~ Solmu () { poista leftChild ; poista oikeusLapsi ; } } * juuri ; yksityinen : SplayNode * _Seuraaja ( SplayNode * localRoot ) const { SplayNode * seuraaja = localRoot ; if ( seuraaja -> rightChild != nullptr ) { seuraaja = _Minimi ( seuraaja -> oikeaLapsi ); } muu { while ( seuraaja != juuri || seuraaja != seuraaja -> vanhempi -> vasenLapsi ) { seuraaja = seuraaja -> vanhempi ; } } palauta seuraaja ; } SplayNode * _Prececessor ( SplayNode * localRoot ) const { SplayNode * edeltäjä = localRoot ; if ( edeltäjä -> leftChild != nullptr ) { edeltäjä = _Maksimi ( edeltäjä -> vasenLapsi ); } muu { while ( edeltäjä != juuri || edeltäjä != edeltäjä -> vanhempi -> oikeaLapsi ) { edeltäjä = edeltäjä -> vanhempi ; } } palauta edeltäjä ; } SplayNode * _Minimi ( SplayNode * localRoot ) const { SplayNode * minimi = localRoot ; while ( minimi -> leftChild != nullptr ) minimi = minimi -> leftChild ; palautus minimi ; } SplayNode * _Maximum ( SplayNode * localRoot ) const { SplayNode * maksimi = localRoot ; while ( maksimi -> oikeaLapsi != nullptr ) maksimi = maksimi -> oikeaLapsi ; tuotto maksimi ; } SplayNode * _Search ( const T & key ) { SplayNode * searchedElement = root ; while ( searchedElement != nullptr ) { if ( searchedElement -> data < key ) searchedElement = searchedElement -> rightChild ; else if ( avain < searchedElement -> data ) searchedElement = searchedElement -> leftChild ; else if ( searchedElement -> data == avain ) { _Splay ( searchedElement ); palauta haettuElement ; } } return nullptr ; } void _LeftRotate ( SplayNode * localRoot ) { SplayNode * rightChild = localRoot -> rightChild ; localRoot -> rightLapsi = oikeaLapsi -> vasenLapsi ; if ( oikeaLapsi -> vasenLapsi != nullptr ) oikeaLapsi -> vasenLapsi -> vanhempi = localRoot ; _Transplant ( localRoot , rightChild ); oikeaLapsi -> vasenLapsi = localRoot ; oikeaLapsi -> vasenLapsi -> vanhempi = oikeaLapsi ; } void _RightRotate ( SplayNode * localRoot ) { SplayNode * leftChild = localRoot -> leftChild ; localRoot -> vasenLapsi = vasenLapsi -> oikeaLapsi ; if ( vasenLapsi -> oikeaLapsi != nullptr ) leftLapsi -> oikeaLapsi -> vanhempi = localRoot ; _Transplant ( paikallinenRoot , leftChild ); vasenLapsi -> oikeaLapsi = localRoot ; vasenLapsi -> oikeaLapsi -> vanhempi = vasenLapsi ; } void _Transplant ( SplayNode * localParent , SplayNode * localChild ) { if ( paikallinenParent -> vanhempi == nullptr ) root = localChild ; else if ( localParent == localParent -> vanhempi -> leftChild ) localParent -> vanhempi -> leftChild = paikallinenLapsi ; else if ( localParent == localParent -> parent -> rightChild ) localParent -> parent -> rightChild = localChild ; if ( localChild != nullptr ) localChild -> vanhempi = localParent -> vanhempi ; } void _Splay ( SplayNode * pivotElement ) { while ( pivotElement != root ) { if ( pivotElement -> vanhempi == juuri ) { if ( pivotElement == pivotElement -> vanhempi -> leftChild ) { _RightRotate ( pivotElement -> vanhempi ); } else if ( pivotElement == pivotElement -> vanhempi -> rightChild ) { _LeftRotate ( pivotElement -> vanhempi ); } } muu { // Zig-Zig-askel. if ( pivotElement == pivotElement -> vanhempi -> leftChild && pivotElement -> vanhempi == pivotElement -> vanhempi -> vanhempi -> leftChild ) { _RightRotate ( pivotElement -> vanhempi -> vanhempi ); _RightRotate ( pivotElement -> vanhempi ); } else if ( pivotElement == pivotElement -> vanhempi -> rightChild && pivotElement -> vanhempi == pivotElement -> vanhempi -> vanhempi -> rightChild ) { _LeftRotate ( pivotElement -> vanhempi -> vanhempi ); _LeftRotate ( pivotElement -> vanhempi ); } // Siksak-askel. else if ( pivotElement == pivotElement -> vanhempi -> rightChild && pivotElement -> vanhempi == pivotElement -> vanhempi -> vanhempi -> leftChild ) { _LeftRotate ( pivotElement -> vanhempi ); _RightRotate ( pivotElement -> vanhempi ); } else if ( pivotElement == pivotElement -> vanhempi -> leftChild && pivotElement -> vanhempi == pivotElement -> vanhempi -> vanhempi -> rightChild ) { _RightRotate ( pivotElement -> vanhempi ); _LeftRotate ( pivotElement -> vanhempi ); } } } } julkinen : SplayTree () { juuri = nullptr ; } virtual ~ SplayTree () { poista juuri ; } void Insert ( jatkuva T & avain ) { SplayNode * preInsertPlace = nullptr ; SplayNode * insertPlace = root ; while ( insertPlace != nullptr ) { preInsertPlace = insertPlace ; if ( insertPlace -> data ( ) < key ) insertPlace = insertPlace -> rightChild ; else if ( avain <= insertPlace -> data ) insertPlace = insertPlace -> leftChild ; } SplayNode * insertElement = uusi SplayNode ( avain ); insertElement -> vanhempi = preInsertPlace ; if ( preInsertPlace == nullptr ) root = insertElement ; else if ( preInsertPlace -> data < insertElement -> data ) preInsertPlace -> rightChild = insertElement ; else if ( insertElement -> data < preInsertPlace -> data ) preInsertPlace -> leftChild = insertElement ; _Splay ( insertElement ); } void Poista ( jatkuva T & avain ) { SplayNode * removeElement = _Haku ( avain ); if ( removeElement != nullptr ) { if ( poistaElement -> rightChild == nullptr ) _Transplant ( poistaElement , removeElement -> leftChild ); else if ( poistaElement -> leftChild == nullptr ) _Transplant ( poistaElement , removeElement -> rightChild ); else { SplayNode * newLocalRoot = _Minimi ( poistoElement -> rightChild ); if ( newLocalRoot -> parent != removeElement ) { _Transplant ( newLocalRoot , newLocalRoot -> rightChild ); newLocalRoot -> rightChild = poistaElement -> rightChild ; newLocalRoot -> rightChild -> parent = newLocalRoot ; } _Transplant ( poistoelementti , uusiLocalRoot ); newLocalRoot -> leftChild = poistaElement -> leftChild ; newLocalRoot -> leftChild -> parent = newLocalRoot ; _Splay ( newLocalRoot ); } poista PoistaElement ; } } bool Haku ( const T & avain ) { return _Search ( avain ) != nullptr ; } bool isEmpty () const { return root == nullptr ; } T seuraaja ( jatkuva T & avain ) { if ( _Seuraaja ( _Haku ( avain )) != nullptr ) { return _Seuraaja ( _Haku ( avain )) -> getValue (); } muu { paluu -1 ; } } T edeltäjä ( jatkuva T & avain ) { if ( _Edeltäjä ( _Haku ( avain )) != nullptr ) { return _Prececessor ( _Search ( avain )) -> getValue (); } muu { paluu -1 ; } } }; #endif //SPLAYTREE_H

Huomautus

Laajentuva puu tarjoaa itsemuovautuvan rakenteen – rakenteelle, jolle on tunnusomaista taipumus pitää usein käytetyt solmut lähellä puun yläosaa, kun taas harvoin käytettävät solmut siirtyvät lähemmäksi lehtiä. Siten pääsyaika usein vierailtuihin solmuihin on lyhyempi ja pääsyaika harvoin vierailtuihin solmuihin on keskimääräistä pidempi.

Laajentuvassa puussa ei ole mitään eksplisiittisiä tasapainotustoimintoja, mutta solmujen vinouttaminen juuria kohti auttaa pitämään puun tasapainossa.

Katso myös

  • Tasapainotetut (itsetasapainottavat) puut:
  • Luettelo tietorakenteista (puista)

Kirjallisuus

  • Thomas H. Kormen et al. Algoritmit: rakentaminen ja analyysi. - 2. painos - M . : Williams Publishing House , 2007. - S. 1296. - ISBN 5-8459-0857-4 .
  • Daniel Sleater, Robert Tarjan. Tietorakenne dynaamisille puille. - Journal of Computer and System Sciences, 1983. - S. 262-391.