Wskaż największą możliwą oraz najmniejszą możliwą wysokość drzewa binarnego
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Wskaż największą możliwą oraz najmniejszą możliwą wysokość drzewa binarnego
Niech \(n \in \nn \), \(n \ge 3 \) .Wskaż największą możliwą oraz najmniejszą możliwą wysokość drzewa binarnego mającego n wierzchołków.
-
- Fachowiec
- Posty: 2963
- Rejestracja: 14 lis 2016, 14:38
- Podziękowania: 33 razy
- Otrzymane podziękowania: 1303 razy
- Płeć:
Re: Wskaż największą możliwą oraz najmniejszą możliwą wysokość drzewa binarnego
Dla każdego \(n\) istnieje naturalne k, takie że \(T_{k-1}< n \le T_k \) gdzie \(T_m\) jest m-tą liczbą trójkątną, ( czyli \( \frac{(k-1)k}{2} <n \le \frac{k(k+1)}{2} \) ) a wtedy \(k\) jest najmniejszą (tak jest wtedy gdy każdy poziom(ewentualnie prócz ostatniego) jest maksymalnie wypełniony) wysokością regularnego drzewa binarnego .
Największa wysokość takiego drzewa to \(\frac{n-1}{2}\) (rozwijamy przykładowo tylko najbardziej skrajne prawe liście)
Największa wysokość takiego drzewa to \(\frac{n-1}{2}\) (rozwijamy przykładowo tylko najbardziej skrajne prawe liście)
Ostatnio zmieniony 28 kwie 2022, 13:34 przez Jerry, łącznie zmieniany 1 raz.
Powód: poprawa wiadomości; dodałem zgubiony )
Powód: poprawa wiadomości; dodałem zgubiony )