SB树

这棵二叉树中包含了所有的非负有理数. 首先看它的构造:

左侧有一个点$0/1$, 右侧有一个点$1/0$. 在中间创建一个点$0+1/1+0=1/1$, 这就是SB树的根.

接下来, $1/1$的左儿子是它和$0/1$的分子、分母分别相加: $1+0/1+1=1/2$. 右儿子是与$1/0$做这个操作: $1+1/1+0=2/1$. 接下来的节点, 其左儿子为: 该节点与左兄弟的分子分母分别相加. 特别地, 没有左兄弟时 (即它在左链上) 认为左兄弟为$0/1$. 右儿子为: 该节点与右兄弟的分子分母分别相加. 特别地, 没有右兄弟时 (即它在右链上) 认为右兄弟为$1/0$.

首先证明:

SB树中每个数都满足: 分子分母互质, 即每个非负有理数至多出现一次.

证: 我们来证明: 对每个节点, 考虑其加入时刻, 假如此时构造它使用了$m/n$$m'/n'$. 那么必有$m'n-mn'=1$.

首先这对根节点成立.

现在假设对$m+m'/n+n'$的构造时刻, $m/n$$m'/n'$$m'n-mn'=1$, 现在只要证明

  1. $(m+m')n-m(n+n')=1$
  2. $m'(n+n')-(m+m')n=1$

而这两个等式都与原等式相同. 于是对每个$m/n$存在$a,b$使$am+bn=1$, 从而$m,n$互质.