Tilfeldig binært tre - Random binary tree

I informatikk og sannsynlighetsteori er et tilfeldig binært tre et binært tre valgt tilfeldig fra en sannsynlighetsfordeling på binære trær. To forskjellige fordelinger brukes ofte: binære trær dannet ved å sette inn noder en om gangen i henhold til en tilfeldig permutasjon , og binære trær valgt fra en jevn diskret fordeling der alle forskjellige trær er like sannsynlige. Det er også mulig å danne andre fordelinger, for eksempel ved gjentatt splitting. Å legge til og fjerne noder direkte i et tilfeldig binært tre vil generelt forstyrre dets tilfeldige struktur, men treap og relaterte randomiserte binære søketre datastrukturer bruker prinsippet om binære trær dannet av en tilfeldig permutasjon for å opprettholde et balansert binært søketre dynamisk ettersom noder settes inn og slettes.

For tilfeldige trær som ikke nødvendigvis er binære, se tilfeldig tre .

Binære trær fra tilfeldige permutasjoner

For ethvert sett med tall (eller, mer generelt, verdier fra en total rekkefølge ), kan man danne et binært søketre der hvert tall settes inn i rekkefølge som et blad på treet, uten å endre strukturen til de tidligere innsatte tallene. Posisjonen som hvert tall skal settes inn i, er unikt bestemt av et binært søk i treet dannet av de forrige tallene. For eksempel, hvis de tre tallene (1,3,2) settes inn i et tre i den sekvensen, vil tallet 1 sitte ved roten av treet, tallet 3 vil bli plassert som det riktige barnet og tallet 2 som venstre barn av tallet 3. Det er seks forskjellige permutasjoner av tallene (1,2,3), men bare fem trær kan konstrueres ut fra dem. Det er fordi permutasjonene (2,1,3) og (2,3,1) danner det samme treet.

Forventet dybde på en node

For et fast valg av en verdi $x$ i et gitt sett med $n$ tall, hvis en tilfeldig permuterer tallene og danner et binært tre fra dem som beskrevet ovenfor, forventes verdien av lengden på banen fra roten til treet til $x$ er høyst $2 log n + O (1)$ , hvor " $logg$ " betegner den naturlige logaritmefunksjonen og $O$ introduserer stor O -notasjon . For, det forventede antallet forfedre til $x$ er ved forventningens linearitet lik summen, over alle andre verdier $y$ i settet, for sannsynligheten for at $y$ er en stamfar til $x$ . Og en verdi $y$ er en stamfar til $x$ nøyaktig når $y$ er det første elementet som skal settes inn fra elementene i intervallet $[x, y]$ . Dermed har verdiene som er tilstøtende til $x$ i den sorterte verdisekvensen sannsynlighet $1/2$ for å være en stamfar til $x$ , verdiene ett skritt unna har sannsynlighet $1/3$ , etc. Legger du til disse sannsynlighetene for alle posisjoner i den sorterte sekvensen gir to ganger et harmonisk nummer , som fører til grensen ovenfor. En grense for dette skjemaet gjelder også for den forventede søkelengden til en vei til en fast verdi $x$ som ikke er en del av det gitte settet.

For å forstå det ved å bruke min-max-poster. Tallet i en tilfeldig permutasjon er min (max) posten betyr at det er min (max) verdien fra den første posisjonen til dens posisjon. Tenk på et enkelt eksempel $l$ = (2, 4, 3, 6, 5, 1). Min -postene i $l$ er 2, 1 ved å søke etter min -verdien fra start til slutt. På samme måte er maks -kodene i $l$ 2, 4, 6. Det forventede antallet min (maks) poster er all sannsynlighet for hvert tall i en tilfeldig permutasjon. For posisjon $i$ har den sannsynligheten for 1/ $i$ . Derfor er det forventede antallet min (maks) poster et harmonisk tall. For å søke 3 i $l$ , er alle tallene i (2, 1) mindre enn 3, og (4, 6, 5, 1) er større enn 3. Søket på $ls$ tilfeldige binære tre teller bare maksimale poster på (2 , 1) og min -poster på (4, 6, 5, 1) - derfor er det to ganger et harmonisk tall.

Den lengste stien

Selv om det ikke er like enkelt å analysere som den gjennomsnittlige banelengden, har det også vært mye forskning på å bestemme forventningen (eller høy sannsynlighetsgrense) for lengden på den lengste banen i et binært søketre generert fra en tilfeldig innsettingsrekkefølge. Det er nå kjent at denne lengden, for et tre med $n$ noder, er nesten sikkert

