To dlatego, że permutacje (2,1,3) i (2,3,1) tworzą te same drzewa.
Najdłuższa ścieżka 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:
gdzie β jest to unikatowy numer z zakresu 0 <β <1 spełniający równanie
Bibliografia 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.
Kategoria:Drzewa (informatyka) Kategoria:Rachunek prawdopodobieństwa