Как пронумеровать все двоичные деревья? Как на КДПВ: “дерево” из одного листа будет первым, дерево из двух листов вторым, второе дерево с ещё одной веткой, исходящей из корня – третьим. А как найти номер произвольного дерева в такой схеме?
Прежде всего, мотороллер не мой. Описанная в статье схема была опубликована Кэролайн Колийн и Джованни Плацоттой (C. Colijn, G. Plazzotta) в Systematic Biology. Но так как большая часть хабра вряд ли читает английские биологические журналы, я решил, что стоит кусок оттуда перевести.
Предположим, что у нас уже есть некая схема нумерации, причём нумерация начинается с простейшего дерева, состоящего из одного листа. Назовём дерево, состоящее из двух поддеревьев с номерами k и j такими, что k >= j, (k, j)-деревом. Множество (k, j)-деревьев упорядочим лексикографически: (1), (1, 1), (2, 1), (2, 2), (3, 1), (3, 2)… Искомым номером как раз и будет место дерева в такой последовательности. То есть (1, 1)-дерево – это то же самое, что дерево № 2, (2, 1)-дерево – то же самое, что дерево № 3 и так далее. Можно проверить: на КДПВ так оно и есть.
Для перевода (k, j)-нотации в номера надо обратить внимание на то, что это по сути последовательность всех возможных пар натуральных чисел. Так как k >= j >= 1 по определению, то существует ровно k (k, j)-пар, от (k, 1) до (k, k), для любого k. Следовательно, (k, 1)-пара имеет номер (1+2+3+…+k-1) + 1, потому что ей предшествует (1 + 2 + 3 + … + k-1) пар. И, разумеется, номер (k, j)-пары больше номера (k, 1)-пары на (j-1). Подставив формулу для суммы арифметической прогрессии и сократив лишние единицы, мы приходим к следующей формуле:
Лишняя единица объясняется тем, что последовательность начинается не с (1, 1)-, а с (1)-дерева. Теперь номер любого произвольного дерева можно вычислить рекурсивным образом. Целевое дерево является по определению (k, j)-деревом, где k и j – поддеревья, растущие из его корня. k-дерево, в свою очередь, является (k1, k2)-деревом, где k1 и k2 – его поддеревья, и так далее до листьев, являющихся (1)-деревьями. Например:
Из такого способа вычисления номера следует и практический смысл всей затеи. Собственно номера – прикольная штука, но не очень понятно, что с ней дальше делать. Разве что полюбоваться тем, как огромное число заняло всю вашу оперативку и хочет ещё (на практике: разметка примерно десятка деревьев с 500 листьями не влазит в 64 Гб даже с использованием gmpy2). Они слишком сильно варьируют даже с небольшими изменениями деревьев; два дерева на картинке выше, например, отличаются только тем, что в правом отсутствует один лист в самом низу. Но каждому дереву соответствует ещё и вектор номеров всех его внутренних узлов. А на векторах уже можно определить метрику дистанций (например, евклидову) и использовать её для кластеризации топологий деревьев. В оригинальной статье деревья были филогенетические и удалось выявить различия в эволюции вируса гриппа в США и тропиках. В тропиках заболевание встречается круглый год, поэтому наблюдаются все промежуточные формы (масса (k, 1)-поддеревьев справа). А вот в Америке грипп – дело сезонное и преимущественно заносится из-за границы, поэтому таких деревьев практически нет.
В оригинальной статье ещё есть масса интересного: в частности, генерализация для не-двоичных деревьев, разные практически полезные варианты метрик дистанции, доказательство того, что это действительно метрики в строгом смысле, определение математических операций над деревьями и прочее такое. Если вдруг захочется поиграться, то авторский код на R и моя имплементация на питоне доступны на гитхабе. И то и другое, правда, рассчитано на филогенетические деревья.
Автор: synedra
