b'\n_START_ARTICLE_\nLosowe drzewo binarne\n_START_PARAGRAPH_\nLosowe drzewo binarne \xe2\x80\x93 losowe drzewo binarne oznacza drzewo binarne losowo wybrane z pewnego rozk\xc5\x82adu prawdopodobie\xc5\x84stwa na drzewach binarnych. Powszechnie u\xc5\xbcywane s\xc4\x85 dwie metody konstruowania losowych drzew binarnych: tworzone przez w\xc4\x99z\xc5\x82y wstawiane pojedynczo zgodnie z losow\xc4\x85 permutacj\xc4\x85 oraz drzewa binarne wybrane z r\xc3\xb3wnomiernym rozk\xc5\x82adem dyskretnym, w kt\xc3\xb3rym wszystkie odr\xc4\x99bne drzewa s\xc4\x85 jednakowo prawdopodobne. Dost\xc4\x99pne s\xc4\x85 r\xc3\xb3wnie\xc5\xbc inne metody tworzenia losowych drzew binarnych, na przyk\xc5\x82ad przez wielokrotny podzia\xc5\x82.\n_START_SECTION_\nDrzewa binarne z losowych permutacji\n_START_PARAGRAPH_\nDla ka\xc5\xbcdego zestawu liczb mo\xc5\xbcna tworzy\xc4\x87 binarne drzewo poszukiwa\xc5\x84, w kt\xc3\xb3rym ka\xc5\xbcda liczba jest wstawiana w kolejno\xc5\x9bci jako li\xc5\x9b\xc4\x87 w drzewie bez zmiany struktury wcze\xc5\x9bniej wprowadzonych numer\xc3\xb3w. Pozycja w kt\xc3\xb3rym ka\xc5\xbcda liczba powinna zosta\xc4\x87 dodana jest jednoznacznie okre\xc5\x9blona przez wyszukiwanie binarne w drzewie utworzone przez poprzednie liczby. Na przyk\xc5\x82ad je\xc5\x9bli te trzy liczby (1,3,2) s\xc4\x85 wstawiane do drzewa w tej sekwencji, liczba 1 b\xc4\x99dzie znajdowa\xc5\x82a si\xc4\x99 w korzeniu drzewa, liczba 3 zostanie umieszczona jako prawe dziecko liczby 1, a liczba 2 jako lewe dziecko liczby 3. Istnieje sze\xc5\x9b\xc4\x87 r\xc3\xb3\xc5\xbcnych permutacji liczb (1,2,3), ale tylko pi\xc4\x99\xc4\x87 drzew mo\xc5\xbce by\xc4\x87 z nich skonstruowane. To dlatego, \xc5\xbce permutacje (2,1,3) i (2,3,1) tworz\xc4\x85 te same drzewa.'