Дерево Штерна — Броко — способ расположения всех неотрицательных несократимых дробей в вершинах упорядоченного бесконечного двоичного дерева.
В каждом узле дерева Штерна — Броко (иногда также называемого деревом Фарея) стоит медианта дробей и , стоящих в ближайших к этому узлу левом и правом верхних узлах. Начальный кусок дерева Штерна — Броко в этом случае выглядит так:
Близким по построению к дереву Штерна — Броко является дерево Калкина — Уилфа, в котором дробь является корнем, а все прочие узлы заполняются по следующему алгоритму: каждая вершина имеет двух потомков: левого и правого .
История
В книге Р. Грэма, Д. Кнута, О. Паташника «Конкретная математика» открытие «дерева Штерна — Броко» связывается с именами Морица Штерна (1858) и Ахилла Броко (1860). Однако аналогичное построение в форме «дерева Калкина — Уилфа» было известно ещё древнегреческим математикам. Оно описано под именем «порождения всех отношений из отношения равенства как из матери и корня» в двух математических обзорах II в. н. э., принадлежащих Никомаху Герасскому и Теону Смирнскому. Теон сообщает, что эта конструкция была известна Эратосфену Киренскому — знаменитому учёному, жившему в III в. до н. э.
Свойства
Все дроби в деревьях Калкина — Уилфа и Штерна — Броко несократимы. Каждая несократимая дробь появляется в дереве ровно один раз.
Для дерева Калкина — Уилфа эти свойства легко доказываются, если заметить, что каждому шагу по дереву в направлении к корню соответствует элементарный шаг вычитания меньшего числа из большего в алгоритме Евклида для поиска наибольшего общего делителя.
Для дерева Штерна — Броко доказательство основано на следующей лемме: если — дроби в двух соседних узлах дерева, то .
Система счисления Штерна — Броко Можно воспользоваться символами L и R для идентификации левой и правой ветви при продвижении вниз по дереву от корня, дроби 1/1, к некоторой определённой дроби. Тогда каждая положительная дробь получает единственное представление в виде строки состоящей из символов «R» и «L» (дроби 1/1 соответствует пустая строка). Такое представление положительных рациональных чисел назовём системой счисления Штерна — Броко. К примеру, обозначение LRRL соответствует дроби 5/7.
См. также Ряд Фарея Цепная дробь Подходящая дробь Система счисления Алгоритм Евклида Дерево Калкина — Уилфа Окружность Форда
Литература . .
Ссылки The Stern — Brocot or Farey Tree
Онлайн-демонстратор приближения рациональных чисел при помощи дерева Штерна — Броко
Категория:Алгоритмы Категория:Числа Категория:Дроби Категория:Непрерывная дробь