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

Опубликовано Опубликовано в рубрике PHP, SQL, Theory, Деревья

Приветствую всех читателей моего блога!

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

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

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

ID узла — id_node ID родителя — id_parent Заголовок — title
1 2 Один
2 0 Два
3 4 Три
4 1 Четыре
5 2 Пять

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

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

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

   private function getCategoryArray() {
        $query = $this->db_connect->prepare("SELECT * FROM tree_table");
        $query->execute();
        $result = $query->fetchAll(PDO::FETCH_OBJ);
        
        $category_array = array();
        foreach ($result as $value) {
            $category_array[$value->id_parent][] = $value;
        }

        return $category_array;
    }

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

    public function buildTree($parent_id, $tree_level) {
        if (isset($this->category[$parent_id])) { 
            foreach ($this->category[$parent_id] as $value) { 
                echo "
" . $value->id_tree_test . " : " . $value->title . "
"; $tree_level++; $this->buildTree($value->id_tree_test, $tree_level); $tree_level--; } } }

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

    $tree = new Tree();
    $tree->buildTree(0, 0); 

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

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

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

За сим все! Безошибочного Вам кода!

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

  1. «Мы смело оперируем фабриками, синглтонами и декораторами, но забываем о такой фундаментальной части программирования, как классические алгоритмы»
    Так и есть! Спасибо за статью, разобрался.

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

    С уважением.

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *