Losowe drzewo binarne

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

Losowe drzewo binarne – w informatyce i teorii prawdopodobieństwa, losowe drzewo binarne oznacza drzewo binarne losowo wybrane z pewnego rozkładu prawdopodobieństwa na drzewach binarnych. Powszechnie używane są dwie metody konstruowania losowych drzew binarnych: tworzone przez węzły wstawiane pojedynczo zgodnie z losową permutacją oraz drzewa binarne wybrane z równomiernym rozkładem dyskretnym, w którym wszystkie odrębne drzewa są jednakowo prawdopodobne. Dostępne są również inne metody tworzenia losowych drzew binarnych, na przykład przez wielokrotny podział.

Drzewa binarne z losowych permutacji[edytuj | edytuj kod]

Dla każdego zestawu liczb można tworzyć binarne drzewo poszukiwań, w którym każda liczba jest wstawiana w kolejności jako liść w drzewie bez zmiany struktury wcześniej wprowadzonych numerów. Pozycja w którym każda liczba powinna zostać dodana jest jednoznacznie określona przez wyszukiwanie binarne w drzewie utworzone przez poprzednie liczby. Na przykład jeśli te trzy liczby (1,3,2) są wstawiane do drzewa w tej sekwencji, liczba 1 będzie znajdowała się w korzeniu drzewa, liczba 3 zostanie umieszczona jako prawe dziecko liczby 1, a liczba 2 jako lewe dziecko liczby 3. Istnieje sześć różnych permutacji liczb (1,2,3), ale tylko pięć drzew może być z nich skonstruowane. To dlatego, że permutacje (2,1,3) i (2,3,1) tworzą te same drzewa.

Najdłuższa ścieżka[edytuj | edytuj kod]

Choć nie tak łatwo analizować jak średnią długość ścieżki, podjęto wiele badań dotyczących określenia najdłuższej ścieżki drzewa binarnego wybranego w sposób losowy. Wiadomo, że ta długość dla drzewa z n węzłów to niemal na pewno:

\frac{1}{\beta}\log n \approx 4.311\log n,

gdzie β jest to unikatowy numer z zakresu 0 <β <1 spełniający równanie

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

Bibliografia[edytuj | edytuj kod]

  • Mahmoud Hosam M., Evolution of Random Search Trees, John Wiley & Sons, 1992.
  • Reed Bruce, The height of a random binary search tree, Journal of the ACM 50, 2003.
  • Seidel Raimund, Aragon Cecilia R., Randomized Search Trees, Algorithmica 16, 1996.