Drzewo Sterna-Brocota

Drzewo Sterna-Brocota – drzewo binarne zawierające wszystkie dodatnie ułamki nieskracalne.

Konstrukcja

Zaczynamy od ${\frac {0}{1}}$ – symbolizującego zero i ${\frac {1}{0}}$ symbolizującego nieskończoność. Następnie na kolejnych piętrach drzewa wpisujemy „pomiędzy” wartości ${\frac {a}{b}}$ oraz ${\frac {c}{d}}$ wartość ${\frac {a+c}{b+d}}$ – patrz ilustracja.

Własności

• W drzewie występują wszystkie dodatnie liczby wymierne zapisane jako ułamki nieskracalne.
• Każda liczba wymierna dodatnia występuje w drzewie dokładnie raz.
• Jeśli liczby $a$ oraz $b$ są względnie pierwsze to ułamek ${\frac {a}{b}}$ występuje w drzewie dokładnie raz.
• W drzewie występują wszystkie liczby dodatnie wymierne, więc taką liczbę możemy opisać jako ścieżkę od korzenia drzewa do tej liczby. Jest to skończony ciąg symboli L oraz P (albo 0 1) np. liczbę ${\frac {3}{8}}$ zapisujemy jako LLPL.
• Każdą liczbę rzeczywistą dodatnią możemy zapisać jako ciąg symboli L oraz P tak, że początkowe fragmenty tego ciągu symbolizują liczby wymierne przybliżające tę liczbę.

Zobacz też

• ciąg Fareya
• okrąg Forda

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Stern-Brocot Tree, [w:] MathWorld, Wolfram Research [dostęp 2020-12-12]  (ang.).