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 树实际上是一个堆。也就是说，它是 的二叉树，它也是 和 的堆。

实现

构建实现

1
2
3
4
5
6
7

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

1
2
3
4
5
6
7

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)

查询实现

1
2
3
4
5
6
7
8

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

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)

例题

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

# 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)

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

# 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]

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

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 逼近定理是说，对于任意的一个无理数 ，均能找到无穷个有理数逼近它，满足不等式：