{\ displaystyle {\ frac {1} {\ beta}} \ log n \ ca 4.311 \ log n,}

hvor $β$ er det unike tallet i området $0 < β <1 som$ tilfredsstiller ligningen

{\ displaystyle \ displaystyle 2 \ beta e^{1- \ beta} = 1.}

Forventet antall blader

I modellen for tilfeldig permutasjon har hvert av tallene fra settet med tall som ble brukt for å danne treet, bortsett fra det minste og største av tallene, sannsynlighet $1/3$ for å være et blad i treet, for det er et blad når den satt inn etter sine to naboer, og noen av de seks permutasjonene til disse to naboene, og det er like sannsynlig. Ved lignende resonnement har den minste og største av tallene sannsynlighet $1/2$ for å være et blad. Derfor er det forventede antall blader summen av disse sannsynlighetene, som for $n \geq 2$ er nøyaktig $(n + 1)/3$ .

Strahler nummer

Den Strahler antall av et tre er et mer følsomt mål på avstanden fra et blad der en node har Strahler nummer $jeg$ når det enten har et barn med det nummeret eller to barn med nummer $i - en$ . For n -node tilfeldige binære søketrær, antyder simuleringer at det forventede Strahler -tallet er . Imidlertid er bare den øvre grensen faktisk bevist. ${\ displaystyle \ log _ {3} n+o (\ log n)}$ ${\ displaystyle \ log _ {3} n+O (1)}$

Treaps og randomiserte binære søketrær

I applikasjoner med binære søketre -datastrukturer er det sjelden at verdiene i treet settes inn uten sletting i en tilfeldig rekkefølge, noe som begrenser direkte applikasjoner av tilfeldige binære trær. Imidlertid har algoritmdesignere utviklet datastrukturer som gjør at innsetting og sletting kan utføres i et binært søketre, og ved hvert trinn opprettholder egenskapen at treets form er en tilfeldig variabel med samme fordeling som et tilfeldig binært søk tre.

Hvis et gitt sett med ordnede tall tildeles numeriske prioriteringer (distinkte tall som ikke er relatert til verdiene), kan disse prioritetene brukes til å konstruere et kartesisk tre for tallene, et binært tre som har sin ordreovergangssekvens den sorterte sekvensen av tallene og det er haugbestilt av prioriteringer. Selv om mer effektive konstruksjonsalgoritmer er kjent, er det nyttig å tenke på et kartesisk tre som konstruert ved å sette inn de oppgitte tallene i et binært søketre i prioritert rekkefølge. Ved å velge prioritetene enten å være et sett med uavhengige tilfeldige reelle tall i enhetsintervallet, eller ved å velge dem som en tilfeldig permutasjon av tallene fra $1$ til $n$ (hvor $n$ er antall noder i treet), og ved å opprettholde bunkeordreegenskapen ved hjelp av trerotasjoner etter enhver innsetting eller sletting av en node, er det mulig å opprettholde en datastruktur som oppfører seg som et tilfeldig binært søketre. En slik datastruktur er kjent som en treap eller et randomisert binært søketre.

Jevnt tilfeldige binære trær

Antall binære trær med n noder er et katalansk tall : for $n = 1, 2, 3, ... er$ dette antallet trær

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796,\dots

(sekvens A000108 i OEIS ).

Så hvis et av disse trærne velges ensartet tilfeldig, er sannsynligheten det gjensidige for et katalansk tall. Trær i denne modellen har forventet dybde proporsjonal med kvadratroten til $n$ , i stedet for logaritmen. Imidlertid er det forventede Strahler -tallet for et jevnt tilfeldig n -node binært tre lavere enn det forventede Strahler -antallet tilfeldige binære søketrær. ${\ displaystyle \ log _ {4} n+O (1)}$

På grunn av deres store høyder, brukes denne modellen av tilfredsstillende tilfeldige trær vanligvis ikke for binære søketrær, men den har blitt brukt på problemer med å modellere parse-trærne for algebraiske uttrykk i kompilatordesign (der ovennevnte bundet til Strahler-tall oversetter i antall registre som trengs for å evaluere et uttrykk) og for å modellere evolusjonære trær . I noen tilfeller kan analysen av tilfeldige binære trær under modellen for tilfeldig permutasjon automatisk overføres til uniformsmodellen.

Tilfeldig splittede trær

