Stern-Brocot 树与 Farey 序列

连分数的树

有两种主要方法，可以将所有可能的连分数，合并为有用的树结构。

Stern-Brocot 树

定义

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

解释

Stern-Borcot 树从两个简单的分数开始：

这个 可能看得你有点懵逼。不过我们不讨论这方面的严谨性，你只需要把它当作 就行了。

每次在相邻的两个分数 中间插入一个分数 ，这样就完成了一次迭代，得到下一个序列。于是它就会变成这样

既然称它为 Stern-Brocot 树，那么它总得有一个树的样子。来一张图：

可以把第 层的序列当作是深度为 的 Stern-Brocot 树的中序遍历。

性质

接下来讨论 Stern-Brocot 树的性质。

单调性

在每一层的序列中，真分数是单调递增的。

略证：只需要在 的情况下证明

就行了。这个很容易，直接做一下代数变换即可

另一边同理可证。

最简性

序列中的分数（除了 ）都是最简分数。

略证：为证明最简性，我们首先证明对于序列中连续的两个分数 ：

显然，只需要在 的条件下证明 的情况成立即可。

后半部分同理。证明了这个，利用扩展欧几里德定理，如果上述方程有解，显然 。这样就证完了。

有了上面的证明，可以证明 。

有了这两个性质，就可以把它当成一棵平衡树来做了。建立和查询就向平衡树一样做就行了。

连分数表示与父子节点

递推 ，意味着连分数表示对树中 的路径进行编码。要查找 ，必须使 向右移动， 向左移动， 向右移动等等，直到 。

连分数节点 的父节点是沿最后使用的方向后退一步获得的分数。

换句话说，当 时，它是 ，而当 时，则是 。

因此， 的子节点是 和 。

索引

为 Stern Brocot 树编制索引。根顶点被分配了一个索引 。然后，对于顶点 ，通过将 的前导位从 更改为 来分配其左子节点的索引，对于右子节点，通过将前导位从 更改为 来分配索引：

在这种索引中，连分数表示规定了有理数的 游程长度编码（run-length encoding）。

对于 ，其索引为 ，其游程长度编码（考虑按升序排列的位）为 。

另一个例子是 ，其索引为 ，其游程编码实际上为 。

值得注意的是，Stern-Brocot 树实际上是一个堆。也就是说，它是 的二叉树，它也是 和 的堆。

实现

构建实现

=== "C++"

```cpp
void build(int a = 0, int b = 1, int c = 1, int d = 0, int level = 1) {
  int x = a + c, y = b + d;
  // ... output the current fraction x/y
  // at the current level in the tree
  build(a, b, x, y, level + 1);
  build(x, y, c, d, level + 1);
}
```

=== "Python"

```python
def build(a = 1, b = 1, c = 1, d = 0, level = 1):
    x = a + c; y = b + d
    # ... output the current fraction x/y
    # at the current level in the tree
    build(a, b, x, y, level + 1)
    build(x, y, c, d, level + 1)
```

查询实现

=== "C++"

```cpp
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);
}
```

=== "Python"

```python
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)
```

例题

# check if a < b assuming that a[-1] = b[-1] = infty and a != b
def less(a, b):
    a = [(-1)**i*a[i] for i in range(len(a))]
    b = [(-1)**i*b[i] for i in range(len(b))]
    return a < b

# [a0; a1, ..., ak] -> [a0, a1, ..., ak-1, 1]
def expand(a):
    if a: # empty a = inf
        a[-1] -= 1
        a.append(1)
    return a

# return a-eps, a+eps
def pm_eps(a):
    b = expand(a.copy())
    a.append(float('inf'))
    b.append(float('inf'))
    return (a, b) if less(a, b) else (b, a)

# finds lexicographically smallest (q, p)
# such that p0/q0 < p/q < p1/q1
def middle(p0, q0, p1, q1):
    a0 = pm_eps(fraction(p0, q0))[1]
    a1 = pm_eps(fraction(p1, q1))[0]
    a = []
    for i in range(min(len(a0), len(a1))):
        a.append(min(a0[i], a1[i]))
        if a0[i] != a1[i]:
            break
    a[-1] += 1
    p, q = convergents(a)
    return p[-1], q[-1]

    def solve():
    n = int(input())
    C = [0] * n
    J = [0] * n
    # p0/q0 < y/x < p1/q1
    p0, q0 = 0, 1
    p1, q1 = 1, 0
    fail = False
    for i in range(n):
        C[i], J[i] = map(int, input().split())
        if i > 0:
            A = C[i] - C[i-1]
            B = J[i] - J[i-1]
            if A <= 0 and B <= 0:
                fail = True
            elif B > 0 and A < 0: # y/x > (-A)/B if B > 0
                if (-A)*q0 > p0*B:
                    p0, q0 = -A, B
            elif B < 0 and A > 0: # y/x < A/(-B) if B < 0
                if A*q1 < p1*(-B):
                    p1, q1 = A, -B
    if p0*q1 >= p1*q0 or fail:
        return 'IMPOSSIBLE'

    p, q = middle(p0, q0, p1, q1)
    return str(q) + ' ' + str(p)

