Stern–Brocot tree
In number theory, the Stern–Brocot tree is an infinite complete binary tree in which the vertices correspond one-for-one to the positive rational numbers, whose values are ordered from the left to the right as in a binary search tree.
The Stern–Brocot tree was introduced independently by Moritz Stern (1858) and Achille Brocot (1861).
Stern was a German number theorist; Brocot was a French clockmaker who used the Stern–Brocot tree to design systems of gears with a gear ratio close to some desired value by finding a ratio of smooth numbers near that value.
The parent-child relation between numbers in the Stern–Brocot tree may be defined in terms of simple continued fractions or mediants, and a path in the tree from the root to any other number q provides a sequence of approximations to q with smaller denominators than q.
Because the tree contains each positive rational number exactly once, a breadth first search of the tree provides a method of listing all positive rationals that is closely related to Farey sequences.
Each such fraction can be understood as labeling the region of the plane bounded by two infinite paths descending from the preceding vertex labeled by the same fraction.
The relationship between parents and descendants can also be understood in terms of continued fractions.
Every positive rational number q may be expressed as a continued fraction of the form
but using this equivalence to replace every continued fraction ending with a one by a shorter continued fraction shows that every rational number has a unique representation in which the last coefficient is greater than one.
Then, unless q = 1, the number q has a parent in the Stern–Brocot tree given by the continued fraction expression
Equivalently this parent is formed by decreasing the denominator in the innermost term of the continued fraction by 1, and contracting with the previous term if the fraction becomes 1/1.
For instance, the rational number 23/16 has the continued fraction representation
then one child is the number represented by the continued fraction
It is clear that for each finite continued fraction expression one can repeatedly move to its parent, and reach the root [1;] = 1/1 of the tree in finitely many steps (in a0 + ... + ak − 1 steps to be precise).
Therefore, every positive rational number appears exactly once in this tree.
The Stern–Brocot tree forms an infinite binary search tree with respect to the usual ordering of the rational numbers.
[1][2] The set of rational numbers descending from a node q is defined by the open interval (Lq, Hq) where Lq is the ancestor of q that is smaller than q and closest to it in the tree (or Lq = 0 if q has no smaller ancestor) while Hq is the ancestor of q that is larger than q and closest to it in the tree (or Hq = +∞ if q has no larger ancestor).
The path from the root 1 to a number q in the Stern–Brocot tree may be found by a binary search algorithm, which may be expressed in a simple way using mediants.
The binary search algorithm proceeds as follows: The sequence of values M computed by this search is exactly the sequence of values on the path from the root to q in the Stern–Brocot tree.
Each open interval (L, H) occurring at some step in the search is the interval (LM, HM) representing the descendants of the mediant M. The parent of q in the Stern–Brocot tree is the last mediant found that is not equal to q.
[3] If a real number x is approximated by any rational number a/b that is not in the sequence of mediants found by the algorithm above, then the sequence of mediants contains a closer approximation to x that has a denominator at most equal to b; in that sense, these mediants form the best rational approximations to x.
The Stern–Brocot tree may itself be defined directly in terms of mediants: the left child of any number q is the mediant of q with its closest smaller ancestor, and the right child of q is the mediant of q with its closest larger ancestor.
Again, using 7/5 as an example, its closest smaller ancestor is 4/3, so its left child is 4 + 7/3 + 5 = 11/8, and its closest larger ancestor is 3/2, so its right child is 7 + 3/5 + 2 = 10/7.
The Farey sequence of order n is the sorted sequence of fractions in the closed interval [0,1] that have denominator less than or equal to n. As in the binary search technique for generating the Stern–Brocot tree, the Farey sequences can be constructed using mediants: the Farey sequence of order n + 1 is formed from the Farey sequence of order n by computing the mediant of each two consecutive values in the Farey sequence of order n, keeping the subset of mediants that have denominator exactly equal to n + 1, and placing these mediants between the two values from which they were computed.
A similar process of mediant insertion, starting with a different pair of interval endpoints
may also be seen to describe the construction of the vertices at each level of the Stern–Brocot tree.
The Stern–Brocot sequence of order i consists of all values at the first i levels of the Stern–Brocot tree, together with the boundary values 0/1 and 1/0, in numerical order.
Thus the Stern–Brocot sequences differ from the Farey sequences in two ways: they eventually include all positive rationals, not just the rationals within the interval [0,1], and at the nth step all mediants are included, not only the ones with denominator equal to n. The Farey sequence of order n may be found by an inorder traversal of the left subtree of the Stern–Brocot tree, backtracking whenever a number with denominator greater than n is reached.
Along with the definitions in terms of continued fractions and mediants described above, the Stern–Brocot tree may also be defined as a Cartesian tree for the rational numbers, prioritized by their denominators.
It follows from the theory of Cartesian trees that the lowest common ancestor of any two numbers q and r in the Stern–Brocot tree is the rational number in the closed interval [q, r] that has the smallest denominator among all numbers in this interval.
