Stern–Brocot 树与 Farey 序列

引入

本文介绍存储最简分数的数据结构以及其它相关概念。它们与 连分数 紧密相关，在算法竞赛中可以用于解决一系列数论问题，并可能作为某些题目的隐含背景出现。

Stern–Brocot 树

Stern–Brocot 树是一种维护分数的优雅的结构，包含所有不同的正有理数。这个结构分别由 Moritz Stern 在 1858 年和 Achille Brocot 在 1861 年独立发现。

构造

逐层构造

Stern–Borcot 树可以在迭代构造第 阶 Stern–Brocot 序列（Stern–Brocot sequence of order ）的过程中得到。第 阶 Stern–Brocot 序列由两个简单的分数组成：

此处的 严格意义上并不算是有理分数，可以理解为表示 的最简分数。

在第 阶 Stern–Brocot 序列相邻的两个分数 和 中间插入它们的中位分数（mediant）¹，就得到第 阶 Stern–Brocot 序列。尽管中位分数的定义本身允许分数的约分，但是在 Stern–Brocot 树的构造中，只需要直接将分子和分母分别相加即可，而不必担心约分的问题。由此，可以迭代地构造出所有阶的 Stern–Brocot 序列。前几次迭代的结果如下：

将每次迭代中新添加的分数连结成树状结构，就得到了 Stern–Brocot 树。如下图所示：

第 阶 Stern–Brocot 序列，不计左右端点，就是深度为 的 Stern–Brocot 树的中序遍历。

三元组构造

另一种等价的构造方式是以三元组

作为根节点，且在每个节点

后都分别添加

为左右子节点，就可以构造出整个 Stern–Brocot 树。Stern–Brocot 树的每个节点记录的三元组中，实际存储的分数是位于三元组中间的分数 ，而左右两个分数 和 是更早就出现过的分数。而且，考虑前一种构造就会发现，分数 正是通过插入 和 的中位分数得到的。

矩阵表示与 Stern–Brocot 数系

三元组构造意味着每个 Stern–Brocot 树上的节点都对应着一个矩阵

Stern–Brocot 树的根节点是单位矩阵 ，而向左子节点移动和向右子节点移动则分别对应将当前节点矩阵右乘以矩阵

每个节点实际对应的分数就是 。每个节点的矩阵 都可以写成一系列矩阵 和 的乘积，这也可以理解为是由 和 构成的字符串，表示了从根节点到达它的路径。将所有正的有理数唯一地表示为这样的字符串，这可以看作得到了正有理数的一种表示，故而也称作 Stern–Brocot 数系（Stern–Brocot number system）。

建树实现

建树算法只需要模拟上述过程即可。下面是对前 层的 Stern–Brocot 树做中序遍历的代码。

1
2
3
4
5
6
7
8

// In-Order Transversal of Stern-Brocot Tree till Layer N.
void build(int n, int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
  if (level > n) return;  // Only first n layers.
  int x = a + c, y = b + d;
  build(n, a, b, x, y, level + 1);
  std::cout << x << '/' << y << ' ';  // Output the current fraction.
  build(n, x, y, c, d, level + 1);
}

1
2
3
4
5
6
7
8

# In-Order Transversal of Stern-Brocot Tree till Layer N.
def build(n, a=0, b=1, c=1, d=0, level=1):
    if level > n:
        return
    x, y = a + c, b + d
    build(n, a, b, x, y, level + 1)
    print(f"{x}/{y}", end=" ")
    build(n, x, y, c, d, level + 1)

建树算法的复杂度是 的。

性质

接下来讨论 Stern–Brocot 树的性质。简而言之，Stern–Brocot 树是包含所有正的最简有理分数的 二叉搜索树，它也是分子和分母的 堆，也是分母和分子构成的二元组的 笛卡尔树。如果考虑前文的三元组构造中的左右端点形成的区间，则 Stern–Brocot 树也可以看作是 上的 线段树。这些陈述可以通过如下的三条基本性质导出：

单调性

在上面的构造中，每一层的分数都是单调递增的。为此只需要归纳证明。因为如果 ，那么必然有

这一点可以通过消去不等式的分母得出。归纳起点是 ，单调性也显然成立。

最简性

在上面的构造中，每个分数都是最简分数。为此同样需要归纳证明上面的构造中，每一层相邻的分数 和 都满足等式

根节点处是单位矩阵，这显然成立。向下移动时，乘以的矩阵 和 的行列式都是 ，根据 行列式 的性质可知，在下一层同样成立

对于归纳起点 和 这也是显然的。由此，根据 裴蜀定理，必然可知每个分数的分子和分母都是互素的，即所有分数都是最简分数。

