数据结构

SB树

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

左侧有一个点0/10/1，右侧有一个点1/01/0。在中间创建一个点0+1/1+0=1/10+1/1+0=1/1，这就是SB树的根。

接下来，1/11/1的左儿子是它和0/10/1的分子、分母分别相加：1+0/1+1=1/21+0/1+1=1/2。右儿子是与1/01/0做这个操作：1+1/1+0=2/11+1/1+0=2/1。接下来的节点，其左儿子为：该节点与左兄弟的分子分母分别相加。特别地，没有左兄弟时（即它在左链上）认为左兄弟为0/10/1。右儿子为：该节点与右兄弟的分子分母分别相加。特别地，没有右兄弟时（即它在右链上）认为右兄弟为1/01/0。

首先证明：

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

证：我们来证明：对每个节点，考虑其加入时刻，假如此时构造它使用了m/nm/n和m′/n′m'/n'。那么必有m′n−mn′=1m'n-mn'=1。

首先这对根节点成立。

现在假设对m+m′/n+n′m+m'/n+n'的构造时刻，m/nm/n和m′/n′m'/n'有m′n−mn′=1m'n-mn'=1，现在只要证明

  1. (m+m′)n−m(n+n′)=1(m+m')n-m(n+n')=1
  2. m′(n+n′)−(m+m′)n=1m'(n+n')-(m+m')n=1

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