Stern–Brocot 树

Stern–Brocot 树
术语名称	Stern–Brocot 树
英语名称	Stern–Brocot tree
别名	SB树

法里树
术语名称	法里树
英语名称	Farey tree

Stern–Brocot树(Stern–Brocot tree)是一棵无限完全二叉树，树中的结点一一对应于全体正有理数，且值从左向右递增，因此也是一棵二叉搜索树。

定义

记以下一棵完全二叉树：

1. 根结点为三元组 [math]\displaystyle{ \left(\tfrac{0}{1}, \tfrac{1}{1}, \tfrac{1}{0}\right) }[/math] ；
2. 递归地，任意结点 [math]\displaystyle{ \left(\tfrac{a}{b}, \tfrac{c}{d}, \tfrac{e}{f}\right) }[/math] 的左子结点为 [math]\displaystyle{ \left(\tfrac{a}{b}, \tfrac{a+c}{b+d}, \tfrac{c}{d}\right) }[/math] ，右子结点为 [math]\displaystyle{ \left(\tfrac{c}{d}, \tfrac{c+e}{d+f}, \tfrac{e}{f}\right) }[/math] 。

称这样的二叉树为 Stern–Brocot 树(Stern–Brocot tree)。称任意结点 [math]\displaystyle{ \left(\tfrac{a}{b}, \tfrac{c}{d}, \tfrac{e}{f}\right) }[/math] 中的有理数 [math]\displaystyle{ \tfrac{c}{d} }[/math] 为这个结点的值。

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

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

性质

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

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

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

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

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

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

连分数
基本定义	连分数（简单、普通、广义；有限、无限）	连分数算法
部分结构	渐近分数	完全商
分类	有限连分数	循环连分数、无限不循环连分数
最佳有理逼近
用连分数逼近	渐近分数	半渐近分数
用中间分数逼近	Farey 数列	Stern–Brocot 树

琐事

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