Stern-Brocot tree - AbsoluteAstronomy.com

Number theory

Number theory is a branch of pure mathematics devoted primarily to the study of the integers. Number theorists study prime numbers as well...

, the Stern–Brocot tree is an infinite complete binary tree

Tree (graph theory)

In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...

in which the vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

correspond precisely

Bijection

A bijection is a function giving an exact pairing of the elements of two sets. A bijection from the set X to the set Y has an inverse function from Y to X. If X and Y are finite sets, then the existence of a bijection means they have the same number of elements...

to the positive rational number

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...

s, whose values are ordered from left to right as in a search tree

Search tree

In computer science, a search tree is a binary tree data structure in whose nodes data values are stored from some ordered set, in such a way that in-order traversal of the tree visits the nodes in ascending order of the stored values...

.

The Stern–Brocot tree was discovered independently by and . Stern was a German number theorist; Brocot was a French clockmaker

Clockmaker

A clockmaker is an artisan who makes and repairs clocks. Since almost all clocks are now factory-made, most modern clockmakers only repair clocks. Modern clockmakers may be employed by jewellers, antique shops, and places devoted strictly to repairing clocks and watches...

who used the Stern–Brocot tree to design systems of gears with a gear ratio

Gear ratio

The gear ratio of a gear train is the ratio of the angular velocity of the input gear to the angular velocity of the output gear, also known as the speed ratio of the gear train. The gear ratio can be computed directly from the numbers of teeth of the various gears that engage to form the gear...

close to some desired value by finding a ratio of smooth number

Smooth number

In number theory, a smooth number is an integer which factors completely into small prime numbers. The term seems to have been coined by Leonard Adleman. Smooth numbers are especially important in cryptography relying on factorization.-Definition:...

s near that value.

The root of the Stern–Brocot tree corresponds to the number 1. The parent-child relation between numbers in the Stern–Brocot tree may be defined in terms of continued fraction

Continued fraction

In mathematics, a continued fraction is an expression obtained through an iterative process of representing a number as the sum of its integer part and the reciprocal of another number, then writing this other number as the sum of its integer part and another reciprocal, and so on...

s or mediants, and a path in the tree from the root to any other number q provides a sequence of approximation

Diophantine approximation

In number theory, the field of Diophantine approximation, named after Diophantus of Alexandria, deals with the approximation of real numbers by rational numbers....

s 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 sequence

Farey sequence

In mathematics, the Farey sequence of order n is the sequence of completely reduced fractions between 0 and 1 which, when in lowest terms, have denominators less than or equal to n, arranged in order of increasing size....

A tree of continued fractions

Every positive rational number q may be expressed as a continued fraction of the form

where k and a₀ are non-negative integers, and each subsequent coefficient a_i is a positive integer. This representation is not unique because one has

for every sequence of coefficients a₀, ..., a_k−1.
Using this identity to rewrite any representation of the former form into the latter form, one may obtain that the final coefficient satisfies (unless , in which case one obtains a₀ ≥ 1); with this additional requirement the representation becomes unique. Then, unless , then number q has a parent in the Stern–Brocot tree given by the continued fraction expression

which in case one can rewrite as

.
For instance, the rational number has the continued fraction representation

so its parent in the Stern–Brocot tree is the number

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 .

Conversely each number q in the Stern–Brocot tree has exactly two children: if

then one child is the number represented by the continued fraction

while the other child is represented by the continued fraction

One of these children is less than q and this is the left child; the other is greater than q and it is the right child (in fact the former expression gives the left child if k is odd, and the right child if k is even).
For instance, the continued fraction representation of is [1;2,4] and its two children are [1;2,5] = (the right child) and [1;2,3,2] = (the left child).

It is clear that for each finite continued fraction expression one can repeatedly move to its parent, and reach the root [1;]= of the tree in finitely many steps (in steps to be precise). Therefore every positive rational number appears exactly once in this tree. Moreover all descendants of the left child of any number q are less than q, and all descendants of the right child of q are greater than q. The numbers at depth d in the tree are the numbers for which the sum of the continued fraction coefficients is .

Mediants and binary search

The Stern–Brocot tree forms an infinite binary search tree

Binary search tree

In computer science, a binary search tree , which may sometimes also be called an ordered or sorted binary tree, is a node-based binary tree data structurewhich has the following properties:...

with respect to the usual ordering of the rational numbers. The set of rational numbers descending from a node q is defined by the open interval (L_q,H_q) where L_q is the ancestor of q that is smaller than q and closest to it in the tree (or L_q = 0 if q has no smaller ancestor) while H_q is the ancestor of q that is larger than q and closest to it in the tree (or L_q = +∞ 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. Augment the non-negative rational numbers to including a value 1/0 (representing +∞) that is by definition greater than all other rationals. The binary search algorithm proceeds as follows:

Initialize two values L and H to 0/1 and 1/0, respectively.
Until q is found, repeat the following steps:
- Let L = a/b and H = c/d; compute the mediant M = (a + c)/(b + d).
- If M is less than q, then q is in the open interval (M,H); replace L by M and continue.
- If M is greater than q, then q is in the open interval (L,M); replace H by M and continue.
- In the remaining case, q = M; terminate the search algorithm.

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 (L_M,H_M)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.

This binary search procedure can be used to convert floating-point numbers into rational numbers. By stopping once the desired precision is reached, floating-point numbers can be approximated to arbitrary precision. 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. In this formula, q and its ancestor must both be taken in lowest terms, and if there is no smaller or larger ancestor then 0/1 or 1/0 should be used respectively. 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.

Relation to Farey sequences

The Farey sequence

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, 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 [0/1,1/0], 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 0 is the sequence [0/1,1/0], and the Stern–Brocot sequence of order i is the sequence formed by inserting a mediant between each consecutive pair of values in the Stern–Brocot sequence of order i − 1. 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.

Additional properties

are all the rationals at the same depth in the Stern–Brocot tree, then

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

Cartesian tree

In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric traversal of the tree returns the original sequence...

for the rational numbers, prioritized by their denominators. That is, it is the unique binary search tree of the rational numbers in which the parent of any vertex q has a smaller denominator than q (or, if q and its parent are both integers, in which the parent is smaller than q). It follows from the theory of Cartesian trees that the lowest common ancestor

Lowest common ancestor

The lowest common ancestor is a concept in graph theory and computer science. Let T be a rooted tree with n nodes. The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants .The LCA of v and w in T is the shared ancestor of v...

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.

Permuting the vertices on each level of the Stern–Brocot tree by a bit-reversal permutation produces a different tree, the Calkin–Wilf tree

Calkin–Wilf tree

In number theory, the Calkin–Wilf tree is a tree in which the vertices correspond 1-for-1 to the positive rational numbers. The tree is rooted at the number 1, and any rational number expressed in simplest terms as the fraction a/b has as its two children the numbers a/ and /b...

, in which the children of each number a/b are the two numbers a/(a + b) and (a + b)/b. Like the Stern–Brocot tree, the Calkin–Wilf tree contains each positive rational number exactly once, but it is not a binary search tree.

A tree of continued fractions

Mediants and binary search

Relation to Farey sequences

Additional properties

See also