Puna-musta puu

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 2. marraskuuta 2019 tarkistetusta versiosta . tarkastukset vaativat 32 muokkausta .

Puna-musta puu

Tyyppi

hakupuu

Keksintövuosi

1972

Tekijä

Rudolf Baier

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)

Mediatiedostot Wikimedia Commonsissa

Punamusta puu ( eng. red-black tree , RB tree ) on yksi itsetasapainottuvien binäärihakupuiden tyypeistä, joka takaa puun korkeuden logaritmisen kasvun solmujen lukumäärästä ja mahdollistaa nopean perushakupuun suorittamisen toiminnot: solmun lisääminen, poistaminen ja etsiminen. Tasapaino saavutetaan ottamalla käyttöön puusolmun lisäattribuutti - "värit". Tämä attribuutti voi ottaa yhden kahdesta mahdollisesta arvosta - "musta" tai "punainen".

Saksalaista keksijää Rudolf Bayeria pidetään punamustan puun keksijänä . Tietorakenteelle annettiin nimi "punamusta puu" L. Gimbasin ja R. Sedgwickin artikkelissa (1978). Gimbasin mukaan he käyttivät kaksivärisiä kyniä [1] . Sedgwickin mukaan punainen näytti parhaalta lasertulostimessa [1] [2] .

Punamustaa puuta käytetään vertailukelpoisten tietojen, kuten tekstin tai numeroiden, järjestämiseen. Punamustien puiden lehtisolmut eivät sisällä dataa, joten ne eivät vaadi muistin varaamista - riittää, että kirjoitat nollaosoittimen osoittimeksi esi-isolmussa olevaan lapseen. Joissakin toteutuksissa voidaan kuitenkin käyttää eksplisiittisiä lehtisolmuja algoritmin yksinkertaistamiseksi.

Järjestyksen periaate

Punamusta puu on binäärihakupuu , jossa jokaisella solmulla on väriattribuutti . Jossa:

Solmu voi olla joko punainen tai musta, ja siinä on kaksi lasta;
Juuri on yleensä musta. Tällä säännöllä on vain vähän vaikutusta mallin suorituskykyyn, koska juuren väri voidaan aina muuttaa punaisesta mustaksi;
Kaikki lehdet, jotka eivät sisällä tietoja, ovat mustia.
Kunkin punaisen solmun molemmat lapset ovat mustia.
Mikä tahansa yksinkertainen polku esi-isolmusta lapsilehtisolmuun sisältää saman määrän mustia solmuja.

Näistä rajoituksista johtuen polku juuresta kaukaisimpaan lehteen on enintään kaksi kertaa pidempi kuin lähimpään ja puu on suunnilleen tasapainossa. Lisäys-, poisto- ja hakutoiminnot vaativat pahimmassa tapauksessa puun pituuteen verrannollisen ajan, mikä mahdollistaa punamustat puut olla tehokkaampia pahimmassa tapauksessa kuin perinteiset binäärihakupuut.

Tämän toiminnan ymmärtämiseksi riittää, kun tarkastellaan ominaisuuksien 4 ja 5 vaikutusta yhdessä. Olkoon mustien solmujen määrä juuresta lehteen B punamustalle puulle T. Tällöin lyhin mahdollinen polku mihin tahansa lehtiin sisältää B solmua, ja ne ovat kaikki mustia. Pidempi mahdollinen polku voidaan rakentaa sisällyttämällä punaiset solmut. Lauseesta 4 johtuen puussa ei kuitenkaan voi olla kahta punaista solmua peräkkäin ja lausekkeiden mukaisesti 2 ja 3, polku alkaa ja päättyy mustaan solmuun. Siksi pisin mahdollinen polku koostuu 2B-1-solmuista, vuorotellen punaisista ja mustista.

Jos sallit muun kuin lehtisolmun olla alle kaksi lasta ja lehtisolmun sisältää dataa, puu säilyttää perusominaisuudet, mutta sen kanssa työskentelyn algoritmeista tulee monimutkaisempia. Siksi artikkeli käsittelee vain "tyhmiä lehtisolmuja", jotka eivät sisällä tietoja ja jotka yksinkertaisesti osoittavat, mihin puu päättyy. Nämä solmut voidaan jättää pois joissakin kuvissa. Kohdasta 5 seuraa myös, että punaisen solmun jälkeläiset voivat olla joko kaksi mustaa välisolmua tai kaksi mustaa lehteä, ja ottaen huomioon kohdat 3 ja 4 - että jos yksi mustan solmun jälkeläisistä on lehtisolmu , toisen tulee olla joko myös arkki tai yllä kuvattu malli, jossa on yksi punainen ja kaksi arkkia.

Myös kirjallisuudessa on tulkinta, jossa ei itse solmut, vaan niihin johtavat reunat on maalattu punaisilla / mustilla väreillä - mutta tällä ei ole suurta merkitystä sen toimintaperiaatteen ymmärtämiselle.

B-puun analogia parametrin 4 kanssa

Punamusta puu on rakenteeltaan samanlainen kuin B-puu parametrilla 4, jossa jokainen solmu voi sisältää 1 - 3 arvoa ja vastaavasti 2 - 4 osoitinta lapsille. Tällaisessa B-puussa kukin solmu sisältää vain yhden arvon, joka vastaa puna-mustan puun mustan solmun arvoa, valinnaisilla arvoilla ennen ja/tai sen jälkeen samassa solmussa, jotka molemmat vastaavat punamustan puun vastaaviin punaisiin solmuihin.

Yksi tapa nähdä tämä vastaavuus on "nostaa" punaisia solmuja punamustan puun graafisessa esityksessä niin, että ne ovat vaakasuorassa samassa tasossa mustien solmujen esivanhempiensa kanssa muodostaen sivun. B-puussa tai muokatussa graafisessa esityksessä punamusta puusta kaikilla lehtien solmuilla on sama syvyys.

Tämän tyyppinen B-puu on yleisempi kuin punamusta puu, vaikka, kuten näet, yhdestä tällaisesta B-puusta voidaan saada useita punamusta puita parametrilla 2. Jos B-puusivu sisältää vain yhden arvon, solmu on musta ja siinä on kaksi alapistettä. Jos sivulla on kolme arvoa, keskisolmu on musta ja jokainen sen naapuri on punainen. Jos sivulla on kuitenkin kaksi arvoa, mikä tahansa solmu voi muuttua mustaksi punamustapuussa (jolloin toinen on punainen).

Työskentely punamustien puiden kanssa

Punamustat puut ovat käytännössä yksi yleisimmin käytetyistä itsetasapainottuvista hakupuista. Erityisesti useimpien C++ STL - kirjaston [3] , Java TreeMap -luokan [4] sekä monien muiden assosiatiivisten taulukkototeutusten useissa toteutuksissa eri kirjastoissa olevat set- ja karttasäilöt perustuvat punamustiin puihin.

Punamustat puut ovat suositumpia kuin täydellisesti tasapainotetut puut. jälkimmäisessä puusta poistamiseen ja tarvittavan tasapainon ylläpitämiseen voidaan käyttää liikaa resursseja. Lisäyksen tai poistamisen jälkeen tarvitaan uudelleenvärjäystoiminto, joka vaatii (O(log n ) tai O(1)) värinmuutoksia (mikä on käytännössä melko nopeaa) ja enintään kolme puun kiertoa (enintään kaksi lisäystä varten ). Vaikka insertio ja deleetio ovat monimutkaisia, ne ovat silti O(log n ) työvoimavaltaisia.

Lisää

Punamustapuuhun lisätään uusi solmu yhden lehden tilalle, värjätty punaiseksi, ja siihen on kiinnitetty kaksi lehteä (koska lehdet ovat abstraktio, joka ei sisällä dataa, niiden lisääminen ei vaadi lisätoimintoa) . Mitä seuraavaksi tapahtuu, riippuu lähellä olevien solmujen väristä. Huomaa, että:

Ominaisuus 3 (kaikki lehdet ovat mustia) on aina totta.
Ominaisuutta 4 (Mikä tahansa punaisen solmun molemmat alat ovat mustia) voidaan rikkoa vain lisäämällä punainen solmu, värjäämällä musta solmu punaiseksi tai kiertämällä sitä.
Ominaisuutta 5 (Kaikki polut mistä tahansa solmusta lehtisolmuihin sisältävät saman määrän mustia solmuja) voidaan rikkoa vain lisäämällä musta solmu, värjäämällä punainen solmu mustaksi (tai päinvastoin) tai kiertämällä.

Huomautus : Kirjain N tarkoittaa nykyistä solmua (väritetty punaisella). Ensinnäkin uusi solmu lisätään, mutta tätä menettelyä voidaan soveltaa rekursiivisesti muihin solmuihin (katso tapaus 3). P merkitsee N:n esi-isä , G merkitsee N : n isoisää ja U setä (solmu, jolla on yhteinen vanhempi solmun P kanssa ). Huomaa, että joissain tapauksissa solmujen roolit voivat muuttua, mutta joka tapauksessa jokainen nimitys edustaa samaa solmua kuin alussa. Mikä tahansa kuvassa esitetty väri on tässä tapauksessa oletettu tai saatu muista näkökohdista.

Jokainen tapaus on peitetty C - koodiesimerkeillä . Solmurakenteen määritelmä voi näyttää tältä:

enum solmun_värit { PUNAINEN , MUSTA }; struct solmu { struct solmu * vanhempi , * vasen , * oikea ; enum solmu_värit väri ; intkey ; _ };

Nykyisen solmun setä ja isoisä löytyvät funktioilla:

rakennesolmu * _ isovanhempi ( struct solmu * n ) { if (( n != NULL ) && ( n -> vanhempi != NULL )) return n -> vanhempi -> vanhempi ; muu return NULL ; } rakennesolmu * _ setä ( struct solmu * n ) { struct solmu * g = isovanhempi ( n ); jos ( g == NULL ) return NULL ; // Ei isovanhempaa tarkoittaa ei setä jos ( n -> vanhempi == g -> vasen ) paluu g -> oikealle ; muu paluu g -> vasen ; }

Puun kierto vasemmalle ja oikealle voidaan tehdä seuraavasti:

mitätön rotate_left ( struct solmu * n ) { struct solmu * pivot = n -> oikea ; pivot -> vanhempi = n -> vanhempi ; /* mahdollisesti puun juuren kääntäminen */ if ( n -> vanhempi != NULL ) { if ( n -> vanhempi -> vasen == n ) n -> vanhempi -> vasen = pivot ; muu n -> vanhempi -> oikea = pivot ; } n -> oikea = pivot -> vasen ; if ( pivot -> left != NULL ) pivot -> vasen -> vanhempi = n ; n -> vanhempi = pivot ; pivot -> vasen = n ; } mitätön rotate_right ( struct solmu * n ) { struct solmu * pivot = n -> vasen ; pivot -> vanhempi = n -> vanhempi ; /* mahdollisesti puun juuren kääntäminen */ if ( n -> vanhempi != NULL ) { if ( n -> vanhempi -> vasen == n ) n -> vanhempi -> vasen = pivot ; muu n -> vanhempi -> oikea = pivot ; } n -> vasen = pivot -> oikea ; if ( pivot -> right != NULL ) pivot -> oikealle -> vanhempi = n ; n -> vanhempi = pivot ; pivot -> oikea = n ; }

Tapaus 1: Nykyinen solmu N on puun juuressa. Tässä tapauksessa se maalataan uudelleen mustaksi, jotta ominaisuus 2 (juuri on musta) pysyy oikeana. Koska tämä toiminto lisää yhden mustan solmun kuhunkin polkuun, ominaisuutta 5 (kaikki polut mistä tahansa solmusta lehtisolmuihin sisältävät saman määrän mustia solmuja) ei rikota.

mitätön insert_case1 ( struct solmu * n ) { if ( n -> vanhempi == NULL ) n -> väri = MUSTA ; muu insert_case2 ( n ); }

Tapaus 2: Nykyisen solmun emo P on musta, eli ominaisuutta 4 (jokaisen punaisen solmun molemmat lapset ovat mustia) ei rikota. Tässä tapauksessa puu pysyy oikeana. Ominaisuutta 5 (kaikki polut mistä tahansa tietystä solmusta lehtisolmuihin sisältävät saman määrän mustia solmuja) ei ole rikottu, koska nykyisellä solmulla N on kaksi mustaa lehteä, mutta koska N on punainen, polku jokaiseen näistä lapsista sisältää saman mustien solmujen määrä, joka on polku mustaan lehteen, joka on korvattu nykyisellä solmulla, joten ominaisuus pysyy tosi.

mitätön insert_case2 ( struct solmu * n ) { if ( n -> vanhempi -> väri == MUSTA ) paluu ; /* Puu on edelleen voimassa */ muu insert_case3 ( n ); } Huomautus: Seuraavissa tapauksissa oletetaan, että N :llä on isovanhempi G , koska sen emo - P on punainen, ja jos se olisi juuri, se olisi musta. Siten N :llä on myös setä U , vaikka se voi olla lehtisolmu tapauksissa 4 ja 5.

Tapaus 3: Jos sekä vanhempi P että setä U ovat punaisia, ne voidaan molemmat värjätä mustiksi ja isovanhempi G muuttuu punaisiksi (ominaisuuden 5 säilyttämiseksi (kaikki polut mistä tahansa solmusta lehtisolmuihin sisältävät saman määrän mustia solmuja)) . Nyt nykyisellä punaisella solmulla N on musta emo. Koska minkä tahansa polun vanhemman tai sedän kautta täytyy kulkea isovanhemman kautta, mustien solmujen määrä näissä poluissa ei muutu. G :n isovanhempi voi kuitenkin nyt rikkoa ominaisuuksia 2 (juuri on musta) tai 4 (kunkin punaisen solmun molemmat lapset ovat mustia) (ominaisuutta 4 voidaan rikkoa, koska G :n vanhempi voi olla punainen). Tämän korjaamiseksi koko toimenpide suoritetaan rekursiivisesti G :lle tapauksesta 1.

mitätön insert_case3 ( struct solmu * n ) { struct solmu * u = setä ( n ), * g ; if (( u != NULL ) && ( u -> väri == PUNAINEN )) { // && (n->parent->color == PUNAINEN) Toinen ehto testataan insert_case2:ssa, eli vanhempi on jo punainen. n -> vanhempi -> väri = MUSTA ; u -> väri = MUSTA ; g = isovanhempi ( n ); g -> väri = PUNAINEN ; insert_case1 ( g ); } muu { insert_case4 ( n ); } } Huomautus: Muissa tapauksissa vanhemman P oletetaan olevan esi-isänsä vasen lapsi. Jos näin ei ole, sinun on vaihdettava vasemmalle ja oikealle . Koodiesimerkit huolehtivat siitä.

Tapaus 4: P :n vanhempi on punainen, mutta U :n setä on musta. Lisäksi nykyinen solmu N on P : n oikea lapsi , ja P puolestaan on esi-isänsä G vasen lapsi . Tällöin voidaan suorittaa puun kierto, joka muuttaa nykyisen solmun N ja sen esi -isän P rooleja . Käytä sitten päivitetyn rakenteen entiselle pääsolmulle P tapausta 5, koska ominaisuus 4 (mikä tahansa punaisen solmun molemmat alat ovat mustia) on edelleen rikottu. Kierto saa joitain polkuja (kaavion alipuussa, joka on merkitty "1") kulkemaan solmun N läpi , mitä ei aiemmin ollut. Tämä aiheuttaa myös sen, että jotkin polut (alipuussa, jonka nimi on "3") eivät kulje P -solmun läpi . Molemmat solmut ovat kuitenkin punaisia, joten kierto ei riko ominaisuutta 5 (kaikki polut tietystä solmusta lehtisolmuihin sisältävät saman määrän mustia solmuja). Ominaisuutta 4 rikotaan kuitenkin edelleen, mutta nyt ongelma on rajoittunut tapaukseen 5.

mitätön insert_case4 ( struct solmu * n ) { struct solmu * g = isovanhempi ( n ); if (( n == n -> vanhempi -> oikea ) && ( n -> vanhempi == g -> vasen )) { rotate_left ( n -> vanhempi ); n = n -> vasen ; /* * rotate_left voidaan tehdä seuraavasti, koska olemassa on jo *g = isovanhempi(n) * * struct solmu *saved_p=g->left, *saved_left_n=n->left; * g->vasen=n; * n->vasen=tallennettu_p; * tallennettu_p->oikea=tallennettu_vasen_n; * */ } else if (( n == n -> vanhempi -> vasen ) && ( n -> vanhempi == g -> oikea )) { rotate_right ( n -> vanhempi ); n = n -> oikea ; /* * rotate_right voidaan tehdä seuraavasti, koska on jo olemassa *g = isovanhempi(n) * * struct solmu *tallennettu_p=g->oikea, *tallennettu_oikea_n=n->oikea; *g->oikea=n; * n->oikea=tallennettu_p; * tallennettu_p->vasen=tallennettu_oikea_n; * */ } insert_case5 ( n ); }

Tapaus 5: Vanhempi P on punainen, mutta setä U on musta, nykyinen solmu N on P :n vasen lapsi ja P on G :n vasen lapsi . Tässä tapauksessa puuta pyöritetään G :llä . Tuloksena on puu, jossa entinen vanhempi P on nyt sekä nykyisen solmun N että entisen isovanhemman G vanhempi . Tiedetään, että G on musta, koska sen entinen lapsi P ei muuten voisi olla punainen (rikkomatta ominaisuutta 4). Sitten P :n ja G :n värit vaihtuvat ja tämän seurauksena puu täyttää ominaisuuden 4 (mikä tahansa punaisen solmun molemmat lapset ovat mustia). Ominaisuus 5 (Kaikki polut mistä tahansa solmusta lehtisolmuihin sisältävät saman määrän mustia solmuja) pysyy myös totta, koska kaikki polut, jotka kulkevat minkä tahansa näistä kolmesta solmusta, kulkivat aiemmin G :n kautta , joten nyt ne kaikki kulkevat P :n kautta . Kussakin tapauksessa näistä kolmesta solmusta vain yksi on musta.

mitätön insert_case5 ( struct solmu * n ) { struct solmu * g = isovanhempi ( n ); n -> vanhempi -> väri = MUSTA ; g -> väri = PUNAINEN ; if (( n == n -> vanhempi -> vasen ) && ( n -> vanhempi == g -> vasen )) { pyöritä_oikealle ( g ); } muu { kiertää_vasemmalle ( g ); } }

Poisto

Kun normaalista binäärihakupuusta poistetaan solmu, jossa on kaksi ei-lehteä lasta, etsitään joko sen vasemmanpuoleisesta alipuusta suurin elementti tai oikeasta alipuusta pienin elementti ja siirretään sen arvo poistettavaan solmuun. Poistamme sitten solmun, josta kopioimme arvon. Arvon kopioiminen solmusta toiseen ei riko punamustan puun ominaisuuksia, koska puun rakenne ja solmujen värit eivät muutu. On syytä huomata, että poistettavassa uudessa solmussa ei voi olla kahta ei-lehtiä olevaa lapsisolmua kerralla, muuten se ei ole suurin/pienin elementti. Siten käy ilmi, että tapaus poistaa solmu, jolla on kaksi ei-lehteä alisolmua, pelkistyy tapaukseksi, jossa poistetaan solmu, joka sisältää enintään yhden ei-lehtisen alisolmun. Siksi jatkokuvauksessa lähdetään olettamuksesta, että poistettavalla solmulla on enintään yksi ei-lehtinen lapsi.

Käytämme merkintää M poistettavalle solmulle; merkitsemme C :llä M : n jälkeläistä , jota kutsumme myös yksinkertaisesti "sen jälkeläiseksi". Jos M :llä on ei-lehtinen lapsi, ota se C :ksi . Muuten C :lle otamme minkä tahansa lehtien jälkeläisistä.

Jos M on punainen solmu, korvaa se lapsillamme C , jonka määritelmän mukaan on oltava musta. (Tämä voi tapahtua vain, kun M :llä on kaksi lehtiä, koska jos punaisella solmulla M on musta ei-lehtilapsi toisella puolella ja lehtilapsi toisella puolella, niin mustien solmujen määrä molemmilla puolilla on erilainen, jolloin puusta tulee virheellinen. punainen-musta puu ominaisuuden 5 rikkomisen vuoksi.) Kaikki poistettavan solmun läpi kulkevat polut sisältävät yksinkertaisesti yhden punaisen solmun vähemmän, poistettavan solmun ylä- ja alaosan on oltava mustia, joten Kiinteistö 3 ("Kaikki lehdet ovat mustia") ja ominaisuus 4 ("Punaisen solmun molemmat lapset ovat mustia") ovat edelleen voimassa.

Toinen yksinkertainen tapaus on, kun M on musta ja C on punainen. Pelkästään mustan solmun poistaminen rikkoisi ominaisuutta 4 ("Punaisen solmun molemmat lapset ovat mustia") ja ominaisuutta 5 ("Jokainen yksinkertainen polku tietystä solmusta mihin tahansa lehtisolmuun sisältää saman määrän mustia solmuja"), mutta jos me värjätä C mustaksi, molemmat ominaisuudet säilyvät.

Vaikea tapaus on, kun sekä M että C ovat mustia. (Tämä voi tapahtua vain, kun musta solmu, jossa on kaksi lehtilapsia, poistetaan, koska jos mustassa solmussa M on musta ei-lehtilapsi toisella puolella ja lehtilapsi toisella, niin mustien solmujen lukumäärä molemmilla puolilla on erilainen ja puusta tulee virheellinen punamusta puu, koska ominaisuus 5 on rikottu.) Aloitamme korvaamalla solmun M sen lapsilla C . Kutsumme tätä jälkeläistä (sen uudessa asemassa) N :ksi ja sen "veljeksi" (sen uuden esi-isän toiseksi jälkeläiseksi) - S. (Aiemmin S oli M :n "veli" .) Alla olevissa kuvissa käytämme myös merkintää P N :n uudelle esi- isälle ( M :n vanha esi-isä ), S L :n S :n vasemmalle lapselle , ja S R S :n oikealle lapselle ( S ei voi olla lehtisolmu , koska jos N oletuksenamme on musta, niin N:n sisältävä alipuu P on korkeudeltaan kaksi musta ja siksi P :n toisen alipuun, joka sisältää S :n, täytyy myös olla musta korkeudeltaan kaksi, mikä ei voi olla tilanne, kun S on lehti) .

Huomautus : Joissakin tapauksissa muutamme solmujen rooleja ja nimityksiä, mutta jokaisessa tapauksessa mikä tahansa nimitys tarkoittaa edelleen samaa solmua kuin tapauksen alussa. Kuvassa näkyvät värit ovat joko sattumanvaraisia tai saatu muista oletuksista. Valkoinen tarkoittaa tuntematonta väriä (joko punaista tai mustaa).

Etsimme "veljeä" käyttämällä tätä toimintoa:

rakennesolmu * _ sisarus ( rakennesolmu * n ) _ { if ( n == n -> vanhempi -> vasen ) return n -> vanhempi -> oikea ; muu paluu n -> vanhempi -> vasen ; } Huomautus : Jotta puu pysyisi oikein määriteltynä, jokaisen lehden on pysyttävä lehdenä kaikkien muutosten jälkeen (joten sillä ei ole lapsia). Jos poistettavalla solmulla on ei-lehtinen ali N , on helppo nähdä, että ominaisuus on voimassa. Toisaalta, jos N on lehti, niin, kuten kuvista tai koodista näkyy, myös ominaisuus pätee.

Voimme suorittaa yllä olevat vaiheet käyttämällä seuraavaa koodia, jossa funktio replace_nodekorvaa puun childsolmun . nMukavuussyistä tämän osan koodi olettaa, että tyhjät lehdet edustavat todellisia solmuobjekteja, eivät NULL:ia (lisäyskoodin tulisi toimia samalla esityksellä).

void korvaa_solmu ( solmu * n , solmu * lapsi ) { lapsi -> vanhempi = n -> vanhempi ; if ( n == n -> vanhempi -> vasen ) { n -> vanhempi -> vasen = lapsi ; } muu { n -> vanhempi -> oikeus = lapsi ; } } mitätön delete_one_child ( struct solmu * n ) { /* * Ehto: n:llä on enintään yksi nollasta poikkeava lapsi. */ struct solmu * lapsi = is_leaf ( n -> oikea ) ? n -> vasen : n -> oikea ; korvaa_solmu ( n , lapsi ); if ( n -> väri == MUSTA ) { jos ( lapsi -> väri == PUNAINEN ) lapsi -> väri = MUSTA ; muu delete_case1 ( lapsi ); } vapaa ( n ); } Huomautus : Jos N on nollalehti, emmekä halua esittää nollalehtiä todellisina objekteina, voimme muokata algoritmia kutsumalla ensin delete_case1() sen yläpuolella (solmu n, jonka poistimme yllä olevasta koodista) ja poistamalla sen jälkeen että. Voimme tehdä tämän, koska isä on musta ja siksi käyttäytyy kuin tyhjä lehti (ja sitä kutsutaan joskus "haamulehdeksi"). Voimme poistaa sen turvallisesti, koska se npysyy lehtinä kaikkien yllä olevien toimenpiteiden jälkeen.

Jos N ja sen nykyinen isä ovat mustia, isän poistaminen aiheuttaa N :n läpi kulkeville poluille yhden mustan solmun vähemmän kuin poluilla, jotka eivät kulje sen läpi. Koska tämä rikkoo ominaisuutta 5 (kaikki polut mistä tahansa solmusta sen lehtisolmuihin sisältävät saman määrän mustia solmuja), puu on tasapainotettava uudelleen. On useita harkitsevia tapauksia:

Tapaus 1: N on uusi juuri. Tässä tapauksessa kaikki on tehty. Olemme poistaneet jokaiselta polulta yhden mustan solmun ja uusi juuri on musta solmu, joten ominaisuudet säilyvät.

mitätön delete_case1 ( struct solmu * n ) { if ( n -> vanhempi != NULL ) poista_tapaus2 ( n ); } Huomaa : Tapauksissa 2, 5 ja 6 oletetaan, että N on esi-isänsä P vasen lapsi . Jos kyseessä on oikea lapsi, vasen ja oikea on vaihdettava kaikissa kolmessa tapauksessa. Jälleen koodiesimerkit ottavat tämän huomioon.

Tapaus 2: S on punainen. Tässä tapauksessa vaihdamme P :n ja S :n värit ja teemme sitten kierron vasemmalle P :n ympäri , jolloin S on N :n isovanhempi . Huomaa, että P :n on oltava musta, jos siinä on punainen lapsi. Tuloksena saatavassa alipuussa on vielä yksi musta solmu vähemmän, joten emme ole vielä valmiit siihen. Nyt N :llä on musta sisarus ja punainen isä, joten voimme siirtyä vaiheisiin 4, 5 tai 6. (Hänen uusi sisaruksensa on musta, koska hän oli punaisen S :n jälkeläinen .)

Seuraavassa S tarkoittaa uutta veljeä N.

void delete_case2 ( struct solmu * n ) { struct solmu * s = sisarus ( n ); if ( s -> väri == PUNAINEN ) { n -> vanhempi -> väri = PUNAINEN ; s -> väri = MUSTA ; if ( n == n -> vanhempi -> vasen ) rotate_left ( n -> vanhempi ); muu rotate_right ( n -> vanhempi ); } delete_case3 ( n ); }

Tapaus 3: P :n , S :n ja S:n lapset ovat mustia. Tässä tapauksessa värjäämme vain S - punaisen. Tämän seurauksena kaikilla poluilla S :n läpi mutta ei N :n kautta on yksi musta solmu vähemmän. Koska N :n isän poistaminen aiheuttaa sen, että kaikki N :n kautta kulkevat polut sisältävät yhden mustan solmun vähemmän, tällaiset toimet tasoittavat tasapainoa. Kuitenkin kaikki P :n kautta kulkevat polut sisältävät nyt yhden mustan solmun vähemmän kuin polut, jotka eivät kulje P :n läpi , joten ominaisuus 5 (kaikki polut mistä tahansa kärjestä sen lehtisolmuihin sisältävät saman määrän mustia solmuja) on edelleen rikki. Korjataksemme tämän soveltamalla tasapainotusmenettelyä P :hen tapauksesta 1 alkaen.

void delete_case3 ( struct solmu * n ) { struct solmu * s = sisarus ( n ); jos ( ( n -> vanhempi -> väri == MUSTA ) && ( s -> väri == MUSTA ) && ( s -> vasen -> väri == MUSTA ) && ( s -> oikea -> väri == MUSTA ) ) { s -> väri = PUNAINEN ; delete_case1 ( n -> vanhempi ); } muuta poista_tapaus4 ( n ); }

Tapaus 4: S ja hänen lapsensa ovat mustia, mutta P on punainen. Tässä tapauksessa muutamme vain S :n ja P :n värejä . Tämä ei vaikuta mustien solmujen määrään reiteillä S :n läpi , mutta lisää yhden mustien solmujen määrään reiteillä N :n kautta , mikä palauttaa poistetun mustan solmun vaikutuksen.

void delete_case4 ( struct solmu * n ) { struct solmu * s = sisarus ( n ); jos ( ( n -> vanhempi -> väri == PUNAINEN ) && ( s -> väri == MUSTA ) && ( s -> vasen -> väri == MUSTA ) && ( s -> oikea -> väri == MUSTA ) ) { s -> väri = PUNAINEN ; n -> vanhempi -> väri = MUSTA ; } muuta poista_tapaus5 ( n ); }

Tapaus 5: S on musta, S :n vasen lapsi on punainen, S :n oikea lapsi on musta ja N on isänsä vasen lapsi. Tässä tapauksessa käännämme puuta oikealle S :n ympäri . Siten S : n vasemmasta lapsesta tulee sen isä ja N :n uusi veli . Sen jälkeen vaihdamme S :n ja hänen uuden isänsä värit. Kaikissa poluissa on edelleen sama määrä mustia solmuja, mutta nyt N :llä on musta sisarus, jolla on punainen oikea lapsi, ja siirrytään tapaukseen 6. N tai sen isä eivät vaikuta tähän transformaatioon. (Tapauksessa 6 merkitsemme S :llä N :n uutta veljeä .)

void delete_case5 ( struct solmu * n ) { struct solmu * s = sisarus ( n ); if ( s -> color == BLACK ) { /* tämä if-lause on triviaali tapauksesta 2 johtuen (vaikka tapaus 2 muutti sisaruksen sisaruksen lapseksi, sisaruksen lapsi ei voi olla punainen, koska kukaan punainen vanhempi ei voi on punainen lapsi). */ /* seuraavat lauseet vain pakottavat punaisen olemaan vanhemman vasemmanpuoleisen puolen vasemmalla puolella tai oikealla oikealla, joten tapaus kuusi pyörii oikein. */ jos ( ( n == n -> vanhempi -> vasen ) && ( s -> oikea -> väri == MUSTA ) && ( s -> vasen -> väri == PUNAINEN ) ) { /* tämäkin viimeinen testi on triviaali tapausten 2-4 takia. */ s -> väri = PUNAINEN ; s -> vasen -> väri = MUSTA ; rotate_right ( s ); } muuten jos ( ( n == n -> vanhempi -> oikea ) && ( s -> vasen -> väri == MUSTA ) && ( s -> oikea -> väri == PUNAINEN ) ) { /* tämäkin viimeinen testi on triviaali tapausten 2-4 takia. */ s -> väri = PUNAINEN ; s -> oikea -> väri = MUSTA ; rotate_left ( s ); } } poista_tapaus6 ( n ); }

Tapaus 6: S on musta, S : n oikea lapsi on punainen ja N on isänsä P vasen lapsi . Tässä tapauksessa käännämme puuta vasemmalle P :n ympäri , minkä jälkeen S :stä tulee P : n ja sen oikean lapsen vanhempi. Seuraavaksi vaihdamme P:n ja S:n värit ( P saa S : n värin , S saa P :n värin ) ja S : n oikeasta lapsesta tulee musta. Alipuulla on edelleen sama juuriväri, joten ominaisuuksia 4 (kunkin punaisen solmun molemmat lapset ovat mustia) ja 5 (kaikki polut mistä tahansa kärjestä sen lehtisolmuihin sisältävät saman määrän mustia solmuja) ei rikota. Kuitenkin N :llä on nyt ylimääräinen musta esi-isä: joko P :stä tuli musta tai se oli musta ja S lisättiin mustaksi isovanhemmaksi. Siten N :n kautta kulkevat reitit kulkevat yhden mustan lisäsolmun läpi.

Sillä välin, jos polku ei kulje N :n läpi, on kaksi mahdollista vaihtoehtoa:

Hän käy läpi uuden veljen N. Sitten sen on mentävä S :n ja P :n läpi , jotka vain vaihtoivat värejä ja paikkoja. Siksi polku sisältää saman määrän mustia solmuja.
Se kulkee uuden sedän N , S :n oikean lapsen, kautta . Se kulki kerran S :n, S :n isän ja S :n oikean lapsen (joka oli punainen), kautta, mutta nyt se kulkee vain S :n kautta , joka on saanut entisen vanhemman värin, ja S :n oikean lapsen , jolla on on maalattu uudelleen punaisesta mustaksi (oletetaan, että väri S : musta). Vaikutus on, että tämä polku kulkee saman määrän mustia solmuja.

Joka tapauksessa mustien solmujen määrä näillä poluilla ei muutu. Siksi olemme palauttaneet ominaisuudet 4 (kunkin punaisen solmun molemmat lapset ovat mustia) ja 5 (kaikki polut mistä tahansa kärjestä sen lehtisolmuihin sisältävät saman määrän mustia solmuja). Kaavion valkoinen solmu voi olla joko punainen tai musta, mutta sen tulee osoittaa samaa väriä sekä muunnoksen alussa että lopussa.

void delete_case6 ( struct solmu * n ) { struct solmu * s = sisarus ( n ); s -> väri = n -> vanhempi -> väri ; n -> vanhempi -> väri = MUSTA ; if ( n == n -> vanhempi -> vasen ) { s -> oikea -> väri = MUSTA ; rotate_left ( n -> vanhempi ); } muu { s -> vasen -> väri = MUSTA ; rotate_right ( n -> vanhempi ); } }

Kaikki rekursiiviset funktiokutsut pyrstoidaan ja muunnetaan silmukoiksi, joten algoritmi vaatii O(1)-muistin . Yllä olevassa algoritmissa kaikki tapaukset yhdistetään vuorotellen, paitsi tapaus 3, jossa voi tapahtua paluu tapaukseen 1, mikä koskee solmun esi-isä: tämä on ainoa tapaus, jossa peräkkäinen toteutus on tehokas silmukka (yhden jälkeen kierto tapauksessa 3).

Häntärekursiota ei myöskään esiinny koskaan lapsisolmuissa, joten häntärekursiosilmukka voi siirtyä vain lapsisolmuista heidän peräkkäisiin vanhempiinsa. Tapaukseen 1 ei tule enempää kuin O(log n ) edestakaista matkaa (jossa n on solmujen kokonaismäärä puussa ennen poistamista). Jos kierto tapahtuu tapauksessa 2 (ainoa mahdollinen tapausten 1-3 syklissä), niin solmun N isä muuttuu punaiseksi kierron jälkeen ja poistumme syklistä. Siten tämän jakson aikana ei suoriteta enempää kuin yksi kierto. Silmukasta poistumisen jälkeen tulee enintään kaksi lisäkiertoa. Yleensä puussa ei ole enempää kuin kolme kiertoa.

Vertailu tasapainoiseen AVL-puuhun

Puun korkeus

Olkoon puun korkeus h, pisteiden vähimmäismäärä N. Sitten:

AVL-puulle . Koska , , N(h) kasvaa Fibonacci-sekvenssinä , joten , missä $N(h)=N(h-1)+N(h-2)+1$ $N(0) = 0$ $N(1) = 1$ $N(h)=\Theta (\lambda ^{h})$ $\lambda =({\sqrt {5}}+1)/2\noin 1,62$
punamustalle puulle $N(h)\geq 2^{{(h-1)/2}}=\Theta ({\sqrt {2}}^{h})$

Siksi samalla lehtimäärällä punamusta puu voi olla korkeampi kuin AVL-puu, mutta enintään kertoimella 1. [5] $\log \lambda /\log {\sqrt {2}}\noin 1,388$

Hae

Koska punamusta puu on pahimmassa tapauksessa korkeampi, haku siinä on hitaampaa, mutta aikahäviö ei ylitä 39%.

Lisää

Asennus vaatii enintään 2 kierrosta molemmissa puutyypeissä. Punamustan puun suuremman korkeuden vuoksi lisääminen voi kuitenkin kestää kauemmin.

Poisto

Punamustasta puusta poistaminen vaatii jopa 3 kiertoa, AVL-puussa se voi vaatia useita kierroksia puun syvyyteen (juureen asti). Siksi poistaminen punamustasta puusta on nopeampaa kuin poistaminen AVL-puusta. Kuitenkin testit osoittavat, että AVL-puut ovat nopeampia kuin puna-mustat puut kaikissa operaatioissa [6] [7] , viimeisimmän testin kirjoittaja ehdottaa, että punamustat puut voivat olla tehokkaampia suurella muistimäärällä [8] .

Muisti

Jokaisen solmun AVL-puu tallentaa korkeuseron (kokonaisluku -1 - +1, koodaukseen tarvitaan 2 bittiä). Punamusta puu jokaisessa solmussa tallentaa värin (1 bitti). Näin ollen punamusta puu voi olla taloudellisempi. (Totta, kun otetaan huomioon, että nykyaikaisissa tietokonejärjestelmissä muisti on varattu tavujen kerrannaisina, puut ovat täsmälleen samat)

Käytännössä kuitenkin molemmissa puutyypeissä käytetään kokonaislukuja, koska bittien kanssa työskentely vaatii prosessorin lisälaskelmia (yksi assembler-käsky ja %al 0x10000000). On kuitenkin olemassa punamusta-puun toteutuksia, jotka tallentavat väriarvon bitteinä. Esimerkki on Boost Multiindex . Värin bitin tallentamisen tarkoitus on vähentää puna-mustan puun muistin kulutusta ( Ordered indexes node compression ). Tämän toteutuksen väribittiä ei tallenneta erilliseen muuttujaan, vaan johonkin puun solmuosoittimista, jolloin se muuttuu leimatuksi osoittimeksi .

Todiste asymptoottisista rajoista

Punamustan puun, joka sisältää n sisäistä solmua, korkeus on . $O(log(n))$

Nimitykset:

$h(v)$ on juuretun alipuun korkeus $v$
$bh(v)$ on mustien solmujen lukumäärä (ei lasketa , jos se on musta) mistä tahansa alipuun lehdestä (kutsutaan mustaksi korkeudeksi) $v$ $v$

Lemma: Solmuun juurtuneella alipuulla on vähintään sisäiset solmut. $v$ $2^{bh(v)}-1$

Lemman todistus (korkeuden induktiolla):

Induktion perusta: . $h(v)=0$

Jos alipuun korkeus on nolla, sen on oltava nolla , joten . $v$ $bh(''v'')=0$

Niin:

2^{bh(v)}-1=2^{0}-1=1-1=0

Induktiovaihe: olkoon solmu sellainen, että alipuussa on myös vähintään sisäisiä solmuja. Osoittakaamme, että silloin , jolle , on ainakin sisäiset solmut. $v$ $h(v)=k$ $2^{bh(v)}-1$
$v'$ $h(v')=k+1$ $2^{bh(v')}-1$

Koska sillä on , se on sisäinen solmu. Sellaisenaan sillä on kaksi lasta, jotka molemmat ovat mustapituisia , joko (riippuen siitä, onko se punainen vai musta). Induktiohypoteesin mukaan jokaisella jälkeläisellä on vähintään sisäiset solmut, ja siksi sillä on vähintään $v'$ $h(v')>0$ $bh(v')$ $bh(v')-1$ $v'$
$2^{bh(v')-1}-1$ $v'$

2^{bh(v')-1}-1+2^{bh(v')-1}-1+1=2^{bh(v')}-1

sisäiset solmut.

Tämän lemman avulla voimme osoittaa, että puulla on logaritminen korkeus. Koska vähintään puolet minkä tahansa polun solmuista juuresta lehtiin on mustia (punamustan puun ominaisuus 4), juuren musta korkeus on vähintään . Lemman mukaan meillä on: $h(root)/2$

n\geq 2^{{{h({\teksti{juuri))) \over 2}}}-1\leftrightarrow \;\log _{2}{(n+1)}\geq {h({\ teksti{juuri))) \over 2}\leftrightarrow \;h({\text{root)))\leq 2\log _{2}{(n+1)}.

Juuren korkeus on siis . $O(log(n))$

Katso myös

Ensimmäinen syvyyshaku
Leveys ensimmäinen haku
Tasapainotetut (itsetasapainottavat) puut:

AVL puu
matriisipuu
Täysin tasapainoinen puu
laajeneva puu
B+-puut
2-3-puu
R-puu
B*-puu

Luettelo tietorakenteista (puista)

Linkit

Kirjallisuus

Kormen T., Leizerson C., Rivest R., Stein K. Algoritmit: rakentaminen ja analyysi = Introduction to algorithms. - 2. painos - M . : Kustantaja "Williams" , 2011. - S. 336-364. - ISBN 978-5-8459-0857-5 .

Muistiinpanot

↑ 1 2 tietorakennetta - Mistä termi "punainen/musta puu" tulee? - Software Engineering Stack Exchange . Haettu 4. tammikuuta 2019. Arkistoitu alkuperäisestä 5. tammikuuta 2019. (määrätön)
↑ Kurssi "Algoritmit: suunnittelu ja analyysi, osa 1", luento "Red-Black Trees" Arkistoitu 25. elokuuta 2014 Wayback Machinessa (Video 5:07 )
↑ Tohtori Dobbs - STL:n puna-mustat puut
↑ TreeMap-luokka . Haettu 13. maaliskuuta 2015. Arkistoitu alkuperäisestä 18. maaliskuuta 2015. (määrätön)
↑ suuren lehtimäärän rajassa
↑ AVL vs RB Arkistoitu 11. heinäkuuta 2016 Wayback Machinessa
↑ Red-Black vs AVL: vertailuarvot Arkistoitu 10. helmikuuta 2015 Wayback Machinessa
↑ AVL vs. Red-Black: the Decision Arkistoitu 10. helmikuuta 2015 Wayback Machinessa

Puu (tietorakenne)
Binäärihakupuu Puu (graafiteoria) puun rakenne
Binääripuut	binäärinen puu T-puu
Itsetasapainottavat binaaripuut	AA puu AVL puu Puna-musta puu Splay-puu puu sakkoilla karteesinen puu Fibonacci puu B-puu T-puu
B-puut	2-3-puu B⁺-puu B*-puu B x -puu UB puu 2-3-4 puu (a,b)-puu tanssiva puu
etuliite puita	suffiksi puu Pakattu etuliitepuu Kolmiosainen hakupuu
Avaruuden binaarinen osiointi	k-ulotteinen puu VP-puu
Ei-binääripuut	Quadtree oktreen Harva Voxel Octree eksponentiaalinen puu PQ puu
Avaruuden hajottaminen	R-puu Hilbert R-puu R+-puu R*-puu X-puu M-puu Fenwick puu Segmenttipuu
Muut puut	pino hash puu sormipuu metrinen puu Päällystyspuu BK-puu Kaksiketjuinen puu iDistance Linkistä leikattu puu LSM puu
Algoritmit	Leveys ensimmäinen haku Ensimmäinen syvyyshaku DSW-algoritmi kattava puu protokolla