Drzewo Sterna-Brocota
Drzewo Sterna-Brocota – drzewo binarne zawierające wszystkie dodatnie ułamki nieskracalne.
Konstrukcja
Zaczynamy od – symbolizującego zero i symbolizującego nieskończoność. Następnie na kolejnych piętrach drzewa wpisujemy „pomiędzy” wartości oraz wartość – patrz ilustracja.
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/37/SternBrocotTree.svg/500px-SternBrocotTree.svg.png)
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 oraz są względnie pierwsze to ułamek 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ę 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ż
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.).