php рекурсивный обход дерева

/dev/energy

Сайт о том, как стать программистом и как с этим жить потом

О простом. Построение простого дерева.

Совсем недавно я обнаружил очень интересную особенность развития современных web-программистов. Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, как классические алгоритмы. Ведь если присмотреться к их реализации, то это тоже своего рода паттерны. С институтской скамьи можно вспомнить, к примеру, nested sets, b-tree, сортировку «пузырьком». Реализация многих алгоритмов давно устоялась. А потому, я хотел бы посвятить несколько статей алгоритмам и их применении в PHP.

Начну я с самого простого — построения древовидной иерархии.

Казалось бы, что тут сложного? В базе данных есть таблица примерно следующего содержания:

Необходимо представить этот массив в виде древовидного меню. Я не буду говорить о том, какими неправильными способами можно решить эту задачу =)
Единственно верный подход в данном случае — рекурсивный метод.

Алгоритм (паттерн, если так хотите) будет примерно следующим:
0. Создаем объект дерева и выбираем все элементы в таблице.
1. Вызываем метод построения. Он инициализирует сборку массива родительских категорий. Именно этот момент является ноу-хау данного алгоритма. Он позволяет нам организовать изящную рекурсию.
2. Итеративно обходим массив, начиная с нулевого элемента. Выводим информацию о текущем элементе.
3. Увеличиваем уровень погружения. Рекурсивно вызываем метод для дочернего элемента. Если он есть в массиве родительских категорий, то идем к шагу 2, иначе — выходим в шаг-инициализатор.
4. Уменьшаем уровень погружения. Выходим из итерации.

Итак, метод сборки массива категорий будет выглядеть примерно вот так

Далее напишем наш рекурсивный метод в соответствии с приведенным выше алгоритмом

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

А вот как будет выглядеть наше дерево в итоге : посмотреть

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

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

Источник

Бинарные деревья поиска и рекурсия – это просто

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

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

Рис. 1 Бинарное дерево

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

Рис. 2 Бинарное дерево поиска
Сбалансированное бинарное дерево поиска — это бинарное дерево поиска с логарифмической высотой. Данное определение скорее идейное, чем строгое. Строгое определение оперирует разницей глубины самого глубокого и самого неглубокого листа (в AVL-деревьях) или отношением глубины самого глубокого и самого неглубокого листа (в красно-черных деревьях). В сбалансированном бинарном дереве поиска операции поиска, вставки и удаления выполняются за логарифмическое время (так как путь к любому листу от корня не более логарифма). В вырожденном случае несбалансированного бинарного дерева поиска, например, когда в пустое дерево вставлялась отсортированная последовательность, дерево превратится в линейный список, и операции поиска, вставки и удаления будут выполняться за линейное время. Поэтому балансировка дерева крайне важна. Технически балансировка осуществляется поворотами частей дерева при вставке нового элемента, если вставка данного элемента нарушила условие сбалансированности.

Рис. 3 Сбалансированное бинарное дерево поиска

Сбалансированное бинарное дерево поиска применяется, когда необходимо осуществлять быстрый поиск элементов, чередующийся со вставками новых элементов и удалениями существующих. В случае, если набор элементов, хранящийся в структуре данных фиксирован и нет новых вставок и удалений, то массив предпочтительнее. Потому что поиск можно осуществлять алгоритмом бинарного поиска за то же логарифмическое время, но отсутствуют дополнительные издержки по хранению и использованию указателей. Например, в С++ ассоциативные контейнеры set и map представляют собой сбалансированное бинарное дерево поиска.

Рис. 4 Экстремально несбалансированное бинарное дерево поиска

Теперь кратко обсудим рекурсию. Рекурсия в программировании – это вызов функцией самой себя с другими аргументами. В принципе, рекурсивная функция может вызывать сама себя и с теми же самыми аргументами, но в этом случае будет бесконечный цикл рекурсии, который закончится переполнением стека. Внутри любой рекурсивной функции должен быть базовый случай, при котором происходит выход из функции, а также вызов или вызовы самой себя с другими аргументами. Аргументы не просто должны быть другими, а должны приближать вызов функции к базовому случаю. Например, вызов внутри рекурсивной функции расчета факториала должен идти с меньшим по значению аргументом, а вызовы внутри рекурсивной функции обхода дерева должны идти с узлами, находящимися дальше от корня, ближе к листьям. Рекурсия может быть не только прямой (вызов непосредственно себя), но и косвенной. Например А вызывает Б, а Б вызывает А. С помощью рекурсии можно эмулировать итеративный цикл, а также работу структуры данных стек (LIFO).

