Вывести дерево с рекурсией

В принципе, задача очень близка к первой решенной нами. Только вместо позиции двоичная «цифра» означает отсутствие или наличие соответствующего элемента в результирующем наборе:

Поскольку двоичная арифметика представлена в компьютерах гораздо эффективнее, мы можем воспользоваться функциями работы с битовыми строками:

Иерархия — без рекурсии!

Теперь, вооруженные всеми приведенными выше алгоритмами, попробуем найти решение нашей задачи сначала в общем виде, а затем разберем один из типичных частных случаев.

Пути-дороги

Для начала воспользуемся тем фактом, что в качестве элементов пути, который идентифицирует конкретную запись, можно использовать уникальные ключи промежуточных записей — в нашем случае это id .

Но сортировать по такому пути, конечно, будет некорректно — поэтому для дальнейшей сортировки превратим id записей в соответствующее значение data , которое использовали в первом варианте.

Дано: газовая плита, чайник. Задача: вскипятить воду.
Физик: Зажечь плиту, наполнить чайник водой и поставить на плиту, ждать.
Математик: Аналогично.

Дано: зажженная газовая плита, наполненный водой чайник. Задача: вскипятить воду.
Физик: Поставить чайник на плиту, ждать.
Математик: Выливаем воду из чайника на плиту. Огонь погас, чайник пуст, задача сведена к предыдущей.
© Народный анекдот

Но как найти путь до каждого из элементов без рекурсии? Вот здесь нам и пригодятся алгоритмы выше.

Корректный путь от корня до конкретного элемента обладает следующими свойствами:

• Правило #1: начинается и заканчивается нужными нам элементами
  path[1] = root AND path[array_length(path, 1)] = id
• Правило #2: предок каждого элемента, кроме корневого, так же присутствует в наборе
  pid = ANY(path) OR pid = root
• Правило #3: из всех таких наборов искомый — самой маленькой длины
  Иначе для id=3 наборы <1,2,3>и <1,2,3,4>окажутся равноподходящими, поскольку предок id=4 (pid=1) тоже присутствует.
• Правило #4: предок каждого элемента стоит ровно в предыдущей позиции
  pid = path[pos — 1]

Итак, намечаем план действий:

• генерируем все подмножества элементов, исключая root и id , формируя «тело» пути по правилу #1
• проверяем выполнение правила #2
• выбираем, согласно правилу #3, самый короткий набор
• генерируем все перестановки его элементов
• проверяем выполнение правила #4
• что осталось — искомый «путь»

А попроще — можно.

Можно и попроще, если заранее известно, что порядок «детей» внутри одного «родителя» определяется некоторым сквозным ключом. Например, это может быть некоторый монотонно возрастающий timestamp сообщений в ветке форума или, как в нашем случае, первичный ключ типа serial ( id ).

В таком случае, мы уже точно знаем порядок следования идентификаторов записей в нужном нам пути — он совпадает с общей сортировкой по этому ключу. И нам надо только выкинуть лишние id из списка всех предстоящих:

Понятно, что производительность таких «экспоненциальных» решений не особо велика и применять «в бою» надо с большой осторожностью, но как гимнастика для ума — вполне.

Источник

Практика метапрограммирования на C++: бинарное дерево поиска на этапе компиляции

Создатели шаблонов в C++ заложили основу целого направления для исследований и разработки: оказалось, что язык шаблонов C++ обладает полнотой по Тьюрингу, то есть метапрограммы (программы, предназначенные для работы на этапе компиляции) C++ в состоянии вычислить всё вычислимое. На практике мощь шаблонов чаще всего применяется при описании обобщенных структур данных и алгоритмов: STL (Standard Template Library) тому живой пример.

Однако, с приходом C++11 с его variadic -шаблонами, библиотекой type_traits , кортежами и constexpr ‘ами метапрограммирование стало более удобным и наглядным, открыв дорогу к реализации многих идей, которые раньше можно было воплотить только с помощью расширений конкретного компилятора или сложных многоэтажных макросов.

