Wysokość drzewa

0

Proszę o odpowiedź w jaki sposób została wyliczona wysokość drzew?

wysokoscdrzewa.jpg

1

@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.

0

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 ?

0
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.

1 użytkowników online, w tym zalogowanych: 0, gości: 1