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
20
21

# 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

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 序列的定义，可以得到 的长度 公式为：

中间分数

对于 ，记中间分数为

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

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

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

对比上述表达式与

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

两个相邻中间分数的差为

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

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

证明

一种证法可以定量计算。根据连分数中的定理有

由于

因此

取倒数即证毕。

另一种证法使用中间分数。首先，两个相邻渐进分数之间的距离有

由于 本身介于两个相邻渐进分数之间，到其中一个渐进分数的距离 一定小于 。不等式右边即证毕。

对于不等式左边，由于对于固定的 ，两头的中间分数就是渐进分数，因此有位置关系

因此有距离关系

更换下标，不等式左边即证毕。