Kartesisk træ

kartesisk træ
engelsk  Treap
Type Binært søgetræ
Opfindelsens år 1989
Forfatter Raimund Siedel, Cecilia Aragon
Kompleksitet i O-symboler
Gennemsnit I værste fald
Bygning
Søg
Indsæt
Fjernelse
 Mediefiler på Wikimedia Commons

Et kartesisk træ  er et binært træ, hvis noder lagrer:

En reference til den overordnede node er valgfri, den er kun ønskelig for den lineære træbygningsalgoritme.

Det kartesiske træ er ikke selvbalancerende i sædvanlig forstand og bruges af følgende årsager:

Ulemper ved kartesisk træ:

Terminologi

I engelsk litteratur kaldes et kartesisk træ bygget til en række givne nøgler og tilfældige vægte, der er tildelt dem, når de konstrueres, tegnebogens ord treap , da det kombinerer egenskaberne af et sorteringsdyngetræ ( heap ) og et tilfældigt binært træ ( træ ). ) med en logaritmisk forventning om højden. På russisk blev ordene ducha [1] ( træ + bunke ), deramid ( træ + pyramide ), kurevo ( bunke + træ ) foreslået svarende til ordet treap .

Den enkleste algoritme til at konstruere et kartesisk træ

Den nemmeste at forstå algoritme til at konstruere et kartesisk træ ud fra et sæt af datapar (x, y) er som følger. Lad os sortere alle par efter tast x og nummerere den resulterende sekvens af tasterne y:

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

Lad os finde minimumsnøglen y. Lad det være y(k). Det vil være roden til træet. Tasten y(k) deler rækkefølgen af ​​tasterne y i to:

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

I hver af dem finder vi minimum y - disse vil være børnene af noden y (k) - venstre og højre. Med de resulterende 4 stykker (muligvis færre), vil vi gøre det samme. Den foreslåede algoritme til at konstruere et kartesisk træ er baseret på rekursion: vi finder minimum y i sekvensen og tildeler den som roden. fundet y opdeler sekvensen i to dele, for hver af delene kører vi algoritmen til at konstruere et kartesisk træ.

Skematisk kan dette skrives som følger:

T( y(1), ..., y(n) ) = rod: y(k) venstre_træ: T( y(1), ..., y(k−1) ) højre_træ: T( y(k+1), ..., y(n))) hvor y(k) = min(y(1), ..., y(n))


Struktur entydighedsegenskab

Det følger af denne algoritme, at sættet af par (x, y) entydigt bestemmer strukturen af ​​det kartesiske træ. Bemærk til sammenligning, at det sæt nøgler, der er gemt i et binært søgetræ, ikke entydigt bestemmer træets struktur. Det samme gælder for den binære heap - hvad strukturen af ​​den binære heap vil være (hvordan nøglerne er fordelt mellem noderne) afhænger ikke kun af selve nøglesættet, men også af rækkefølgen, hvori de tilføjes. Der er ingen sådan tvetydighed i et kartesisk træ.

Lineær trækonstruktionsalgoritme

En anden træbygningsalgoritme er også baseret på rekursion. Først nu vil vi sekventielt tilføje elementer y og genopbygge træet. Træet T(y(1), …, y(k+1)) vil blive bygget af træet T(y(1), …, y(k)) og det næste element y(k+1).

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

Ved hvert trin vil vi huske linket til den sidst tilføjede node. Han vil være til højre. Faktisk har vi bestilt nøglerne y i henhold til nøglen x knyttet til dem. Da et kartesisk træ er et søgetræ, skal x-tasterne efter projektion på en vandret linje øges fra venstre mod højre. Noden længst til højre har altid den højest mulige nøgleværdi x.

Funktion F, der kortlægger det kartesiske træ T(y(1), …, y(k)) i det foregående trin og det næste y(k+1) til et nyt træ T(y(1), …, y(k) +1)), som følger. Det lodrette for knudepunkt y(k+1) er defineret. Vi er nødt til at beslutte os for det horisontale. Først tjekker vi om den nye node y(k+1) kan gøres til det rigtige barn af node y(k) - dette skal gøres hvis y(k+1) > y(k). Ellers går vi op ad hældningen fra knudepunktet y(k) og ser på værdien af ​​y, der er gemt der. Klatre op ad skråningen, indtil vi finder en node, hvor værdien af ​​y er mindre end y(k+1), hvorefter vi gør y(k+1) til dets højre barn, og gør dets forrige højre barn til venstre barn af y( k+ en).

Denne algoritme-amortisering (i summen af ​​alle trin) fungerer i lineær tid (i henhold til antallet af tilføjede noder). Så snart vi "trådte" over en hvilken som helst knude og klatrede op ad skråningen, vil vi aldrig møde den, når vi tilføjer de næste knudepunkter. Det samlede antal trin op ad skråningen kan således ikke være større end det samlede antal knudepunkter.

Noter

  1. ↑ Donald Knuth . The Art of Computer Programming, bind 3. Sortering og søgning = The Art of Computer Programming, vol.3. Sortering og søgning. - 2. udg. - M .: "Williams" , 2007. - ISBN 0-201-89685-0 .

Links

Litteratur