Кратко обсудим деревья с точки зрения теории графов. Граф – это множество вершин и ребер. Ребро – это связь между двумя вершинами. Количество возможных ребер в графе квадратично зависит от количества вершин (для понимания можно представить турнирную таблицу сыгранных матчей). Дерево – это связный граф без циклов. Связность означает, что из любой вершины в любую другую существует путь по ребрам. Отсутствие циклов означает, что данный путь – единственный. Обход графа – это систематическое посещение всех его вершин по одному разу каждой. Существует два вида обхода графа: 1) поиск в глубину; 2) поиск в ширину.

Поиск в ширину (BFS) идет из начальной вершины, посещает сначала все вершины находящиеся на расстоянии одного ребра от начальной, потом посещает все вершины на расстоянии два ребра от начальной и так далее. Алгоритм поиска в ширину является по своей природе нерекурсивным (итеративным). Для его реализации применяется структура данных очередь (FIFO).

Поиск в глубину (DFS) идет из начальной вершины, посещая еще не посещенные вершины без оглядки на удаленность от начальной вершины. Алгоритм поиска в глубину по своей природе является рекурсивным. Для эмуляции рекурсии в итеративном варианте алгоритма применяется структура данных стек.

С формальной точки зрения можно сделать как рекурсивную, так и итеративную версию как поиска в ширину, так и поиска в глубину. Для обхода в ширину в обоих случаях необходима очередь. Рекурсия в рекурсивной реализации обхода в ширину всего лишь эмулирует цикл. Для обхода в глубину существует рекурсивная реализация без стека, рекурсивная реализация со стеком и итеративная реализация со стеком. Итеративная реализация обхода в глубину без стека невозможна.

Асимптотическая сложность обхода и в ширину и в глубину O(V + E), где V – количество вершин, E – количество ребер. То есть является линейной по количеству вершин и ребер. Записи O(V + E) с содержательной точки зрения эквивалентна запись O(max(V,E)), но последняя не принята. То есть, сложность будет определятся максимальным из двух значений. Несмотря на то, что количество ребер квадратично зависит от количества вершин, мы не можем записать сложность как O(E), так как если граф сильно разреженный, то это будет ошибкой.

DFS применяется в алгоритме нахождения компонентов сильной связности в ориентированном графе. BFS применяется для нахождения кратчайшего пути в графе, в алгоритмах рассылки сообщений по сети, в сборщиках мусора, в программе индексирования – пауке поискового движка. И DFS и BFS применяются в алгоритме поиска минимального покрывающего дерева, при проверке циклов в графе, для проверки двудольности.
Обходу в ширину в графе соответствует обход по уровням бинарного дерева. При данном обходе идет посещение узлов по принципу сверху вниз и слева направо. Обходу в глубину в графе соответствуют три вида обходов бинарного дерева: прямой (pre-order), симметричный (in-order) и обратный (post-order).

Прямой обход идет в следующем порядке: корень, левый потомок, правый потомок. Симметричный — левый потомок, корень, правый потомок. Обратный – левый потомок, правый потомок, корень. В коде рекурсивной функции соответствующего обхода сохраняется соответствующий порядок вызовов (порядок строк кода), где вместо корня идет вызов данной рекурсивной функции.

Если нам дано изображение дерева, и нужно найти его обходы, то может помочь следующая техника (см. рис. 5). Обводим дерево огибающей замкнутой кривой (начинаем идти слева вниз и замыкаем справа вверх). Прямому обходу будет соответствовать порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами слева. Для симметричного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами снизу. Для обратного обхода порядок, в котором огибающая, двигаясь от корня впервые проходит рядом с узлами справа. В коде рекурсивного вызова прямого обхода идет: вызов, левый, правый. Симметричного – левый, вызов, правый. Обратного – левый правый, вызов.

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

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

Надеюсь Вы не уснули, и статья была полезна. Скоро надеюсь последует продолжение банкета статьи.

