Cecilia Holmgren: Split-träd och Galton-Watson-träd: Två viktiga klasser av slumpträd

Ett träd är en sammanhängande graf utan cykler. Jag kommer att prata om slumpträd, träd som konstrueras med en slumpmässig procedur.

Splitträd introducerades av Devroye (1998) för att förena många kända typer av slumpträd i en gemensam klass. Många splitträd används som sökalgoritmer i datorer, exempelvis är det binära sökträdet visualiseringen av den mest kända sökalgoritmen Quicksort. Introduktionen av splitträd låter många typer av träd studeras gemensamt, där man normalt behöver göra separata studier för varje enskilt träd i klassen. Splitträd bildas genom att n stycken nycklar delas ut till noderna i trädet på ett slumpmässigt sätt. Höjden på trädet blir logaritmisk och begränsas då av C log n där C är en konstant.

Galton-Watson-träd är en annan viktig klass av slumpträd. Dessa introducerades 1875 av Galton och Watson för att beskriva om ett familjenamn dör ut, där namnet går vidare från far till son och dör ut om ingen man i de senare generationerna får söner. Trädet kan bli ändligt eller oändligt beroende på väntevärdet för antalet söner. Många slumpträd som studeras av kombinatoriker kan förenas med Galton-Watson träd som är betingade på att totala antalet noder är n. Höjden av dessa träd begränsas av C√n.

Jag kommer att beskriva dessa bägge viktiga klasser av slumpträd och diskutera resultat och metoder för att karaktärisera träden. Det finns främst två typer av metoder för att studera slumpträd: analytiska och probabilistiska. I min egen forskning om slumpträd har jag fokuserat på probabilistiska metoder, bl.a. har jag använt förnyelseteori för att hitta fördelningen för totala väglängden av splitträd (söktiden för motsvarande algoritmer) vilket jag också kommer att berätta om.