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