Рационал сандардың Штерн-Броко ағашы

Ordered binary tree of rational numbers

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 search tree. The Stern–Brocot tree was introduced independently by and 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 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 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. The left subtree of the Stern–Brocot tree, containing the rational numbers in the range (0,1), is called the Farey tree.

Each vertex in the tree can be associated with a triple of fractions consisting of three fractions in the same row as the vertex, namely the fraction immediately to the left of the vertex, the fraction at the vertex itself, and the fraction immediately to the right of the vertex. (Refer to the figure above.) The left and right fractions do not correspond to vertices in the same row as the vertex, but rather to vertices in some preceding row. 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 second element of a triple will always be the mediant of the first and third elements. For example, the root is associated with and its left and right descendents are associated with and The tree is generated by the following rule: the left descendent of is and the right descendent is .

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 [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.