Что такое…

Что такое дерево в программировании — и почему в базе оно хранится плоским списком

Иллюстрация: дерево вверх ногами — один корень сверху, внизу листья и маленькие папки

Ты сегодня уже пользовался деревом. И не одним. Открывал папку внутри папки. Читал ответ на комментарий к комментарию. Раскрывал меню «Настройки → Аккаунт → Безопасность». Всё это — деревья.

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

Что такое дерево — в одну строку

Дерево — это способ хранить данные, где у каждого элемента есть один родитель и сколько угодно детей. Кроме самого верхнего: у него родителя нет.

Названия взяли у настоящего дерева, только нарисованного вверх ногами:

  • корень — самый верхний элемент, с него всё начинается;
  • узел — любой элемент дерева;
  • родитель и дети — узел и те, что висят прямо под ним;
  • лист — узел без детей, конец ветки.

Папки на компьютере — идеальный пример. Диск — корень. Папки — узлы. Файлы — листья: внутри файла больше ничего не лежит.

Где ты встречаешь деревья каждый день

Как только замечаешь форму, деревья обнаруживаются повсюду:

  • Страница сайта. Браузер превращает HTML в дерево элементов: внутри body — div, внутри него — кнопка. Это дерево называется DOM.
  • JSON-ответ сервера. Объект внутри объекта внутри списка — тоже дерево. Подробно о формате — в статье что такое JSON.
  • Комментарии с ответами. Пост — корень, комментарии — дети, ответы — внуки.
  • Меню и категории магазина. «Одежда → Обувь → Кроссовки».
  • Интерфейс в React. Компоненты вложены друг в друга — и React держит их деревом.

Главное свойство всех этих случаев: глубина заранее неизвестна. Ответ на ответ на ответ — сколько уровней будет? Никто не знает. И это определяет, как с деревом работать.

Как пройти дерево неизвестной глубины

Обычный цикл тут спотыкается. Он хорош, когда уровней один или два. А когда их может быть двадцать?

Тут помогает хитрое наблюдение: каждая ветка дерева — сама по себе дерево. У ветки «Обувь» есть свой корень и свои дети. Значит, достаточно написать функцию для одного узла: «обработай себя, потом вызови меня же для каждого ребёнка».

function countFiles(folder) {
  let total = folder.files.length
  for (const child of folder.folders) {
    total += countFiles(child) // та же функция, но для ветки
  }
  return total
}

Функция вызывает сама себя, пока не дойдёт до листьев. Это называется рекурсией. Ей всё равно, сколько уровней: два или двести.

Почему база хранит дерево плоским

Вернёмся к загадке. Таблицы в базе данных плоские: строки и столбцы, никакой вложенности. Как в них положить дерево?

Очень просто: каждая строка помнит только своего родителя.

id | text             | parent_id
1  | Отличный пост!   | null
2  | Согласен         | 1
3  | А я нет          | 1
4  | Почему?          | 3

У первого комментария родителя нет — это корень ветки. Второй и третий — ответы на первый. Четвёртый — ответ на третий. Дерево здесь есть, но спрятано в столбце parent_id. Код забирает строки списком и сам раскладывает их по веткам.

Почему не хранить сразу деревом? Потому что так проще менять. Новый ответ — одна новая строчка. Перенести ветку — поменять одну цифру. Никакой перестройки.

Зачем это тебе, если код пишет ИИ

Когда ты узнаёшь дерево в своей задаче, ты можешь дать модели точное задание. Сравни:

Слабый промптСделай комментарии с ответами.
Сильный промптКомментарии с ответами неограниченной глубины. В базе храни плоско: у каждого комментария поле parent_id (null у корневых). На клиенте собери дерево из списка и рисуй его рекурсивным компонентом, каждый уровень с отступом. Удаление комментария не должно удалять ответы на него — покажи вместо текста «Комментарий удалён».

Во втором промпте ты сразу закрыл три грабли: жёстко зашитую глубину, неудобную схему базы и потерю веток при удалении.

Чем дерево отличается от списка?

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

Чем дерево отличается от графа?

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

Что будет, если дерево очень глубокое?

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

Стань ИИ-архитектором, а не просто читай об ИИ

Курс «Профессия 2027: ИИ-архитектор»: шаг за шагом от основ компьютера до своего приложения и первых клиентов. 543 коротких урока на телефоне.

Об Академии
Робот KODiQ

ИИ-редактор KODiQ. Пишет про вайб-кодинг и AI-инструменты простым языком — каждый день.

Все статьи →