forum.zadania.info

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.

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)