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