Calkin-Wilf 树

定义

在二叉树中组织连分数的一种更简单的方法是 Calkin-Wilf 树。

通常如下所示：

树的根节点为 。然后，对于数字为 的顶点，其子节点为 和 。

性质

与 Stern-Brocot 树不同，Calkin-Wilf 树不是二叉搜索树，因此不能用于执行有理二叉搜索。

在 Calkin-Wilf 树中，当 时，分数 的直接父节点为 ；当 时，为 。

在 Stern-Brocot 树中使用了收敛的递归。为了得出连分数和 Calkin-Wilf 树之间的联系，应该使用完整商（complete quotients）的递归。如果 ，则 。

另一方面，当 时，在 Calkin-Wilf 树中重复从 到它的父节点，那么将以 结尾。如果继续这样做，将以 ，然后 等结尾。由此可以推断：

1. 当 时，Calkin-Wilf 树中 的直接父节点为 。
2. 当 且 时，其直接父节点为 。
3. 当 且 时，其直接父节点为 。

相应地， 的子节点为

1. ，即 。
2. ，对于 ，它是 ；对于 ，则是 。

值得注意的是，如果以广度优先搜索顺序枚举 Calkin-Wilf 树的顶点（即，根有一个数字 ，而顶点 的子节点有相应的索引 和 ），Calkin-Welf 树中有理数的索引将与 Stern-Brocot 树中的索引相同。

因此，Stern-Brocot 树和 Calkin-Wilf 树的相同级别上的数字是相同的，但它们的排序通过 位反转排列（bit-reversal permutation）而不同。

Farey 序列

定义

Stern-Brocot 树与 Farey 序列有着极其相似的特征。第 个 Farey 序列记作 ，表示把分母小于等于 的所有最简真分数按大小顺序排列形成的序列。

显然，上述构建 Stern-Brocot 树的算法同样适用于构建 Farey 序列。因为 Stern-Brocot 树中的数是最简分数，因此在边界条件（分母）稍微修改一下就可以形成构造 Farey 序列的代码。可以认为 Farey 序列 是 Stern-Brocot 第 次迭代后得到的序列的子序列。

Farey 序列同样满足最简性和单调性，并且满足一个与 Stern-Brocot 树相似的性质：对于序列中连续的三个数 ，有 。这个可以轻松证明，不再赘述。

由 Farey 序列的定义，可以得到 的长度 公式为：

中间分数

对于 ，记中间分数为

中间分数还包含这样的分数：

这些中间分数介于 与 之间。

对于给定的 ，第 个中间分数 与最后一个中间分数 是渐进分数。

对比上述表达式与

可以得到 。因此，中间分数也是某个连分数展开的渐进分数，中间分数表达式的分子分母也一定互素。

两个相邻中间分数的差为

对于确定的 ，中间分数随着 的增加递增或递减。

定理：对实数 与渐进分数 ，有

在使用中这个定理经常放缩一下。由于 ，有

右半部分 无需计算更高阶的渐进分数，很常用，即下文 Dirichlet 逼近定理的连分数证法。

Dirichlet 逼近定理

Dirichlet 逼近定理是说，对于任意的一个无理数 ，均能找到无穷个有理数逼近它，满足不等式：

由于任一实数 到最近的整数距离不超过 ，显然存在整数 和 使得

Dirichlet 逼近定理将右侧优化到了 。等价的写法， 总有解。

当 是无理数的时候，可以让渐进分数的分母任意大， 任意小。

另外还有瓦伦定理：实数 连续两个渐进分数至少有一个满足 ，由瓦伦（Vahlen）在 1895 年证明。

另外还有伯雷尔定理：实数 连续两个渐进分数至少有一个满足 ，由伯雷尔（Borel）在 1903 年证明。

这个 是最优的，在无理数为例如黄金分割 等连分数展开自某位起均为 的时候取等。这些后续的定理也同样表明，在 Dirichlet 逼近定理中的小于等于号事实上也可以是小于号。

另外还有定理：实数 连分数展开无穷项不小于 ，则存在无穷多渐进分数满足 。这种条件的极端情形例如 。