Дерево Штерна Броко

Дерево Штерна — Броко — способ расположения всехнеотрицательных несократимых дробей в вершинах упорядоченногобесконечного двоичного дерева.
 В каждом узле дерева Штерна — Броко (иногда также называемогодеревом Фарея) стоит медианта m+mn+n дробейmn и mn, стоящих в ближайших к этому узлу левоми правом верхних узлах. Начальный кусок дерева Штерна — Броко в этомслучае выглядит так:
 Близким по построению к дереву Штерна — Броко является дерево Калкина— Уилфа, в котором дробь 11 является корнем, а все прочиеузлы заполняются по следующему алгоритму: каждая вершина mnимеет двух потомков: левого mm+n и правого m+nn.

История


 В книге Р. Грэхема, Д. Кнута, О. Паташника Конкретная математикаоткрытие «дерева Штерна — Броко» связывается с именами Морица Штерна(1858) и Ахилла Броко (1860). Однако аналогичное построение в форме«дерева Калкина-Уилфа» было известно ещё древнегреческим математикам.Оно описано под именем «порождения всех отношений из отношения равенствакак из матери и корня» в двух математических обзорах II в. н. э.,принадлежащих Никомаху Герасскому и Теону Смирнскому. Теон сообщает, чтоэта конструкция была известна Эратосфену Киренскому — знаменитомуучёному, жившему в III в. до н. э.

Свойства



  • Все дроби в деревьях Калкина — Уилфа и Штерна — Броко несократимы;
  • Каждая несократимая дробь появляется в дереве ровно один раз.

 Для дерева Калкина — Уилфа эти свойства легко доказываются, еслизаметить, что каждому шагу по дереву в направлении к корню соответствуетэлементарный шаг вычитания меньшего числа из большего в алгоритмеЕвклида для поиска наибольшего общего делителя.
 Для дерева Штерна — Броко доказательство основано на следующей лемме:если $p_1/q_1

Система счисления Штерна —Броко


 Можно воспользоваться символами L и R дляидентификации левой и правой ветви при продвижении вниз по дереву откорня, дроби 1/1, к некоторой определённой дроби. Тогда каждаяположительная дробь получает единственное представление в виде строкисостоящей из символов «R» и «L» (дроби 1/1соответствует пустая строка). Такое представление положительныхрациональных чисел назовём системой счисления Штерна — Броко. Кпримеру, обозначение LRRL соответствует дроби 5/7.