В данной статье будет разработана реализация бинарного дерева поиска времени компиляции: структуры данных, являющейся логическим «расширением» кортежа. Мы воплотим бинарное дерево в виде шаблона и попрактикуемся в метапрограммировании: переносе рекурсивных и не только алгоритмов на язык шаблонов C++.

Содержание

Немного теории

Для начала вспомним некоторые определения и понятия о структурах данных и алгоритмах. Можно пропустить этот раздел и сразу перейти к деталям реализации, если читатель знаком с основами теории графов и/или представляет, что такое бинарные деревья и как их можно готовить.

Свободное дерево (дерево без выделенного корня) или просто дерево — ациклический неориентированный граф.

Дерево с корнем — свободное дерево, в котором выделена одна вершина, называемая корнем (root).

Узлы (nodes) — вершины дерева с корнем.

Родительский узел или родитель узла X — последний узел, предшествующий X на пути от корня R к этому узлу X. В таком случае узел X называется дочерним к описанному родительскому узлу Y. Корень дерева не имеет родителя.

Лист — узел, у которого нет дочерних узлов.

Внутренний узел — узел, не являющийся листом.

Степень узла X — количество дочерних узлов этого узла X.

Глубина узла X — длина пути от корня R к этому узлу X.

Высота узла (height) — длина самого длинного простого (без возвратов) нисходящего пути от узла к листу.

Высота дерева — высота корня этого дерева.

Упорядоченное дерево — дерево с корнем, в котором дочерние узлы каждого узла упорядочены (т.е. задано отображение множества дочерних узлов на множество натуральных чисел от 1 до k, где k — общее количество дочерних узлов этого узла). Простыми словами, каждому дочернему узлу присвоено имя: «первый», «второй», . «k-тый».

Бинарное дерево (binary tree) — (рекурсивно) либо пустое множество (не содержит узлов), либо состоит из трёх непересекающихся множеств узлов: корневой узел, бинарное дерево, называемое левым поддеревом, и бинарное дерево, называемое правым поддеревом. Таким образом, бинарное дерево — это упорядоченное дерево, у которого каждый узел имеет степень не более 2 и имеет «левый» и/или/либо «правый» дочерние узлы.

Полностью бинарное дерево (full binary tree) — бинарное дерево, у которого каждый узел либо лист, либо имеет степень два. Полностью бинарное дерево можно получить из бинарного добавлением фиктивных дочерних листов каждому узлу степени 1.

Бинарное дерево поиска — связанная структура данных, реализованная посредством бинарного дерева, каждый узел которого может быть представлен объектом, содержащим ключ (key) и сопутствующие данные, ссылки на левое и правое поддеревья и ссылку на родительский узел. Ключи бинарного дерева поиска удовлетворяют свойству бинарного дерева поиска:

если X — узел, и узел Y находится в левом поддереве X, то Y.key ≤ X.key. Если узел Y находится в правом поддереве X, то X.key ≤ Y.key.

Разумеется, ни о каких «конкатенации» и «добавлении» типов в «контейнеры типов» речи не идёт. Это общая и важная особенность мира времени компиляции: определенный тип (класс) никаким образом модифицировать уже невозможно, но возможно определить новый (или среди ранее определенных выбрать существующий) тип, имеющий необходимые нам свойства.

Стандарт C++11 вводит заголовочный файл type_traits (как часть библиотеки поддержки типов), содержащий коллекцию полезных метафункций. Все они являются шаблонами структур, и после инстанцирования определяют локально некий тип type или числовую константу value (или ничего, как в случае отключения перегрузки с использованием std::enable_if ). Мы будем придерживаться тех же принципов проектирования метафункций.

Первая функция принимает в качестве аргументов шаблона два кортежа, вторая — кортеж и тип, который необходимо добавить в кортеж. Подстановка в качестве аргументов неподходящих типов (например, при попытке сделать конкатенацию int и float ) — операция бессмысленная, поэтому базовый шаблон этих структур не определяется (это предотвратит его инстанцирование для произвольных типов), а вся полезная работа делается в частичных специализациях:

Примерный перевод на человеческий язык специализации tuple_concat :

