Losowe drzewo binarne – 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 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.