Источник

Рекурсия на PHP

В этой статье расскажу вам о рекурсии и о том как грамотно работать с ней на языке PHP.

PHP расшифровывается как PHP: Hypertext Preprocessor. Это смущает многих людей, потому что первое слово аббревиатуры это аббревиатура. Этот тип аббревиатуры называется рекурсивной аббревиатурой.

Перевод Google из официальной документации по PHP

Понятие рекурсии

Для начала разберёмся с понятием рекурсии. В общем смысле рекурсия это отображение чего-либо внутри самого себя. Рекурсивные алгоритмы используют рекурсивные функции, обладающие данным свойством.

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

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

Другим примером можно взять всем хорошо известное детское стихотворение:

…
Эта докучная сказка представляет собой пример простой рекурсии (здесь функция вызывает саму себя).

Глубина рекурсии

В связи с понятием рекурсии возникает понятие глубины рекурсии, то есть степени вложенности её отображений. Русская матрёшка, как правило, имеет 3-х и более вложенных в неё матрёшек. То есть глубина рекурсии в данном случае равна количеству вложенных матрёшек. Глубина рекурсии может быть равна бесконечности, в этом случае говорят о бесконечной рекурсии.

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

Для нас важно, что ограничениям подвержен и сам компьютер. Память компьютера, производительность — не бесконечны. Поэтому применяя рекурсию, нужно понимать её опасности и подводные камни.

Опасности и подводные камни рекурсии

Рассмотрим простой пример.

Здесь функция foo() должна вызывать самое себя до бесконечности. В реальных условиях запуск программы приведёт к Segmentation fault, так как произойдёт переполнение стека вызова в силу ограничений на выделенную под него память. Понимая это следует избегать таких конструкций при разработке.

То же самое касается и примера со сложной рекурсией.

В PHP две функции не могут вызывать друг друга бесконечно, так как это неизбежно
приведёт к падению программы.

Теперь вернёмся к понятию глубины рекурсии. И рассмотрим следующий пример.

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

Рекурсивные алгоритмы на PHP

Теперь мы можем приступить к исследованию алгоритмов основанных на рекурсии.

Существует множество таких алгоритмов:

Рассмотрим некоторые из них.

Вычисление последовательности Фибоначчи

Следует сделать лирическое отступление, которое касается истории открытия данной последовательности…

В 1202 году Леонардо Пизанский, известный как Фибоначчи, решая задачу о размножении кроликов, пришёл к открытию рекуррентного соотношения:
Эта последовательность обладает одним замечательным свойством, а именно:
Число Фи, представляет собой золотую пропорцию, которая часто встречается в природе, выражая собой закон гармонии и красоты…

Вернёмся к нашему алгоритму. Знание рекуррентного соотношения позволяет нам с лёгкостью реализовать этот алгоритм на PHP:

С точки зрения программирования нам интересно знать насколько быстро он выполняется по сравнению с его реализацией на основе итераций, например этой:

Дело в том, что реализация рекурсивного алгоритма “в лоб” обладает одним существенным недостатком. А именно при такой реализации вызов функции для одного и того же аргумента производится многократно. Чтобы это увидеть, нужно внимательно рассмотреть само рекуррентное соотношение.

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

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

Оказывается, что при рекурсивном вызове функций создаются копии её аргументов в стеке и следовательно дополнительные затраты на время выполнения операций копирования.
Чтобы обойти это, может быть использована парадигма Объектно-Ориентированного Программирования (ООП). К примеру мы можем создать массив внутри объекта, который будет иметь рекурсивный метод, внутри которого будет доступ к этому массиву так, что не потребуется передавать этот массив в качестве параметра для каждого вызова этого метода:

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

Предлагаю вам пока самостоятельно поразмышлять на эту тему.

Источник

Задача отображения деревьев в MySql. Способ отображения на хранимых процедурах

Доброго времени суток.

Очень хотелось поднять вопрос о древовидных структурах в MySql. А конкретно о выборках и хранении данных…
Пользователям Oracle и PostgresSQL живется хорошо, в этих БД есть встроенные средства выборки рекурентных данных (см. Иерархические (рекурсивные) запросы).
Пользователям Mysql приходится работать уже с тем, что есть, то есть работа на стороне клиента.
Поскольку эта тема не однократно поднималась, то я попробую рассказать о конкретной задаче и способе её решения.

Задача

Производится выборка данных всего дерева рекурентно на стороне клиента. Общий объем базы 500Мб, и дальше будет только расти. Поскольку ветвей и узлов много, то общее количество запросов к базе на данный момент колеблется от 300 до 1000.

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

Вариант решения

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

В публикациях наиболее часто встречается решение с дополнительным поле типа varchar, в котором хранятся id-шники текстом, разделенные спецсимволом. По этому полю осуществляется сортировка и ограничение чем-нибудь типа like %. %.

В итоге получаем достаточно тяжелое и сложное решение. Времени на его реализацию как всегда не было.

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

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

Запуск процедуры предваряется созданием временной таблички, а затем простой селект выдирает необходимые данные.

Так что я сделал так: сформировал каракас дерева на основе ссылок, последовательно помещая ссылку на элемент-дитя в элемент-родитель. После формирования каркаса дерева я проходил по нему рекурентно и создавал уже дерево с реальными данными.

Вот код преобразования, он в внутри класса. Прошу не судить строго, писалось быстро, из-под палки:

В итоге, получили вполне работоспособную штуку. В случае большой базы и глубины рекурсии данному решению тоже может быть плохо. конкретно может быть плохо mySql-серверу. я бы решал эту проблему введением кеширующей таблицы (постоянной), которая бы хранила бы результаты спуска от начала определенного элемента, и копировала бы их во временную таблицу. То есть получался бы классический кеш рекурсии, только на SQL. Это близко к методам динамического программирования. Может быть когда-нибудь дореализую, если локального кеша не хватит на стабильную работу. Хотя я думаю, что хватит…

Источник

Русские Блоги

Структура данных и алгоритм PHP для обхода двоичного дерева

Во-первых, обход двоичного дерева

Посещение всех узлов в дереве в определенном порядке называетсяОбход дерева, Обход двоичного дерева можно разделитьОбход в глубинусПервый обход в ширину。

Обход в глубину： Глубоко в каждом возможном пути ветвления до точки, где он не может идти дальше, и каждый узел можно посетить только один раз. Можно подразделить наПредзаказТраверс,Средний порядокТраверс,Последовательность публикацииТраверс.

Для любого поддерева сначала посетите корень, затем обойдите его левое поддерево и, наконец, обойдите его правое поддерево.

Для любого поддерева сначала обойдите его левое поддерево, затем посетите корень и, наконец, обойдите его правое поддерево.

② Посетите левое поддерево. [Сначала посетите левое поддерево в левом поддереве, а затем посетите правое поддерево в левом поддереве. ] Выводить до тех пор, пока не будет посещен листовой узел.

③Посетите правое поддерево. [Сначала посетите левое поддерево в правом поддереве, а затем посетите правое поддерево в правом поддереве. ] Выводить до тех пор, пока не будет посещен листовой узел.

① Посетите левое поддерево. [Сначала посетите левое поддерево в левом поддереве, а затем посетите правое поддерево в левом поддереве. ] Выводить до тех пор, пока не будет посещен листовой узел.

③Посетите правое поддерево. [Сначала посетите левое поддерево в правом поддереве, а затем посетите правое поддерево в правом поддереве. ] Выводить до тех пор, пока не будет посещен листовой узел.

① Посетите левое поддерево. [Сначала посетите левое поддерево в левом поддереве, а затем посетите правое поддерево в левом поддереве]. Выводить до тех пор, пока не будет посещен листовой узел.

② Посетите нужное поддерево. [Сначала посетите левое поддерево в правом поддереве, а затем посетите правое поддерево в правом поддереве]. Выводить до тех пор, пока не будет посещен листовой узел.

③Возврат к корню посещения и выход.

В качестве корня сначала выводится A.

Точно так же посмотрите на правое поддерево A.

Затем посетите правое поддерево в левом поддереве. То есть посетить правое поддерево E дерева B, E не имеет левого и правого поддеревьев и вывести E. Затем выведите B.

Затем посетите правое поддерево в правом поддереве. То есть посетить правое поддерево C, C не имеет правого поддерева и вывести C. Затем выведите A.

Источник