Если в качестве аргументов шаблона выступают два класса, которые в свою очередь являются результатами инстанцирования одного и того же шаблона класса ( T ) с переменным числом аргументов, и они были инстанцированы с parameter pack’ами Alist и Blist , то определить локально псевдоним type как инстанцированую версию того же шаблона класса T с конкатенированным списком аргументов, т.е. T .

Звучит зловеще, но на практике всё проще, чем кажется: при попытке вызвать tuple_concat с двумя кортежами одного вида (например, с двумя std::tuple ), внутри структуры определится тип того же кортежа со «сшитым» списком аргументов входных кортежей. Иные попытки инстанцирования просто не скомпилируются (компилятор не сможет вывести типы для определенной выше частичной специализации, а инстанцирование общего шаблона окажется невозможным ввиду отсутствия его тела). Пример:

В свете вышесказанного рассмотрение специализации tuple_push не должно составить большого труда. Дополнительно, для удобства определим соответственные псевдонимы шаблонов:

Эта удобная возможность появилась в языке в C++11 стандарте: она, например, позволяет для доступа к type вместо заковыристого typename tuple_concat ::type писать просто tuple_concat_t .

Последние приготовления: не для дела, а для души дебага научимся превращать целые числа в типы: в узлах дерева надо что-то хранить, а что может быть проще и удобнее для отладки, чем хранить в них обычные числа? Но так как дерево у нас не простое, а с типами (и времени компиляции), то и числа должны быть непростыми. На самом деле, реализация крайне проста и известна:

Смысл у обоих определений один: инстанцирование шаблона с различными численными аргументами будет приводить к определению различных типов: num_t , num_t , num_t и т.д. Не более чем для удобства наделим эту структуру статическим числовым значением value , что позволит нам явно получать назад число из аргумента шаблона (посредством доступа some_num_type::value ) без прибегания к выводу типа.

Бинарное дерево поиска

Рекурсивное определение бинарного дерева поиска оказывается удобным для непосредственного воплощения в виде шаблона. Упрощенное определение

можно перефразировать как «дерево — ЭТО пустое множество ИЛИ множество из трёх элементов: дерево (т.н. левое поддерево), данные, дерево (т.н. правое поддерево)».

Помимо этого, как уже упоминалось, бинарное дерево поиска требует задания отношения порядка на множестве значений, хранящихся в узлах дерева (мы должны уметь как-то сравнивать и упорядочивать узлы, т.е. иметь операцию «меньше»). Каноничным подходом является разбиение данных узла на ключ и значение (ключи сравниваем, значения просто храним), но в нашей реализации в целях упрощения структуры без ограничения общности будем считать данные узла единым типом, для задания же отношения порядка воспользуемся специальным типом Comp (comparator, поговорим о нём далее).

Несмотря на то, что отношение порядка всё-таки задано на множестве хранимых в узлах типов, удобно приписать его самому дереву и хранить как часть типа этого дерева: при вызове метафункций поиска, вставки и обхода непустого дерева нет необходимости в дополнительном указании компаратора.

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

Сама по себе ситуация не критичная и имеет обходное решение в виде разделения объявлений и определений типов:

Примечание: экспериментальным путём обнаружено, что такие структуры компилируются и инстанцируются современными gcc и clang, тем не менее, я пока не проверял строгое соответствие стандарту объявлений таких необычных шаблонов.

Это не единственный способ реализации и представления дерева (например, можно хранить узлы в кортеже и проводить их индексацию), однако такое описание более наглядно и удобно для непосредственного применения алгоритмов работы с деревом.

Отношение порядка

Структура Comp должна содержать метафункции сравнения типов (т.е. шаблоны операций «меньше» и «равно»). Напишем пример такого сравнителя, основанного на sizeof ‘ах типов (возможно, единственная числовая характеристика, определенная для всех полных типов):

Здесь всё должно быть прозрачно: lt — метафункция «меньше» для типов, eq — метафункция «равно». Использован подход, показанный ранее для определения типов чисел: наследование от std::integral_constant наделит инстанцированные lt и eq статическими булевыми значениями value .

