Proszę o odpowiedź w jaki sposób została wyliczona wysokość drzew?
@masterkwi
W przypadku drzewa zrównoważonego odpowiedź jest prosta.
Root to poziom 0 (jeden node/węzeł). Wraz z dodawaniem poziomów liczba nodów się podwaja. Więc wzór na maksymalną ilość nodów to zawsze:
n = 2h+1-1, gdzie h to liczba poziomów, n to liczba nodów
Przekształcamy i wychodzi na to, że:
h = log2(n+1)-1
Co się zwyczajowo określa jako wysokość drzewa jest log n.
Co do drzew niezrównoważonych - drzewa skrajnie niezrównoważone mają tyle poziomów ile elementów, więc tutaj się nie wypowiem w kwestii wzoru.
Co do drzew niezrównoważonych - drzewa skrajnie niezrównoważone mają tyle poziomów ile elementów, więc tutaj się nie wypowiem w kwestii wzoru.
A w skrajnie niewyważonym to nie jest n-1 ?
Wielki Pomidor napisał(a):
A w skrajnie niewyważonym to nie jest n-1 ?
Oczywiście masz rację - root to poziom zero (jak pisałem wcześniej), zatem wysokość to n-1.
Po prostu użyłem skrótu myślowego pisząc o drzewie niezrównoważonym i faktcznie mogło to wyglądać jakby to było n.