Stern-Brokawův strom je způsob, jak uspořádat všechny nezáporné ireducibilní zlomky ve vrcholech uspořádaného nekonečného binárního stromu .
V každém uzlu Stern-Brockova stromu (někdy také nazývaného Fareyho strom ) je medián zlomků a , stojící v levém a pravém horním uzlu nejblíže k tomuto uzlu. Počáteční kus stromu Stern-Broco v tomto případě vypadá takto:
Konstrukčně blízký stromu Stern-Brocko je Calkin-Wilfův strom , ve kterém je zlomek kořenem a všechny ostatní uzly jsou vyplněny podle následujícího algoritmu: každý vrchol má dva potomky: left a right .
V knize Concrete Mathematics od R. Grahama , D. Knutha , O. Patashnika je objev „stromu Stern-Broko“ spojován se jmény Moritze Sterna (1858) a Achilla Broka (1860). Podobnou konstrukci v podobě „Calkin-Wilphova stromu“ však znali i starověcí řečtí matematici. Je popsána pod názvem „vytváření všech vztahů ze vztahu rovnosti jako od matky a kořene“ ve dvou matematických průzkumech 2. století. n. e. patřící Nikomachovi z Geras a Theonovi ze Smyrny . Theon uvádí, že tento design znal Eratosthenes z Kyrény , slavný vědec, který žil ve 3. století před naším letopočtem. před naším letopočtem E.
U Culkin-Wilfova stromu lze tyto vlastnosti snadno prokázat poznámkou, že každý krok ve stromu směrem ke kořeni odpovídá elementárnímu kroku odečtení menšího čísla od většího v Euklidově algoritmu, abychom našli největšího společného dělitele.
Pro Stern-Brockův strom je důkaz založen na následujícím lemmatu: jestliže jsou zlomky ve dvou sousedních uzlech stromu, pak .
K identifikaci levé a pravé větve můžete použít symboly L a R , když se pohybujete po stromu od kořene, zlomku 1/1, k nějakému konkrétnímu zlomku. Potom každý kladný zlomek dostane jedinečnou reprezentaci ve formě řetězce sestávajícího ze znaků " R " a " L " ( zlomek 1/1 odpovídá prázdnému řetězci ). Takové reprezentaci kladných racionálních čísel budeme říkat Sternův-Brokův číselný systém . Například zápis LRRL odpovídá zlomku 5/7.