На практике конкретные деревья конкретных типов должны снабжаться сравнителем, специфичным для данной задачи. Например, напишем сравнитель для описанного ранее класса «числовых типов»:

Такой компаратор, вообще говоря, универсален и умеет сравнивать любые типы, содержащие статическое значение value .

Теперь у нас есть всё для того, чтобы явно, «руками», определить первое дерево типов:

Примечание: Здесь и далее в примерах по-умолчанию подразумевается сравнитель num_comp , явное указание его в списке аргументов шаблонов опускается. Вообще, после разработки операции insert нам не придётся строить деревья таким образом (явным определением).

Описанное дерево изображено на рисунке.

Как нам убедиться, что определенный нами класс точно описывает то, что мы задумали?

Эта отдельная интересная тема для дискуссии и исследования — отладка метапрограмм. У нас нет ни стека вызовов, ни переменных, ни, чёрт возьми, банального printf/std::cout . Есть техники, позволяющие печатать внутри сообщений об ошибках компилятора удобочитаемые выведенные типы, и, в принципе, это достаточно полезная возможность проверки сгенерированных структур (например, после модификации дерева).

Не будем здесь касаться вопроса многомегабайтных сообщений об ошибках просто в случае некорректной программы: после некоторой практики это перестаёт быть проблемой, так как в подавляющем большинстве случаев лишь первая ошибка инстанцироания ведёт к каскаду дальнейших ошибок: отладка в таком случае ведётся «методом последовательных приближений».

Но, как бы парадоксально это ни звучало, что делать, если программа скомпилировалось успешно? Здесь уже автор более свободен в выборе методов отладки. Тип результата метафункций наподобие определенных в type_traits можно просто печатать в виде typeid(t).name() (начиная с C++11 можно легально подсматривать в RTTI). Простые структуры данных можно выводить на экран специальными метафункциями с хвостовой рекурсией, для сложных придётся городить «принтеры», сопоставимые по сложности с операциями над самой структурой.

Библиотека деревьев содержит такой принтер и примеры его использования, читатель может ознакомиться с ними по ссылке на github в конце статьи. Вот, например, напечатанное дерево из примера выше:

Высота

Посмотрим на рекурсивную функцию вычисления высоты бинарного дерева:

Она прекрасна. Просто берём и переносим эту функцию на C++:

Примечание: мы сознательно пошли на небольшое упрощение, из-за которого вычисленная высота дерева будет на 1 больше её математического определения (высота пустого множества не определена). Читатель без труда сможет исправить при необходимости эту особенность, добавив ещё один уровень косвенности и явно вычитая 1 из результата вызова метафункции, однако тогда придётся запретить инстанцирование height для пустого дерева.

Код достаточно прост: при попытке вызова height с пустым множеством будет инстанцирована соответствующая специализация, содержащая статическое value = 0 , в противном случае продолжится каскад инстанцирований, пока мы не наткнёмся на пустое поддерево (то есть тот же самый NIL ), на котором рекурсия и остановится. Это характерная особенность реализации рекурсивных функций посредством шаблонов C++: мы обязаны специализировать дно рекурсии, иначе каскад инстанцирований либо не остановится (компилятор выдаст ошибку о превышении лимита вложенных инстанцирований), либо на одном из шагов произойдёт попытка доступа к несуществующему члену или значению в классе (без специализации описанная выше функция в определенный момент не смогла бы получить Tree::LT , когда Tree было бы равно пустому поддереву NIL ).

В коде выше используется функция max . Она должна быть constexpr (или просто метафункцией, тогда её вызов немного изменится), пример простой и известной реализации:

Наконец, использование функции height :

Скажем о «сложности» функции height : требуется n инстанцирований, где n — число узлов дерева; глубина инстанцирования равна h — т.е. высоте дерева.

Дело в том, что, хотя всю работу по рекурсивному вычислению делает компилятор, его мощь не безгранична: с лёгкой руки изобретателей шаблонов наделённый обязанностью решать проблему останова (!), компилятор всё-таки должен контролировать своё собственное состояние и не вдаваться в крайности, занимаясь майнингом биткоинов сумасшедшего метапрограммиста. А если серьёзно, компилятор сам должен уметь остановиться: для этого вводятся ограничения на глубину инстанцирований шаблонов, рекурсивных вызовов constexpr -функций и длину variadic-списков аргументов.

