Stern–Brocot tree
E656695
The Stern–Brocot tree is an infinite binary tree that systematically lists all positive rational numbers in lowest terms exactly once, ordered by increasing value.
Statements (47)
| Predicate | Object |
|---|---|
| instanceOf |
infinite binary tree
ⓘ
mathematical object ⓘ |
| algorithmicUse |
implementing binary search on rationals
ⓘ
searching for rational approximations ⓘ |
| application |
Diophantine approximation
NERFINISHED
ⓘ
computing best rational approximations to real numbers ⓘ gear tooth design ⓘ |
| classification | enumeration scheme for rational numbers ⓘ |
| constructionDetail |
children of adjacent fractions a/b and c/d are formed using mediant (a+c)/(b+d)
ⓘ
each internal node has exactly two children ⓘ |
| constructionMethod | mediant operation ⓘ |
| discoveredBy | Moritz Stern NERFINISHED ⓘ |
| edgeRepresents | adjacency of fractions via mediant ⓘ |
| encoding |
paths correspond to continued fraction expansions
ⓘ
paths correspond to sequences of left and right moves ⓘ |
| field |
combinatorics
ⓘ
number theory ⓘ |
| independentlyDiscoveredBy | Achille Brocot NERFINISHED ⓘ |
| leftBoundary | 0/1 ⓘ |
| lists | positive rational numbers ⓘ |
| mathematicalCategory | object in discrete mathematics ⓘ |
| namedAfter |
Achille Brocot
NERFINISHED
ⓘ
Moritz Stern NERFINISHED ⓘ |
| nodeRepresents | reduced fraction ⓘ |
| ordering | increasing value ⓘ |
| originalMotivation | optimization of gear ratios ⓘ |
| property |
adjacent fractions a/b and c/d satisfy bc - ad = 1
ⓘ
each rational appears in lowest terms ⓘ every positive rational appears at a unique node ⓘ gives a complete enumeration of Q_{>0} ⓘ lists each positive rational number exactly once ⓘ no two distinct nodes represent the same rational number ⓘ tree is ordered by increasing fraction value from left to right ⓘ |
| relatedStructure |
Calkin–Wilf tree
NERFINISHED
ⓘ
Farey sequence NERFINISHED ⓘ continued fractions ⓘ |
| relationToContinuedFractions | each rational’s path encodes its continued fraction ⓘ |
| relationToFareySequences | adjacent fractions are Farey neighbors ⓘ |
| representation | often drawn between sentinel fractions 0/1 and 1/0 ⓘ |
| rightBoundary | 1/0 ⓘ |
| rootNode | 1/1 ⓘ |
| searchProperty | supports exact search for any positive rational via comparisons ⓘ |
| topology | countably infinite set of nodes ⓘ |
| usedIn |
computer arithmetic algorithms
ⓘ
data structures for rational search ⓘ |
| visualization | binary tree on the projective line over Q ⓘ |
| yearIntroduced | 1858 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.