Введение

Упорядоченное двоичное дерево рациональных чисел

В теории чисел дерево Стерна — Брокота — это бесконечное полное двоичное дерево, в котором вершины соответствуют одно к одному положительным рациональным числам, значения которых упорядочены слева направо, как в дереве поиска. Дерево Стерна — Брокота было введено независимо друг от друга Стерном и Броко. Стерн был немецким теоретиком чисел, а Броко — французским часовщиком, который использовал дерево Стерна — Брокота для проектирования систем зубчатых передач с передаточным отношением, близким к желаемому значению, путем нахождения отношения гладких чисел вблизи этого значения. Корень дерева Стерна — Брокота соответствует числу 1. Связь родительского и дочернего элементов в дереве Стерна — Брокота может быть определена с использованием непрерывных дробей или медиантов, а путь в дереве от корня к любому другому числу q предоставляет последовательность приближений к q с меньшими знаменателями, чем у q. Поскольку дерево содержит каждое положительное рациональное число ровно один раз, поиск в ширину по дереву предоставляет метод перечисления всех положительных рациональных чисел, тесно связанный с последовательностями Фарея. Левое поддерево дерева Стерна — Брокота, содержащее рациональные числа в диапазоне (0, 1), называется деревом Фарея.

Правило генерации

Каждая вершина в дереве может быть связана с тройкой дробей, состоящей из трех дробей в той же строке, что и вершина, а именно дроби непосредственно слева от вершины, дроби на самой вершине и дроби непосредственно справа от вершины. (См. рисунок выше.) Левые и правые дроби не соответствуют вершинам в той же строке, что и вершина, а скорее вершинам в некоторой предыдущей строке. Каждую такую дробь можно понимать как обозначение области плоскости, ограниченной двумя бесконечными путями, сходящимися к предыдущей вершине, помеченной той же дробью. Второй элемент тройки всегда является медиантой первого и третьего элементов. Например, корень связан с , а его левый и правый потомки связаны с и . Дерево генерируется следующим правилом: левый потомок из – это , а правый потомок из – это .

Отношение к последовательностям Фарея

Последовательность Фарея порядка n — это упорядоченная последовательность дробей в замкнутом интервале [0, 1], имеющих знаменатель, не превышающий n. Подобно методу бинарного поиска, используемому для построения дерева Штерна — Броко, последовательности Фарея можно построить с помощью медиант: последовательность Фарея порядка n + 1 формируется из последовательности Фарея порядка n путем вычисления медианты для каждой пары последовательных значений в последовательности Фарея порядка n, сохранения подмножества медиант, знаменатель которых точно равен n + 1, и размещения этих медиант между двумя значениями, из которых они были вычислены. Аналогичный процесс вставки медиант, начинающийся с другой пары граничных точек интервала [0/1, 1/0], также может быть использован для описания построения вершин на каждом уровне дерева Штерна — Броко. Последовательность Штерна — Броко порядка 0 — это последовательность [0/1, 1/0], а последовательность Штерна — Броко порядка i — это последовательность, образованная вставкой медианты между каждой парой последовательных значений в последовательности Штерна — Броко порядка i − 1. Последовательность Штерна — Броко порядка i состоит из всех значений на первых i уровнях дерева Штерна — Броко, вместе с граничными значениями 0/1 и 1/0, расположенными в числовом порядке. Таким образом, последовательности Штерна — Броко отличаются от последовательностей Фарея двумя способами: они в конечном итоге включают все положительные рациональные числа, а не только рациональные числа в интервале [0, 1], и на n-м шаге включаются все медианты, а не только те, у которых знаменатель равен n. Последовательность Фарея порядка n можно получить, выполняя обход в порядке возрастания левого поддерева дерева Штерна — Броко, с возвратом при достижении числа со знаменателем, превышающим n.