Нумерация двоичных деревьев

    Как пронумеровать все двоичные деревья? Как на КДПВ: “дерево” из одного листа будет первым, дерево из двух листов вторым, второе дерево с ещё одной веткой, исходящей из корня – третьим. А как найти номер произвольного дерева в такой схеме?

    КДПВ

    Прежде всего, мотороллер не мой. Описанная в статье схема была опубликована Кэролайн Колийн и Джованни Плацоттой (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). Подставив формулу для суммы арифметической прогрессии и сократив лишние единицы, мы приходим к следующей формуле:

    $N(k, j) = \dfrac{k(k - 1)}{2} + j + 1$



    Лишняя единица объясняется тем, что последовательность начинается не с (1, 1)-, а с (1)-дерева. Теперь номер любого произвольного дерева можно вычислить рекурсивным образом. Целевое дерево является по определению (k, j)-деревом, где k и j – поддеревья, растущие из его корня. k-дерево, в свою очередь, является (k1, k2)-деревом, где k1 и k2 – его поддеревья, и так далее до листьев, являющихся (1)-деревьями. Например:

    image

    Из такого способа вычисления номера следует и практический смысл всей затеи. Собственно номера – прикольная штука, но не очень понятно, что с ней дальше делать. Разве что полюбоваться тем, как огромное число заняло всю вашу оперативку и хочет ещё (на практике: разметка примерно десятка деревьев с 500 листьями не влазит в 64 Гб даже с использованием gmpy2). Они слишком сильно варьируют даже с небольшими изменениями деревьев; два дерева на картинке выше, например, отличаются только тем, что в правом отсутствует один лист в самом низу. Но каждому дереву соответствует ещё и вектор номеров всех его внутренних узлов. А на векторах уже можно определить метрику дистанций (например, евклидову) и использовать её для кластеризации топологий деревьев. В оригинальной статье деревья были филогенетические и удалось выявить различия в эволюции вируса гриппа в США и тропиках. В тропиках заболевание встречается круглый год, поэтому наблюдаются все промежуточные формы (масса (k, 1)-поддеревьев справа). А вот в Америке грипп – дело сезонное и преимущественно заносится из-за границы, поэтому таких деревьев практически нет.

    image

    В оригинальной статье ещё есть масса интересного: в частности, генерализация для не-двоичных деревьев, разные практически полезные варианты метрик дистанции, доказательство того, что это действительно метрики в строгом смысле, определение математических операций над деревьями и прочее такое. Если вдруг захочется поиграться, то авторский код на R и моя имплементация на питоне доступны на гитхабе. И то и другое, правда, рассчитано на филогенетические деревья.
    Share post

    Comments 22

      0
      Из такого способа вычисления номера следует и практический смысл всей затеи. Собственно номера – прикольная штука, но не очень понятно, что с ней дальше делать
      Если зная номер, можно «нарисовать» дерево, то вроде полезно. Вроде как покомпактнее (занимает меньше места), чем стандартный способ хранения дерева. Привели бы его для сравнения, там вроде ссылки на другие ноды используются?
        +1

        Не компактнее, по крайней мере для относительно больших деревьев. Стандартный формат записи деревьев в бионформатике примерно такой: (((А, B), (C, D)), E). Буквы — имена листьев, скобки объединяют соседние узлы. Могут быть ещё всякие приблуды для информации о внутренних узлах, но в простейшем случае так. Для данного дерева размер записи 21 символ, считая пробелы. Это, если я ничего не напутал, №8. Три бита. So far, so good. Но размер записи растёт примерно линейно от числа листьев, а номера во всяком случае не медленнее чисел Каталана, то есть сильно хуже, чем квадратично. На практике полный вектор номеров узлов для дерева после десятка листьев весит сильно больше, чем его запись в стандартной нотации.


        К тому же такое хранение будет некорректно. С точки зрения номеров ((A, B), C) = (A, (B,C)) = 3, а с точки зрения эволюционной информации в дереве это могут быть сильно разные штуки. Но это я со своей колокольни, конечно. Если кому-то надо хранить десятки тысяч топологий деревьев размером в десятки листьев, то может быть и выгода в хранении.

          0
          Тут двоичные деревья
          Их хранят в массивах
          Если именно топологию дерева кодировать (без payload в узлах), то достаточно по биту на каждый возможный узел/лист: 2^2^N (Где N — глубина дерева)
          Завершающие нули можно отбросить.
            0

            Не уверен, что представляю описываемый вами формат хранения. Можете чуть подробнее рассказать или там ссылку кинуть?

              +1
              Ошибся в расчетах.
              Просто в голове засели сбалансированные бинарные деревья
              Есть способ хранения бинарных деревьев в массиве:
              image
              Хранится как:
              image
              Для отображения только топологии этот массив можно представить в виде бинарного вектора. (1 — есть узел, 0 — нет узла)
              Но для разреженных деревьев будет дико неэффективно.

                0
                В общем случае у (несбалансированного) дерева тогда будет несколько представлений, верно? Но каждое представление будет соответствовать только одному дереву, так что почему бы и нет. Можно в принципе придумать алгоритм, считающий для произвольной топологии наиболее короткое представление.

                Эффективность будет сильно зависеть от сбалансированности дерева, в особенности количества (k, 1)-поддеревьев. Для каждого из них в правой части создаётся всегда столько же нулей, сколько узлов в k, минус 1. Любые (k,j)-поддеревья будут содержать в правой части меньше нулей, чем (k, 1), и тем меньше, чем k ближе к j. Размер представления получается где-то между 2n-1 и 2^n от числа листьев. Это без удаления завершающих нулей и ещё каких-нибудь оптимизаций.
                  0
                  В общем случае у (несбалансированного) дерева тогда будет несколько представлений

                  Это в смысле деревья:
                  и

                  равны?
                  Или я чего-то не понял?
                  Я как раз рассмотрел только простые оптимизации — удаление завершающих нулей и первой единицы.
                    0
                    Да, равны. Как и 0-1-2-3-4-5-7-8-11-12-13-14, например. Очевидно, оптимальная запись с точки зрения завершающих нулей вторая в вашем комментарии.
                      0

                      То есть, если я поменяю в корне правого и левого детей местами, то для вас дерево не изменится?

                        0
                        Ну, если мы хотим отбросить информацию о хиральности, то достаточно все деревья сортировать слева направо — это минимизирует запись, да.
                        Я бы сказал максимально минимизирует — достаточно запомнить номер разряда, где кончаются единицы и начинаются нули.

                        Но в большинстве случаев насколько я знаю, эта информация имеет значение…
                          0

                          Для большинства приложений (индексация данных, например) имеет. Но применительно к конкретно филогенетическим деревьям даже положение корня не всегда имеет значение, то есть деревья ((A, B), (C, D)) и ((C, (A, B)), D) часто считаются эквивалентными. Посмотрите, например, на КДПВ моего прошлого поста, там корня вообще нету. Зато очень важна информация, содержащаяся в листьях.

                            0

                            Больше похоже, что вы под деревом подразумеваете граф


                            A     C
                             >---<
                            B     D

                            И дополнительные промежуточные вершины не должны влиять на эквивалентность таких графов.

                              0
                              Да и нет. В филогенетической практике такой граф называется «неукоренённым деревом» и действительно довольно часто используется. Но внутренних вершин степенью меньше тройки там нет, так что их наличие или отсутствие таки важно.
            0
            По-моему, получилась хорошая учебная задачка для студентов-программистов. Тут вам и рекурсия, и деревья, и приложение к реальным проблемам из биологии.

            Скажем, на том же Haskell можно сделать совсем коротко.
            import Data.Tree
            
            n = Node "Node"
            
            a = n [n [n [n [n [], n []], n []], n []],
                   n [n [n [], n []], n [n [], n [n [n [], n []], n []]]]]
            b = n [n [n [n [n [], n []], n []], n []],
                   n [n [n [], n []], n [n [], n [n [], n []]]]]
            
            
            num :: Tree t -> Int
            num (Node _ [])       = 1
            num (Node _ [t1, t2]) = k * (k - 1) `div` 2 + j + 1
                where (k, j)   = if n1 > n2 then (n1, n2) else (n2, n1)
                      (n1, n2) = (num t1, num t2)
            

            Как и можно ожидать, 'num a' возвращает 84, 'num b' возвращает 21.
              0
              Я что-то не понял — каким образом нумерация деревьев помогает решить задачу их кластеризации? Как будто бы это две совершенно разных задачи, нет?
              Для кластеризации вроде как нужно задать метрику между деревьями, то есть определить функцию похожести деревьев, так? На рисунке два похожих дерева, но у одного номер 84, у другого — 21. Ну и как определить расстояние между ними?

              А на векторах уже можно определить метрику дистанций (например, евклидову)

              Как конкретно метрика определяется, поясните, пожалуйста.
                0
                На картинке в левом дереве 3 узла№2, 2 узла №3 и 2 узла №5, а в правом 3 узла№2, 2 узла №3 и 1 узел №5 (и сколько-то других узлов, но смотрим для примера на эти). За счёт этого топологии можно представить в виде векторов `(3, 2, 2)` и `(3, 2, 1)` и между ними уже считать евклидову дистанцию.
                  0
                  Да, спасибо, стало понятнее. Сверткой по номерам поддеревьев получаем вектор дерева. Но отражает ли норма разности таких векторов различие деревьев остаётся под вопросом ввиду нестабильности нумерации. Когда малое изменение дерева (добавление ветки) приводит к большим изменениям номеров веток.
                  Кажется, что можно найти более адекватные метрики.
                    0
                    На практике вроде как работает. Если никак не нормировать на размер поддерева, большую часть дистанции задаёт количество мелких поддеревьев (в пределах десятка листьев) тупо потому что их больше. Гляньте на последнюю картинку, там как раз наиболее значимые вынесены по бокам. И они как раз отражают интересующую авторов биологическую реальность гораздо больше, чем различия в номере корневого узла или его ближайших окрестностей.
                      0
                      Ну тогда можно было наверное еще проще поступить. В таких деревьях, насколько я понял, все узлы делятся на два типа — конечный и промежуточный (родительский). Это и есть базис для сравнения деревьев. Считаем количество тех и других узлов для каждого дерева и получаем вектор дерева. Возможно, такой метрики было бы достаточно.
                        0
                        Нельзя. Формулировка типа «X листьев, Y внутренних узлов» описывает не уникальное дерево, а огромный класс довольно разных деревьев. Не уверен даже, что для данного X может быть больше одного Y. А вектор номеров внутренних узлов однозначно описывает дерево.
                          0
                          Деревья сами по себе довольно простая структура (в смысле топологии). Почему бы не использовать для их сравнения такой инвариант графа, как его диаметр (максимальное расстояние между вершинами дерева) или чуть более сложный — суммарное значение расстояний?

                          Значение обоих инвариантов при заданном количестве узлов n известно для двух предельных деревьев — простой разомкнутой цепочки (максимальное) и для графа-звезды (минимальное). Для первого инварианта D(chain) = n-1, D(star) = 2. Для второго (сумма расстояний): Ds(chain) = (n-1)n(n+1)/6, а для звезды: Ds(star) = (n-1)^2.

                          Все остальные деревья (тут любые деревья, не только бинарные) расположены между этими предельными дистанциями. То есть по значению данных инвариантов можно судить о близости топологии деревьев — к чему ближе дерево: к цепочке (растянутое) или звезде (компактное). Во всяком случае метрика на основе расстояний выглядит прозрачной и обоснованной.
                            0
                            Нельзя по той же причине. Данное расстояние между двумя наиболее удалёнными узлами или сумма длин рёбер характерны для огромного класса очень разных (с биологической точки зрения) деревьев.

              Only users with full accounts can post comments. Log in, please.