完全性

最后，需要说明 Stern–Brocot 树包括了所有正的最简分数。因为前两条性质已经说明 Stern–Brocot 树是二叉搜索树，而任何正的最简分数 必然位于 和 之间，根据二叉搜索树上做搜索的方法，二叉搜索树上没有 的唯一可能性就是搜索过程无限长。这是不可能的。

假设现在已经知道

那么必然有

将两个不等式分别乘以 和 ，就能够得到

利用前面已经说明的等式 可知

每次搜索更深入一层的时候，等式右侧都严格地增加，而左侧保持不变，因此搜索必然在有限步内停止。

查找分数

在实际应用 Stern–Brocot 树的过程中，经常需要查询给定分数在 Stern–Brocot 树上的位置。

朴素算法

因为 Stern–Brocot 是二叉搜索树，只需要通过比较当前分数和要寻找的分数的大小关系，就可以确定从根节点到给定分数的路径。将路径上向左子节点移动和向右子节点移动分别记作 和 ，则每个路径就对应一个由 和 构成的字符串，这就是上文提到的有理数在 Stern–Brocot 数系中的表示。求得到达某个有理数的路径的过程就相当于求得该有理数在 Stern–Brocot 数系中的表示。

朴素的分数查找算法的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// Locate a given fraction in the Stern-Brocot tree.
std::string find(int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) {
  int m = a + c, n = b + d;
  if (x == m && y == n) return "";
  if (x * n < y * m) {
    return 'L' + find(x, y, a, b, m, n);
  } else {
    return 'R' + find(x, y, m, n, c, d);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Locate a given fraction in the Stern-Brocot tree.
def find(x, y, a=0, b=1, c=1, d=0):
    m = a + c
    n = b + d
    if x == m and y == n:
        return ""
    if x * n < y * m:
        return "L" + find(x, y, a, b, m, n)
    else:
        return "R" + find(x, y, m, n, c, d)

算法的复杂度是 的，因此在算法竞赛中并不实用。

在 Stern–Brocot 数系中，每个正的无理数都对应着唯一的无限长的字符串。可以使用同样的算法构造出这个字符串。这个无限长的字符串的每个前缀都对应着一个有理的最简分数。将这些最简分数排成一列，数列中的分数的分母是严格递增的，而数列的极限就是该无理数。因此，Stern-Brocot 树可以用于找到某个无理数的任意精度的有理逼近。但是，应当注意的是，这个有理数数列和无理数之间的差距并非严格递减的。对于有理逼近的严格理论，应当参考连分数页面的 丢番图逼近 一节。在实际应用 Stern-Brocot 树寻找某个实数在分母不超过某范围的最佳逼近时，最后应当注意比较左右区间端点到该实数的距离。

快速算法

查找分数的朴素算法效率并不高，但是经过简单的优化就可以得到 的快速查找算法。优化的关键是将连续的 和 合并处理。

如果要查找的分数 落入 和 之间，那么连续 次向右移动时，右侧边界保持不动，而左侧节点移动到 处；反过来，连续 次向左移动时，左侧边界保持不动，而右侧节点移动到 处。因此，可以直接通过 或 来确定向右和向左移动的次数。此处取严格不等号，是因为算法移动的是左右端点，而要寻找的分数是作为最后得到的端点的中位分数出现的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// Locate a given fraction in the Stern-Brocot tree.
auto find(int x, int y) {
  std::vector<std::pair<int, char>> res;
  int a = 0, b = 1, c = 1, d = 0;
  bool right = true;
  while (x != a + c || y != b + d) {
    if (right) {
      auto t = (b * x - a * y - 1) / (y * c - x * d);
      res.emplace_back(t, 'R');
      a += t * c;
      b += t * d;
    } else {
      auto t = (y * c - x * d - 1) / (b * x - a * y);
      res.emplace_back(t, 'L');
      c += t * a;
      d += t * b;
    }
    right ^= 1;
  }
  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

# Locate a given fraction in the Stern-Brocot tree.
def find(x, y):
    res = []
    a, b, c, d = 0, 1, 1, 0
    right = True
    while x != a + c or y != b + d:
        if right:
            t = (b * x - a * y - 1) // (y * c - x * d)
            res.append((t, "R"))
            a += t * c
            b += t * d
        else:
            t = (y * c - x * d - 1) // (b * x - a * y)
            res.append((t, "L"))
            c += t * a
            d += t * b
        right ^= 1
    return res

当前查找算法需要在分数 已知。如果目标分数未知，往往需要在每次向右或向左移动时，对移动次数进行倍增查找或者二分查找。此时，分数查找算法的复杂度是 。

基于连分数的算法

对于分数已知的情形，可以利用连分数给出更为简单的算法。不妨假设首组移动是向右的；如果不然，则设首组向右移动的次数为零。向右、向左交替移动端点，将每组移动后的端点位置排列如下：

其中，偶数组移动是向右的，故而记录的是左端点的位置；奇数组移动是向左的，故而记录的是右端点的位置。在这一列端点前面再添加两个端点

设第 组移动的次数为 ，那么根据上面得到的移动次数与端点位置之间的关系可知

根据连分数的 递推关系 就可以知道，端点

最后得到的连分数是

因此，在目标分数的末尾为一的 连分数表示 中，不计最后的一，前面的项就编码了 Stern–Brocot 树上自根节点到当前节点的路径。其中，偶数项（下标自 开始）是向右子节点的边，奇数项是向左子节点的边。

有理数的连分数表示可以通过辗转相除法求得，因此基于连分数表示的分数查找算法的复杂度是 的。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// Locate a given fraction in the Stern-Brocot tree.
auto find(int x, int y) {
  std::vector<std::pair<int, char>> res;
  bool right = true;
  while (y) {
    res.emplace_back(x / y, right ? 'R' : 'L');
    x %= y;
    std::swap(x, y);
    right ^= 1;
  }
  --res.back().first;
  return res;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

# Locate a given fraction in the Stern-Brocot tree.
def find(x, y):
    res = []
    right = True
    while y:
        res.append([x // y, ("R" if right else "L")])
        x, y = y, x % y
        right ^= 1
    res[-1][0] -= 1
    return res

利用连分数表示，可以简单地表达出某个节点的父节点和子节点。对于节点 ，它的父节点就是沿最后的移动方向少移动一步的节点：在 时，父节点是 ；否则，父节点是 。它的两个子节点则分别是 和 ；两个节点哪个是左子节点，哪个是右子节点，需要根据 的奇偶性判断。

Calkin–Wilf 树

另外一种更为简单的存储正有理分数的结构是 Calkin–Wilf 树。它通常如下所示：

树的根节点为 。然后，对于分数 所在的节点，其左右子节点分别为 和 。与 Stern–Brocot 树类似，它的每个分数都是最简分数，且包括全体正的最简分数各恰好一次。

与连分数的关系

与 Stern–Brocot 树不同，Calkin–Wilf 树不是二叉搜索树，因此不能用于二分查找有理数。

在 Calkin–Wilf 树中，当 时，分数 的父节点为 ；当 时，为 。对于第一种情形，自 出发，它是父节点的右子节点，可以一直通过父节点的右边向上移动，直到分子不再大于分母为止，此时节点存储的分数是 ，本组移动的次数是 ；对于第二种情形，它是父节点的左子节点，可以一直通过父节点的左边向上移动，直到分母不再大于分子为止，此时节点存储的分数是 ，本组移动的次数是 。

利用连分数的语言，设当前的节点存储的是某个连分数的余项 ，则沿父节点的右边向上移动 次，到达分数 ，随后沿父节点的左边移动 次，到达分数 。因此，从节点 开始向上到达根节点 的路径由连分数 编码：除去最后的 ，偶数项（下标自 开始）表示沿父节点的右边移动的次数，奇数项表示沿父节点的左边移动的次数。

对于分数 所在的节点，它的父节点有如下表示：

1. 当 时，它的父节点为 ；
2. 当 且 时，它的父节点为 ；
3. 当 且 时，它的父节点为 。

反过来，它的子节点则分别是 和 。对于第二个子节点的连分数表示，在 时，应当理解为 。

与 Stern–Brocot 树的关系

同样和连分数建立起联系，Stern–Brocot 树中路径上节点呈现的是渐近分数的递归关系，而 Calkin–Wilf 树中路径上节点呈现的是余项的递归关系。同一个分数的连分数表示是一定的，因此它在 Calkin–Wilf 树上到达根节点的路径的编码和 Stern–Brocot 树的根节点到它的路径的编码是完全一样的。但是，由于路径的方向相反，所以虽然 Stern–Brocot 树和 Calkin–Wilf 树同一层存储的分数是一样的，但是位置并不相同。

如果对两个树分别做 广度优先搜索 并依次对节点编号，根节点编号为 ，那么编号为 的节点的左右子节点分别是 和 。从编号的二进制表示来看，除去起始的 ，从高位至低位每个 均表示向右子节点移动，每个 均表示向左子节点移动。Calkin–Wilf 树上，连分数 表示的有理数所在节点的编号是

相应地，Stern–Brocot 树上，连分数 表示的有理数所在节点的编号是

删去初始的 ，余下的二进制位组成的编号，恰为同一层的顶点自左向右的编号（自 开始）。此处的推导说明，Stern–Brocot 树和 Calkin–Wilf 树中同一层的分数的排列互为位逆序置换（bit-reversal permutation），即将下标的二进制位（补齐起始的 ）反转得到的 上的置换。

正因如此，Stern–Brocot 树上的节点有时会按照对应的 Calkin–Wilf 树上的节点编号，由此得到的编号如下图所示：

这个编号可以递归地构造：根节点编号为 ，每次移动到左子节点时，就将编号首位的 替换成 ，而移动到右子节点时，就将编号首位的 替换成 。对该编号自右向左解读就可以得到自根节点到该节点的路径。

Stern 双原子序列

将 Calkin–Wilf 树中的所有分数按照广度优先搜索的编号排列，或将 Stern–Brocot 树中的所有分数按照上图所示的编号排列，就得到如下序列：

利用 Calkin–Wilf 树的构造过程，可以证明，该序列中相邻的两个分数，前一个的分母必然等于后一个的分子。将分子单独列出，就得到 Stern 双原子序列（Stern diatomic sequence，OEIS A002487），也称为 Stern–Brocot 序列（Stern–Brocot sequence）。上述序列的编号从 开始，并补充规定第 个数是 。

设 是 Stern 双原子序列中第 个数，那么，它满足如下递归关系：

递归起点是 和 。要求得 Stern 双原子序列中 的值，直接利用递归关系复杂度为 ，并不优秀。更好的做法是，将它视为 Calkin–Wilf 树上编号为 的分数的分子，利用上文描述的基于连分数的递归关系求解，复杂度为 。

Farey 序列

Farey 序列与 Stern–Brocot 树有着极其相似的特征。记 第 阶 Farey 序列（Farey sequence of order ）为 。它表示把分母小于等于 的所有位于 之间的最简分数按大小顺序排列形成的序列：

根据 Farey 序列的定义，它自然满足单调性、最简性和完全性。如上图所示， 相较于 新添加的分数总是 中相邻分数的中位分数。

上文中构建 Stern–Brocot 树的算法同样适用于构建 Farey 序列。因为 Stern–Brocot 树中包括所有最简分数，因此只要将边界条件修改为对分母的限制就可以得到构造 Farey 序列的代码。可以将第 阶 Farey 序列 看作是第 阶 Stern–Brocot 序列的子序列。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// Farey Sequence of Order N.
void build(int n, int a = 0, int b = 1, int c = 1, int d = 1,
           bool init = true) {
  int x = a + c, y = b + d;
  if (y > n) return;              // Only first n layers.
  if (init) std::cout << "0/1 ";  // Output 0/1;
  build(n, a, b, x, y, false);
  std::cout << x << '/' << y << ' ';  // Output the current fraction.
  build(n, x, y, c, d, false);
  if (init) std::cout << "1/1 ";  // Output 1/1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

# Farey Sequence of Order N.
def build(n, a=0, b=1, c=1, d=1, init=True):
    x, y = a + c, b + d
    if y > n:
        return
    if init:
        print("0/1", end=" ")
    build(n, a, b, x, y, False)
    print(f"{x}/{y}", end=" ")
    build(n, x, y, c, d, False)
    if init:
        print("1/1", end=" ")

直接构建 Farey 序列的复杂度是 的。

序列长度与分数查找

Farey 序列的长度可以递归求出。相较于 ，序列 多出来的分数的分母都是 ，而分子不超过 且与 互素，因此有：

此处的 是 欧拉函数。该式利用 线性筛 可以 求出，而利用 杜教筛 可以将复杂度降到 。

相较于直接求出序列的长度，更为常见的情景是需要求出序列 中某一分数 的编号。这相当于求值

要得到右式，应用了 莫比乌斯反演。线性筛和枚举因子结合，可以做到 预处理和 询问；杜教筛和 类欧几里得算法 结合，可以做到 预处理和 询问。

反过来，已知编号求解分数，需要对 之间的实数进行二分，或者在 Stern–Brocot 树上进行 二分。前者可能受到浮点数精度限制，对分数编号的询问次数为 ，其中 是精度范围；后者不受浮点数精度限制，但是对分数编号的询问次数为 。

Farey 邻项

如果分数 和 在某个 Farey 序列中相邻，就称它们为 Farey 邻项（Farey neighbors），也称为 Farey 对（Farey pair）。