Привет. Статья расчитана на разработчика до мидла включительно, но в целом может оказаться полезной и другим. Так, для разминки.
Ты наверняка знаешь что такое рекурсия. Она применяется в разных местах, но, как правило, это классические графовые алгоритмы (DFS, BFS, etc.), когда надо пройтись по веткам вширь, вглубь, туда, сюда и вообще. Однако рекурсия может обойтись дорого, учитывая, помимо прочего, ограничения стека и количество данных.
Есть как минимум три относительно простые задачи, которые связаны с деревьями:
- как узнать всех родителей некоего элемента в плоском связном списке (иными словами, восстановить иерархию без построения дерева; узнать путь до элемента);
- как построить иерархическую структуру, имея на руках только плоский связный список его узлов;
- как вывернуть эту иерархию обратно в плоский связный список.
Возможно, ты удивишься, но для решения всех трёх задач рекурсия не нужна. Ниже будут их решения. Они элементарны, но неочевидны (хотя казалось бы).
Вводные
Есть пачка объектов, например, следующей структуры (в виде стэйтема для удобства):
{
"1": { "id": 1, "hid": null, "title": "Root" },
"3": { "id": 2, "hid": 2, "title": "Leaf 1.1" },
"2": { "id": 3, "hid": 1, "title": "Branch 1" },
"5": { "id": 5, "hid": 1, "title": "Branch 2" },
"6": { "id": 6, "hid": 5, "title": "Leaf 2.1" },
"4": { "id": 4, "hid": 2, "title": "Leaf 1.2" },
"7": { "id": 7, "hid": 5, "title": "Leaf 2.2" }
}Перед тобой классический связный список, но поскольку он несортирован, то это можно назвать и кучей. Терминологией пренебречь. Пусть тебя также не смущает наличие индексов: id нам нужен и там, и сям.
Поиск родителей элемента
Решение первой задачи предельно простое. Поскольку каждый элемент ссылается на родителя (кроме самого верховного элемента-родителя), нам просто следует пройтись по хидам до тех пор, пока не наткнёмся на пустой.
function hierarchy(
array $flat_list,
array $node,
string $fk = 'hid',
string $pk = 'id',
): array {
$stack[$node[$pk]] = $node;
while (!empty($flat_list[$node[$fk]])) {
$node = $flat_list[$node[$fk]];
$stack[$node[$pk]] = $node;
}
return $stack;
}Алгоритмическая сложность функции — O(n), где n – количество элементов во входном массиве $flat_list.
Если на входе массив не индексирован по id (как в моём примере), позаботься об этом самостоятельно заранее. Также, возможно, тебе потребуется сортировка.
Остаётся скормить массив функции hierarchy() и она вернёт корректный кусок списка, в котором будет сам элемент и все его родители до максимального.
Построение дерева
С иерархией чуть интереснее, так что решение я объясню чуть подробнее.
На выходе ты должен получить дерево следующей структуры:
[
{
"id": 1,
"hid": null,
"title": "Root",
"children": [
{
"id": 2,
"hid": 1,
"title": "Branch 1",
"children": [
{ "id": 3, "hid": 2, "title": "Leaf 1.1" },
{ "id": 4, "hid": 2, "title": "Leaf 1.2" }
]
},
{
"id": 5,
"hid": 1,
"title": "Branch 2",
"children": [
{ "id": 6, "hid": 5, "title": "Leaf 2.1" },
{ "id": 7, "hid": 5, "title": "Leaf 2.2" }
]
}
]
}
]Смысл решения в том, чтобы вместо накопления стека рекурсии использовать отдельный ассоциированный массив. В него будут покладаться элементы, которые на текущей итерации не являются папами и мамами, но на следующих итерациях они могут таковыми стать.
Что неочевидно и, на первый взгляд, весьма удивительно: дерево мы будем строить сверху вниз. Чево, блять? Да, от родителей к потомкам. Не смотря на то, что элементы ссылаются снизу вверх. В этом нам помогут логика и ссылки.
function tree(
array $flat_list,
string $fk = 'hid',
string $pk = 'id',
): array {
$tree = [];
foreach ($flat_list as &$node) {
$references[$node[$pk]] = &$node;
if (empty($node[$fk]) || empty($references[$node[$fk]])) {
$tree[$node[$pk]] = &$node;
} else {
$references[$node[$fk]]['children'][] = &$node;
}
}
return $tree;
}Алгоритмическая сложность функции — O(n), где n – количество элементов во входном массиве $flat_list.
На каждой итерации узел сначала добавляется в промежуточный массив. Если узел не ссылается на другой, то считается родителем верхнего уровня. Если узел ссылается на другой, то этот другой мы берём из промежуточного массива и к его детям добавляем текущий.
UPD 29.11.23:
я также добавил || empty($references[$node[$fk]]) для того, чтобы добавлять на 1 уровень узлы, родители коих не найдены.
Раз уж мы заменили рекурсию единственным циклом, то построение дерева сильно зависит от сортировки входного списка по возрастанию $fk (`hid`-ов в нашем случае). Ну и данные на вход должны прилететь индексированными.
Присвоения делаем по ссылкам, через это мы экономим тучу памяти: строя текущее дерево, его элементы хранятся, на самом деле, в пришедшем массиве $flat_list. Фактически, на уровне zval, сами данные в $tree храниться не будут.
Для бонусного понимания работы ссылок в пыхе, рекомендую почитать про copy-on-write.
Ну и
, само собой.
Уплощение дерева
Собственно, это тоже очень легко. Размотать дерево мы сможем единственным циклом по элементам, но с хитрецой:
function flatten(
array $tree,
string $branching = 'children'
): array {
$result = [];
while (count($tree)) {
$node = array_shift($tree);
if (!empty($node[$branching])) {
$tree = array_merge($tree, $node[$branching]);
unset($node[$branching]);
}
$result[] = $node;
}
return $result;
}Алгоритмическая сложность при отсутствии потомков — O(n), где n — общее количество узлов во входном дереве $tree. Однако при наличии потомков сложность взлетит до O(n * log n).
На вход первым аргументом мы отдаём дерево, которое построили функцией tree() или любой другой — нам достаточно вторым аргументом указать по какому ключу в нодах лежат её потомки.
Мы бежим по дереву до тех пор, пока оно не иссякнет. Шифтуем первую ноду из дерева в отдельную переменную, элементы дерева смещаются к началу. Если у ноды есть потомки — перемещаем их на первый уровень в конец исходного дерева. Саму эту ноду сохраняем в отдельный стек.
На каждой итерации исходный массив уменьшается на 1 ноду-родителя, но прирастает её потомками второго уровня. Пожалуй, ближайшая ассоциация — работа путеукладчика, когда он катится по рельсам, которые сам перед собой ставит, перевозя и постепенно разбирая стопку заготовленных плотен. В итоге функция вернёт плоский список.
Как видишь, рекурсия совсем необязательна для деревьев, но это не значит, что ты покроешь все свои потребности без неё. Например, у меня недавно стояла задача вычистить “пустые папки” из иерархии (удалить ноды, которые явно указаны как родительские, но фактически не имеют потомков). Для решения такого рода задачи я не увидел адекватного применения описанным выше алгоритмам.
Примеры вх. данных и кода — всего лишь примеры. Бенчмарки и конченая реализация остаются на твоей совести, но основные концепции я постарался донести.