Stern-Brocot 树与 Farey 序列

摘要

Stern-Brocot树是一种维护分数的优雅的数据结构。它分别由Moritz Stern在1858年和Achille Brocot 在1861年发现这个结构。

概述

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

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

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

既然我们叫这个数据结构 Stern-Brocot 树,那么它总得有一个树的样子对吧。来一张图:

pic

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

性质

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

单调性

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

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

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

另一边同理可证。

最简性

序列中的分数(除了 )都是最简分数。

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

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

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

有了上面的证明,我们可以证明

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

实现

构建实现

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

查询实现

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

Farey 序列

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

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

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

由Farey序列的定义,我们可以得到 的长度 公式为:


 上一篇
笛卡尔树 笛卡尔树
摘要 本文介绍一种不太常用,但是与大家熟知的平衡树与堆密切相关的数据结构——笛卡尔树。 笛卡尔树是一种二叉树,每一个结点由一个键值二元组 构成。要求 满足二叉搜索树的性质,而 满足堆的性质。一个有趣的事实是
2019.07.18 Sshwy
下一篇 
约瑟夫问题 约瑟夫问题
摘要 约瑟夫问题由来已久,而这个问题的解法也在不断改进,只是目前仍没有一个极其高效的算法(log以内)解决这个问题。 问题描述 n个人标号 逆时针站一圈,从 号开始,每一次从当前的人逆时针数 个,然后
2019.07.16
  目录