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$互质。