В документации к своему любимому компилятору читатель сможет найти конкретные значения: например, gcc-5.4 «из коробки» (без дополнительных опций) инстанцирует шаблоны не глубже 900 уровней. В свете вышесказанного это означает, что нельзя забывать об оптимизации метафункций (как бы дико это ни звучало). Например, вызов height вполне может отказаться компилироваться gcc, если дерево имеет высоту > 900. Можно даже ввести O-нотацию для описания сложности (хотя часто можно точно посчитать число и глубину инстанцирований), и она будет иметь вполне здравый смысл.

Например, в стандарте C++14 планируется ввести шаблон для генерации целочисленных последовательностей ( std::integer_sequence ): прямая рекурсивная реализация требует N инстанцирований для последовательности 0..N-1, однако существуют элегантные древоподобные решения, глубина рекурсии которых растёт со скоростью логарифма от длины последовательности. В конце концов, мы всегда можем реализовать любую функцию полным перебором, но компилятор этому точно не обрадуется (как и мы, час ждущие завершения компиляции 30-строчной программы или вынужденные читать 9000-страничные сообщения об ошибках).

Если превышение допустимой глубины инстанцирований может просто помешать компиляции, то количество инстанцирований (т.е. вызовов метафункций) прямо влияет на время компиляции: для сложных метапрограмм оно может оказать весьма велико. Здесь играет роль множество факторов (необходимость вывода типов, сопоставление частичных специализаций и т.д.), посему не стоит забывать, что компилятор — такая же программа, а механизм шаблонов — своего рода API к внутреннему кодогенератору компилятора, и пользоваться им надо учиться так же, как осваивать отдельный язык программирования — последовательно и аккуратно (и чтобы никаких «Курсов программирования для чайников за 24 часа»!).

Обход центрированный (in-order traversal)

Задача обхода — определенным образом сформировать список узлов (или данных из узлов, вопрос терминологии и имеет значение на практике). Центрированный (симметричный) обход — обход, при котором корень дерева занимает место между результатами соответствующих обходов левого и правого поддеревьев. Вместе со свойством бинарного дерево поиска (которое о неравенствах, см. теорию) это говорит о том, что центрированный обход бинарного дерева поиска сформирует нам отсортированный список узлов — круто! Вот как будет выглядеть обход определенного ранее дерева:

Рекурсивный алгоритм обхода довольно прост:

Операция «+» в данном случае обозначает конкатенацию списков. Да-да, это именно то, ради чего мы реализовывали конкатенацию кортежей, так как кортежи — это наши списки типов на этапе компиляции. И снова — просто берём и пишем код:

В данном случае не более чем ради наглядности мы воспользовались локальными private псевдонимами: все псевдонимы можно подставить друг в друга и получить фарш, обфусцированный похлеще случайно сгенерированной строки, и даже отступы нас не спасут. Но мы же стараемся для людей, не так ли?

Сложность функции walk : O(n) инстанцирований, где n — число узлов дерева (O-нотация использована для упрощения: аккуратный подсчёт даст примерно 3n вызовов метафункций с учётом конкатенаций). Приятно, что функции tuple_concat и tuple_push выполняют свою работу за 1 инстанцирование, так как они не рекурсивны (благодаря возможности вывода типов parameter pack ‘ов). Глубина инстанцирований, как и в случае height , равна h — высоте дерева.

Не ленитесь добавлять синтаксический сахар и аккуратно форматировать код: метапрограммы объективно воспринимаются хуже, чем обычный код, поэтому стандартные требования к облагораживанию кода ещё более актуальны в этом деле.

Ещё одно замечание по написанию метафункций: читатель, возможно, обратил внимание на то, что для последних двух функций нет необходимости разделять объявление и определение общего шаблона. Это так, однако я придерживаюсь стандартизированного подхода: «от максимально частного к максимально общему». Многие шаблоны целиком работают на частичных специализациях, и в таком случае очень удобно оказывается описывать эти специализации с возрастающим уровнем общности: мысленно программист проходит тот же путь, какой проходит компилятор в попытках инстанцирования и вывода типов.

