Wskaż największą możliwą oraz najmniejszą możliwą wysokość drzewa binarnego

Teoria liczb, teoria grafów, indukcja
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
Ola00
Rozkręcam się
Rozkręcam się
Posty: 61
Rejestracja: 30 lis 2021, 13:55
Podziękowania: 14 razy

Wskaż największą możliwą oraz najmniejszą możliwą wysokość drzewa binarnego

Post autor: Ola00 »

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.
kerajs
Fachowiec
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

Post autor: kerajs »

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)
Ostatnio zmieniony 28 kwie 2022, 13:34 przez Jerry, łącznie zmieniany 1 raz.
Powód: poprawa wiadomości; dodałem zgubiony )
ODPOWIEDZ