查看“︁Stern–Brocot 树”︁的源代码

[[分类:连分数理论]]
[[分类:最佳有理逼近]]
[[分类:以 Stern 命名]]
[[分类:以 Brocot 命名]]
[[分类:以 Farey 命名]]
{{InfoBox
|name=Stern–Brocot 树
|eng_name=Stern–Brocot tree
|aliases=SB树
}}
{{InfoBox
|name=法里树
|eng_name=Farey tree
}}
'''Stern–Brocot树'''('''Stern–Brocot tree''')是一棵无限[[完全二叉树]]，树中的结点一一对应于全体正有理数，且值从左向右递增，因此也是一棵[[二叉搜索树]]。

== 定义 ==

记以下一棵完全二叉树：
# 根结点为三元组 <math>\left(\tfrac{0}{1}, \tfrac{1}{1}, \tfrac{1}{0}\right)</math> ；
# 递归地，任意结点 <math>\left(\tfrac{a}{b}, \tfrac{c}{d}, \tfrac{e}{f}\right)</math> 的左子结点为 <math>\left(\tfrac{a}{b}, \tfrac{a+c}{b+d}, \tfrac{c}{d}\right)</math> ，右子结点为 <math>\left(\tfrac{c}{d}, \tfrac{c+e}{d+f}, \tfrac{e}{f}\right)</math> 。
称这样的二叉树为 '''Stern–Brocot 树'''('''Stern–Brocot tree''')。称任意结点 <math>\left(\tfrac{a}{b}, \tfrac{c}{d}, \tfrac{e}{f}\right)</math> 中的有理数 <math>\tfrac{c}{d}</math> 为这个结点的值。

可以将每个结点看作区间及区间端点的[[中间分数]]，由于中间分数一定位于区间中，每一个结点的两个子结点都是在把这个区间分成左右两段。有时也可以认为 <math>\tfrac{0}{1}</math> 和 <math>\tfrac{1}{0}</math> 是树中“第 0 层”的结点，或者说由 <math>\tfrac{0}{1}</math> 和 <math>\tfrac{1}{0}</math> 生成。

特别地，由于这个和 [[Farey 数列]]逐层构造定义的方式相似，且在 0 到 1 之间就是每一阶的 Farey 数列，所以位于 0 到 1 之间的部分，也就是 Stern–Brocot 树的左子树，也被称为'''<ins>法里</ins>树'''('''Farey tree''')。也可以认为 Farey 树中 <math>\tfrac{0}{1}</math> 和 <math>\tfrac{1}{1}</math> 是树中“第 0 层”的结点，或者说由 <math>\tfrac{0}{1}</math> 和 <math>\tfrac{1}{1}</math> 生成。

== 性质 ==

单调性：由构造方式，每层的值都在上一层分出的区间内，总是能保证每个结点的值从左向右递增。

最简：每层构造出的新的分数都一定是最简分数。

[[连分数]]关系：对每个有理分数，存在等价连分数表示 <math>[a_0; a_1, a_2, \dots, a_{n-1}, 1]</math> 和 <math>[a_0; a_1, a_2, \dots, a_{n-1}+1]</math> ，其两个子结点一定分别是 <math>[a_0; a_1, a_2, \dots, a_{n-1}+2]</math> 和 <math>[a_0; a_1, a_2, \dots, a_{n-1}, 2]</math> （也就是两个表示的最后一个部分商分别加一），其具体左右侧取决于大小关系，进而取决于下标奇偶性。而对 1 以外的数，等价连分数表示 <math>[a_0; a_1, a_2, \dots, a_{n-1}, 1]</math> 和 <math>[a_0; a_1, a_2, \dots, a_{n-1}+1]</math> 的父节点也反过来是 <math>[a_0; a_1, a_2, \dots, a_{n-1}]</math> 。

由于任何一个正有理数都能表示成 <math>[a_0; a_1, a_2, \dots, a_n], a_0 \geq 0, a_i>0, i \geq 1</math> 形式的连分数，根据连分数表示关系可知，其一定出现在树中深度为 <math>a_0 + a_1 + \dots + a_n</math> 的结点上。

从连分数形式可以看出，进行[[深度优先搜索]]时，其中的一些项一定是所搜索目标的[[渐近分数]]，因此可以用于处理[[最佳有理逼近]]。

不考虑涉及 <math>\tfrac{1}{0}</math> 的情况下，进行[[深度优先搜索]]时，相当于从数轴上这一点画一条垂线，这条线从上到下依次恰好只与这些数对应的 [[Ford 圆]]相交。


{{连分数理论}}

== 琐事 ==

最初由钟表匠 Brocot 用此法，将含大素数传动比的齿轮组近似成数字较小的齿数比的乘积，因此得名。