Поиск

Поиск по ключу является основной операцией в классических бинарных деревьях поиска (название говорит само за себя). Мы решили не разделять ключ и данные, поэтому для сравнения узлов будем применять введённый сравнитель Comp . Рекурсивный алгоритм поиска:

Реализация внешне похожа на разработанные ранее:

Выглядит несколько сложнее, это неспроста: во-первых, сам алгоритм содержит больше ветвлений (больше сравнений и условий), во-вторых, здесь мы уже должны применять определенное ранее отношение порядка, и на его основе продолжать поиск рекурсивно либо в левом, либо в правом поддереве. Обратим внимание на детали:

• Для сравнения типов используется сравнитель из корня дерева: Tree::comp , что логично: отношение порядка определяет как способ построения дерева, так и последующие операции (в том числе, поиск), вот почему было удобно поместить псевдоним сравнителя прямо внутрь шаблона дерева ( node<> ).
• Для доступа к шаблону, зависящему от аргумента шаблона ( Tree::comp::eq и Tree::comp::lt ), необходимо использовать ключевое слово template .
• Мы пошли по пути наименьшего сопротивления и использовали std::conditional — стандартную метафункцию, определяющую результирующий псевдоним в зависимости от булевой переменной (такой аналог тернарного оператора ?: для типов). Почему это может быть не очень хорошо — см. далее, однако из положительных моментов — большая наглядность.

Сложность такой реализации search — опять-таки O(n) инстанцирований, глубина — h (высота дерева). «Стоп!» — воскликнет удивленный читатель, — «а как же логарифмическая сложность поиска и всё такое?»

Тут-то и летят камни в сторону std::conditional и выявляется его принципиальное отличие от оператора ?:: тернарный оператор не вычисляет то выражение, которое не будет его результатом (например, мы можем с чистой совестью разыменовывать нулевой указатель в одном из двух выражений, которое отбросится при проверке этого указателя в первом аргументе оператора). std::conditional же инстанцирует все три аргумента (как обычная метафункция), именно поэтому одного только std::conditional недостаточно для остановки рекурсии, и мы всё ещё должны специализировать дно рекурсии.

Прямой результат — лишние инстанцирования, захватывающие всё дерево целиком от корня до листьев. Особым колдунством с добавлением ещё одного уровня косвенности можно-таки «отключить» на каждом шаге рекурсии инстанцирования по пути поддерева, в котором точно нет искомого узла (написав ещё пачку специализаций для этого уровня косвенности), и добиться заветной сложности O(h), однако, на мой взгляд, это задача для более глубокого исследования и в данном случае будет являться преждевременной оптимизацией.

Примеры применения (использованы шаблоны псевдонимов, больше примеров см. в репозитории):

Это может показаться странным: мы ищем в дереве узел с типом… который фактически уже указан в качестве аргумента — зачем? На самом деле, ничего необычного в этом нет — мы ищем тип, равный аргументу в терминах сравнителя. Деревья STL ( std::map ) тоже хранят в узлах пары ( std::pair ), и первый элемент пары считается ключом, который, собственно, и участвует в сравнениях. Достаточно хранить в нашем дереве ту же std::pair и заставить сравнитель Comp сравнивать пары по первому типу в паре — и получим классический ассоциативный (мета-)контейнер! Мы ещё вернёмся к этой идее в конце статьи.

Вставка

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

Поясним его работу: если дерево, в которое происходит вставка, пусто, то вставляемый элемент создаст новое дерево , т.е. просто лист с этим элементом (дно рекурсии). Если же дерево не пусто, то мы должны рекурсивно проваливаться до пустого дерева (т.е. до момента, пока левое или правое поддеревья не окажутся пустыми), и в итоге сформировать в этом поддереве тот же лист вместо NIL, по пути «подвешивая» себя в виде нового левого или правого поддерева. В мире типов изменять существующие типы мы не можем, но можем создавать новые — это и происходит на каждом шаге рекурсии. Реализация: