Karteesinen puu

karteesinen puu
Englanti  Treap
Tyyppi Binäärihakupuu
Keksintövuosi 1989
Tekijä Raimund Siedel, Cecilia Aragon
Monimutkaisuus O - symboleissa
Keskiverto Pahimmillaan
Rakennus
Hae
Lisää
Poistaminen
 Mediatiedostot Wikimedia Commonsissa

Karteesinen puu  on binääripuu , jonka solmut tallentavat:

Viittaus pääsolmuun on valinnainen, se on toivottavaa vain lineaarisen puunrakennusalgoritmille.

Karteesinen puu ei ole itsetasapainottava tavallisessa merkityksessä, ja sitä käytetään seuraavista syistä:

Karteesisen puun haitat:

Terminologia

Englanninkielisessä kirjallisuudessa karteesista puuta, joka on rakennettu joukolle annettuja avaimia ja niitä muodostettaessa niille osoitettuja satunnaisia ​​painoja, kutsutaan lompakkosanaksi treap , koska se yhdistää lajittelukasapuun ( kasa ) ja satunnaisen binääripuun ( puu ) ominaisuudet. ) logaritmisella korkeusodotuksella . Venäjän kielessä sanat ducha [1] ( puu + kasa ), deramide ( puu + pyramidi ), kurevo ( kasa + puu ) ehdotettiin samanlaisiksi kuin sana treap .

Yksinkertaisin algoritmi karteesisen puun rakentamiseen

Yksinkertaisin ymmärrettävä algoritmi karteesisen puun muodostamiseksi dataparien (x, y) joukosta on seuraava. Järjestetään kaikki parit avaimella x ja numeroidaan tuloksena oleva näppäinsarja y:

y(1), y(2), y(3), …, y(n).

Etsitään pienin avain y. Olkoon se y(k). Siitä tulee puun juuri. Avain y(k) jakaa näppäinsarjan y kahteen osaan:

y(1), …, y(k-1); y(k+1), …, y(n).

Jokaisesta niistä löydämme minimin y - nämä ovat solmun y (k) lapset - vasemmalla ja oikealla. Saatujen 4 kappaleen (mahdollisesti vähemmän) kanssa teemme saman. Ehdotettu algoritmi karteesisen puun rakentamiseksi perustuu rekursioon: etsimme jonosta minimin y ja annamme sen juureksi. found y jakaa sekvenssin kahteen osaan, jokaiselle osalle suoritetaan algoritmi karteesisen puun rakentamiseksi.

Kaavamaisesti tämä voidaan kirjoittaa seuraavasti:

T( y(1), ..., y(n) ) = juuri: y(k) vasen_puu: T( y(1), ..., y(k−1) ) oikea_puu: T( y(k+1), ..., y(n)) ) missä y(k) = min( y(1), ..., y(n) )


Rakenteen yksiselitteisyysominaisuus

Tästä algoritmista seuraa, että parien joukko (x, y) määrittää yksiselitteisesti karteesisen puun rakenteen. Vertailun vuoksi huomaa, että binäärihakupuuhun tallennetut avaimet eivät määritä yksiselitteisesti puun rakennetta. Sama pätee binäärikekoon - binäärikeon rakenne (miten avaimet jakautuvat solmujen kesken) ei riipu vain itse avainjoukosta, vaan myös sekvenssistä, jossa ne lisätään. Karteesisessa puussa ei ole tällaista epäselvyyttä.

Lineaarinen puunrakennusalgoritmi

Toinen puunrakennusalgoritmi perustuu myös rekursioon. Vasta nyt lisäämme elementit y peräkkäin ja rakennamme puun uudelleen. Puu T(y(1), …, y(k+1)) rakennetaan puusta T(y(1), …, y(k)) ja seuraavasta elementistä y(k+1).

T( y(1), ..., y(k+1) ) = F ( T( y(1), ..., y(k) ), y(k+1) )

Jokaisessa vaiheessa muistamme linkin viimeksi lisättyyn solmuun. Hän tulee olemaan oikealla. Olemme todellakin tilaaneet avaimet y niihin liitetyn avaimen x mukaan. Koska karteesinen puu on hakupuu, vaakaviivalle projisoinnin jälkeen x-näppäinten on kasvattava vasemmalta oikealle. Oikeanpuoleisella solmulla on aina suurin mahdollinen avainarvo x.

Funktio F, joka kuvaa edellisen vaiheen karteesisen puun T(y(1), …, y(k)) ja seuraavan y(k+1) uudeksi puuksi T(y(1), …, y(k) +1)) seuraavasti. Solmun y(k+1) pystysuora on määritelty. Meidän on päätettävä sen horisontaalisuudesta. Ensin tarkistetaan, voidaanko uudesta solmusta y(k+1) tehdä solmun y(k) oikea lapsi - tämä tulee tehdä, jos y(k+1) > y(k). Muussa tapauksessa nostetaan rinnettä solmusta y(k) ja katsotaan sinne tallennettua y:n arvoa. Kiipeä rinnettä ylös, kunnes löydämme solmun, jossa y:n arvo on pienempi kuin y(k+1), minkä jälkeen teemme y(k+1):stä sen oikea lapsi ja sen edellisestä oikeasta lapsesta y(:n vasen lapsi k+ yksi).

Tämä algoritmin kuoletus (kaikkien vaiheiden summana) toimii lineaarisessa ajassa (lisättyjen solmujen lukumäärän mukaan). Todellakin, heti kun "asimme" minkä tahansa solmun yli kiipeämällä rinnettä ylöspäin, emme koskaan tapaa sitä, kun lisäämme seuraavia solmuja. Siten rinteessä olevien askelmien kokonaismäärä ei voi olla suurempi kuin solmujen kokonaismäärä.

Muistiinpanot

  1. ↑ Donald Knuth . The Art of Computer Programming, Volume 3. Sorting and Searching = The Art of Computer Programming, vol.3. Lajittelu ja haku. - 2. painos - M .: "Williams" , 2007. - ISBN 0-201-89685-0 .

Linkit

Kirjallisuus