Drzewo Sterna-Brocota

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Drzewo Sterna-Brocotadrzewo binarne zawierające wszystkie dodatnie ułamki nieskracalne.

Konstrukcja[edytuj | edytuj kod]

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.

SternBrocotTree.svg

Własności[edytuj | edytuj kod]

  • 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ż[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]