A Stern-Brokaw fa az összes nemnegatív irreducibilis tört elrendezésének módja egy rendezett végtelen bináris fa csúcsaiban .
A Stern-Brocko-fa (néha Farey-fának is nevezik) minden egyes csomópontján van a és a tört mediánja , amely a csomóponthoz legközelebb eső bal és jobb felső csomópontban áll. A Stern-Broco fa kezdeti darabja ebben az esetben így néz ki:
A Stern-Brocko fához közel áll a Calkin-Wilf fa , amelyben a tört a gyökér, és az összes többi csomópont a következő algoritmus szerint van kitöltve: minden csúcsnak két leszármazottja van: bal és jobb .
R. Graham , D. Knuth , O. Patashnik Concrete Mathematics című könyvében a "Stern-Broko fa" felfedezése Moritz Stern (1858) és Achilles Broko (1860) nevéhez fűződik. Azonban egy hasonló konstrukciót a "Calkin-Wilph fa" formájában még az ókori görög matematikusok is ismertek. A 2. század két matematikai felmérésében „minden reláció létrehozása az egyenlőség viszonyából, mint az anya és a gyökér” néven írja le. n. e., amely Gerasi Nikomákhoszhoz és Szmirnai Theonhoz tartozik . Theon beszámol arról, hogy ezt a tervet a cirénei Eratoszthenész ismerte , egy híres tudós, aki a Kr.e. 3. században élt. időszámításunk előtt e.
Egy Culkin-Wilf-fánál ezek a tulajdonságok könnyen bizonyíthatók, ha megjegyezzük, hogy a fában a gyökér felé vezető minden lépés egy elemi lépésnek felel meg, amikor az Euklidész algoritmusában egy kisebb számot kivonunk egy nagyobbból, hogy megtaláljuk a legnagyobb közös osztót.
A Stern-Brocko fa esetében a bizonyítás a következő lemmán alapul: ha a fa két szomszédos csomópontjában törtek vannak, akkor .
Az L és R szimbólumok segítségével azonosíthatja a bal és jobb oldali ágakat, miközben a fán lefelé halad a gyökértől, az 1/1-es törttől egy bizonyos tört felé. Ezután minden pozitív tört egyedi megjelenítést kap egy karakterlánc formájában, amely " R " és " L " karakterekből áll ( az 1/1-es tört egy üres karakterláncnak felel meg ). A pozitív racionális számok ilyen ábrázolását Stern-Broko számrendszernek nevezzük . Például az LRRL jelölés az 5/7 törtnek felel meg.