Дерево

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

Самый известный частный случай — бинарное дерево поиска: у каждого узла не больше двух потомков, слева меньшие значения, справа большие. Если дерево сбалансировано, поиск занимает число шагов порядка логарифма от количества узлов. На похожей идее основаны индексы баз данных: в MySQL и MariaDB индексы InnoDB устроены как B-деревья, где у узла много потомков, а глубина остаётся небольшой даже при миллионах строк.

Где деревья встречаются в веб-разработке

• Браузер строит из HTML DOM — дерево элементов, с которым работает JavaScript.
• В WordPress у страниц и рубрик есть родитель: поле post_parent у записей и parent у терминов таксономии.
• В 1С-Битрикс разделы инфоблока хранятся по схеме вложенных множеств: у раздела есть поля LEFT_MARGIN, RIGHT_MARGIN и DEPTH_LEVEL, поэтому всю ветку можно выбрать одним запросом.

Пример: дерево меню из плоского списка

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

function buildTree(array $rows, int $parentId = 0): array {
    $branch = [];
    foreach ($rows as $row) {
        if ((int) $row['parent_id'] === $parentId) {
            $row['children'] = buildTree($rows, (int) $row['id']);
            $branch[] = $row;
        }
    }
    return $branch;
}

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

Типичные трудности

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