Lekcja: "Algorytmy sortujące - drzewa binarne, sortowanie przez kopcowanie"
Ścieżką nazywamy ciąg węzłów drzewa binarnego spełniających warunek, iż każdy węzeł poprzedni jest rodzicem węzła następnego. Jeśli ścieżka składa się z k węzłów, to długością ścieżki jest liczba k - 1.
W celu zrozumienia zawiłej definicji zilustrujemy to przykładem.
Na rysunku została przedstawiona ścieżka biegnąca przez węzły {d[1], d[2], d[5], d[10]} - zawiera ona cztery węzły, ma zatem długość równą 3. Wysokością drzewa binarnego nazwiemy długość najdłuższej ścieżki od korzenia do liścia. W powyższym przykładzie taka ścieżka ma długość równą 3 – zatem wysokość przedstawionego drzewa ma wysokość równą 3.
Dla n węzłów zrównoważone drzewo binarne ma wysokość równą:
Jedynym amerykańskim politykiem, który podpisał wszystkie cztery dokumenty kluczowe dla USA, czyli Deklarację Niepodległości, traktat pokojowy z Francją, traktat pokojowy z Wielką Brytanią i Konstytucję był Beniamin Franklin.
