스턴 브로콧 트리(Stern Brocot tree)

먼저, 모든 양의 분수를 나열하는 방법에 대해 알아봅시다. 다음 두 분수가 있습니다.

두 번째는 엄밀히 분수는 아니지만, 무한대를 나타내는 기약분수로 해석합시다.

매 반복마다, 모든 인접한 분수 $\dfrac{a}{b}$ 와 $\dfrac{c}{d}$ 사이에 mediant인 $\dfrac{a+c}{b+d}$를 삽입합니다. 반복에 따라 다음과 같이 나열됩니다.

이를 무한히 반복하면 모든 양의 분수를 나열하게 됩니다. 각 분수들은 오름차순으로 나타나며, 기약분수꼴이기 때문에 유일하게 등장합니다.

이 원리를 증명하기 전에 스턴 브로콧 트리가 어떻게 표현되는지 봅시다. 모든 분수는 트리 상에서 두 자식을 가집니다. 각 자식은 왼쪽에서 가장 가까운 조상과의 mediant, 오른쪽에서 가장 가까운 조상과의 mediant입니다.

스턴 브로콧 트리를 중위순회했을 때, 위에서 나열한 분수를 순서대로 만날 수 있습니다.

증명

이 일련의 분수들이 오름차순이고, 기약분수이며, 모든 분수를 포함한다는 사실을 증명해봅시다(건너뛰어도 됩니다).

오름차순 오름차순 증명은 간답합니다. 두 분수의 mediant는 항상 그 사이 값을 가지므로

다음이 성립합니다

두 부등식은 통분하면 쉽게 보일 수 있습니다. 처음 두 분수가 오름차순을 만족하기 때문에 mediant를 삽입을 반복하더라도 오름차순이 유지됩니다.

기약분수 어떤 인접한 분수 $\dfrac{a}{b}$ 와 $\dfrac{c}{d}$에 대해 다음을 보임으로써 기약분수성을 증명하겠습니다.

$ax+by=c$꼴의 디오판틴방정식은 $c \mid gcd(a,b)$일 때 해를 가지게 됩니다. 위의 식의 경우 $\gcd(a,b) = \gcd(c,d) = 1$를 의미하고, 이는 기약분수임을 보이는 것과 같습니다.

처음 두 분수는 자명하게 $bc - ad = 1$임이 자명합니다. 따라서 mediant들이 이 조건을 따르는지 보이면 됩니다.

두 인접한 분수가 $bc - ad = 1$를 만족한다고 가정했을 때, mediant를 추가한 후

다음과 같은 식이 성립해야 하며

이는 $bc - ad = 1$로 쉽게 보일 수 있습니다.

따라서 모든 분수에 대해 위의 식이 항상 성립하고, 모든 분수는 기약분수임을 증명할 수 있습니다.

모든 분수의 등장 각 분수가 스턴 브로콧 트리에서 어디에 위치하는지 알아봅시다. 왼쪽 서브트리의 분수들은 부모의 분수보다 작고, 오른쪽 서브트리의 분수들은 부모의 분수보다 큽니다. 따라서 어떤 분수를 찾으려면 루트로부터 내려가면서 찾으려는 분수보다 작으면 왼쪽, 크면 오른쪽으로 이동해야합니다.

임의의 양의 분수 $\dfrac{x}{y}$를 찾는다고 해봅시다. 이 분수는 분명히 $\dfrac{0}{1}$와 $\dfrac{1}{0}$사이에 존재합니다. 따라서 트리를 무한히 내려가도 안 나오는 경우를 빼면, 모두 트리 상에 존재합니다.

그렇다면 유한하게 내려갔을 때, $\dfrac{x}{y}$가 등장함을 보이겠습니다.

트리를 내려가는 동안 두 자식에 대해 다음이 성립합니다.

정수에서 $z \gt 0 \iff z \ge 1$임을 이용하여 식을 정리합니다.

첫 번째 식에 $c+d$, 두 번째 식에 $a+b$를 곱해 다음 식을 얻을 수 있습니다.

위에서 보였던 $bc-ad=1$을 적용합니다.

트리를 내려갈 때마다 $a,b,c,d$ 중 최소 하나는 값이 증가하기 때문에 $x+y$번 안에 해당 분수를 찾을 수 있습니다. 따라서 모든 분수는 이 트리 안에 존재하게 됩니다.

구현

스턴 브로콧 트리에서 어떤 서브트리를 만드려면 왼쪽 조상과 오른쪽 조상을 알아야 합니다. 처음 레벨에서 각 조상은 $\dfrac{0}{1}$과 $\dfrac{1}{0}$입니다. 각 레벨에서 mediant를 계산하면, 이 값은 왼쪽 서브트리의 오른쪽 조상, 오른쪽 서브트리의 왼쪽 조상이 됩니다.

다음은 스턴 브로콧 트리를 만드는 pseudo code입니다.

1
2
3
4
5
6
void build(int a = 0,int b = 1,int c = 1,int d = 0,int lv = 1){
    int m = a + c, n = b + d;
    // output the current fraction x/y at the current level in the tree
    build(a, b, m, n, lv + 1);
    build(m, n, c, d, lv + 1);
}

정의상 깊이가 무한하기 때문에 실제로 쓰이는 코드는 아니고, PS에서는 어떻게 쓰이는지 알아봅시다.

분수 탐색 알고리즘

스턴 브로콧 트리는 무한 완전 이진탐색 트리입니다. 따라서 이진 탐색 트리에서 원소를 찾는 방법을 그대로 적용할 수 있습니다. 현재 노드의 분수보다 찾으려는 분수가 작은 경우 왼쪽 자식으로, 큰 경우 오른쪽 자식으로 내려갑니다. 분수를 찾을 때까지 트리를 내려가면 됩니다.

분수 $\dfrac{x}{y}$를 찾기 위해 내려간 경로를 반환하는 코드입니다. 모든 분수에 대해 이 경로는 유일하게 존재합니다.

1
2
3
4
5
6
7
8
9
string find(int x, int y, int a = 0, int b = 1, int c = 1, int d = 0) {
    int m = a + c, n = b + d;
    if (x == m && y == n)
        return "";
    if (x*n < y*m)
        return 'L' + find(x, y, a, b, m, n);
    else
        return 'R' + find(x, y, m, n, c, d);
}