Devroye & Kruszewski (1996) genererer tilfeldige binære trær med $n-$ noder ved å generere en virkelig verdsatt tilfeldig variabel $x$ i enhetsintervallet $(0,1)$ , tilordne de første $xn-$ nodene (avrundet ned til et heltall noder) til venstre subtree, den neste noden til roten, og de resterende nodene til høyre subtree, og fortsetter rekursivt i hvert subtree. Hvis $x$ velges ensartet tilfeldig i intervallet, er resultatet det samme som det tilfeldige binære søketreet som genereres av en tilfeldig permutasjon av nodene, ettersom enhver node er like sannsynlig å bli valgt som rot; Imidlertid lar denne formuleringen andre distribusjoner brukes i stedet. For eksempel, i den jevnt tilfeldige binære tremodellen, må en av dens to undertrær også være ensartet tilfeldig når en rot er fikset, så den ensartede tilfeldige modellen kan også genereres ved et annet distribusjonsvalg for $x$ . Som Devroye og Kruszewski viser, ved å velge en beta-fordeling på $x$ og ved å bruke et passende formvalg for å tegne hver av grenene, kan de matematiske trærne som genereres av denne prosessen brukes til å lage realistisk utseende botaniske trær.

Merknader

Referanser

Aldous, David (1996), "Sannsynlighetsfordelinger på kladogrammer", i Aldous, David; Pemantle, Robin (red.), Random Discrete Structures , IMA Volumes in Mathematics and its Applications, 76 , Springer-Verlag, s. 1–18.
Devroye, Luc (1986), "Et notat om høyden på binære søketrær", Journal of the ACM , 33 (3): 489–498, doi : 10.1145/5925.5930.
Devroye, Luc; Kruszewski, Paul (1995), "En merknad om Horton-Strahler-nummeret for tilfeldige trær", Information Processing Letters , 56 (2): 95–99, doi : 10.1016/0020-0190 (95) 00114-R.
Devroye, Luc; Kruszewski, Paul (1996), "The botanical beauty of random binary trees", i Brandenburg, Franz J. (red.), Graph Drawing: 3rd Int. Symp., GD'95, Passau, Tyskland, 20.-22. September 1995 , Forelesningsnotater i informatikk, 1027 , Springer-Verlag, s. 166–177, doi : 10.1007/BFb0021801 , ISBN 978-3-540-60723-6.
Drmota, Michael (2009), Random Trees: An Interplay between Combinatorics and Probability , Springer-Verlag, ISBN 978-3-211-75355-2.
Flajolet, P .; Raoult, JC; Vuillemin, J. (1979), "Antall registre som kreves for å evaluere aritmetiske uttrykk", Theoretical Computer Science , 9 (1): 99–125, doi : 10.1016/0304-3975 (79) 90009-4.
Hibbard, Thomas N. (1962), "Noen kombinatoriske egenskaper til visse trær med applikasjoner for søk og sortering", Journal of the ACM , 9 (1): 13–28, doi : 10.1145/321105.321108.
Knuth, Donald E. (1973), "6.2.2 Binary Tree Searching", The Art of Computer Programming , III , Addison-Wesley, s. 422–451.
Knuth, Donald E. (2005), "Utkast til seksjon 7.2.1.6: Generering av alle trær" , The Art of Computer Programming , IV.
Kruszewski, Paul (1999), "En merknad om Horton-Strahler-nummeret for tilfeldige binære søketrær", Information Processing Letters , 69 (1): 47–51, doi : 10.1016/S0020-0190 (98) 00192-6.
Mahmoud, Hosam M. (1992), Evolution of Random Search Trees , John Wiley & Sons.
Martinez, Conrado; Roura, Salvador (1998), "Randomized binary search trees" , Journal of the ACM , 45 (2): 288–323, CiteSeerX 10.1.1.17.243 , doi : 10.1145/274787.274812.
Pittel, B. (1985), "Asymptotisk vekst av en klasse tilfeldige trær", Annals of Probability , 13 (2): 414–427, doi : 10.1214/aop/1176993000.
Reed, Bruce (2003), "The height of a random binary search tree", Journal of the ACM , 50 (3): 306–332, doi : 10.1145/765568.765571.
Robson, JM (1979), "The height of binary search trees", Australian Computer Journal , 11 : 151–153.
Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized Search Trees" , Algorithmica , 16 (4/5): 464–497, doi : 10.1007/s004539900061.

Eksterne linker

Åpne datastrukturer - Kapittel 7 - Tilfeldige binære søketrær , Pat Morin

Languages

In other projects