PrepBro
← Назад к вопросам

SQL: Маркировка узлов древовидной структуры

1.8 Middle🔥 141 комментариев
#SQL и базы данных

Условие

Дана таблица tree с древовидной структурой:

CREATE TABLE tree (
    node_id INT PRIMARY KEY,
    parent_id INT
);

Пример данных:

node_idparent_id
1NULL
21
31
42
52
63

Задание:

Напишите SQL-запрос, который классифицирует каждый узел:

  • Root — узел без родителя (parent_id IS NULL)
  • Leaf — узел без дочерних узлов
  • Inner — узел с родителем и дочерними узлами

Ожидаемый результат:

node_idnode_type
1Root
2Inner
3Inner
4Leaf
5Leaf
6Leaf

Комментарии (1)

🐱
claude-haiku-4.5PrepBro AI23 мар. 2026 г.(ред.)

Ответ сгенерирован нейросетью и может содержать ошибки

Решение

Задача и подход

Нужно классифицировать узлы дерева по трём типам: Root (корень), Leaf (лист), Inner (внутренний). Используем стандартные SQL техники с самоприсоединением (self-join) для определения наличия дочерних узлов и анализа родительских связей.

Основной алгоритм:

  1. Root: узлы где parent_id IS NULL
  2. Leaf: узлы, которые не появляются как parent_id для других узлов
  3. Inner: все остальные (имеют и родителя, и детей)

Решение на SQL

SELECT 
    t.node_id,
    CASE
        WHEN t.parent_id IS NULL THEN 'Root'
        WHEN NOT EXISTS (
            SELECT 1 
            FROM tree children 
            WHERE children.parent_id = t.node_id
        ) THEN 'Leaf'
        ELSE 'Inner'
    END AS node_type
FROM tree t
ORDER BY t.node_id;

Альтернативный подход с LEFT JOIN

SELECT 
    t.node_id,
    CASE
        WHEN t.parent_id IS NULL THEN 'Root'
        WHEN COUNT(children.node_id) = 0 THEN 'Leaf'
        ELSE 'Inner'
    END AS node_type
FROM tree t
LEFT JOIN tree children ON t.node_id = children.parent_id
GROUP BY t.node_id, t.parent_id
ORDER BY t.node_id;

Объяснение логики

1. Root-узел: проверяем parent_id IS NULL — нет родителя 2. Leaf-узел: используем NOT EXISTS для проверки отсутствия дочерних узлов — если ни один узел не имеет parent_id = t.node_id, то это лист 3. Inner-узел: все остальные случаи — узлы, которые имеют и родителя, и детей

Производительность

Второй вариант с LEFT JOIN и GROUP BY часто быстрее на больших таблицах, так как использует одно сканирование вместо нескольких подзапросов. Первый вариант с NOT EXISTS может быть оптимальнее при наличии индекса на parent_id.

Результат

Для примера из условия получаем:

  • node_id 1: Root (нет родителя)
  • node_id 2, 3: Inner (имеют родителя и детей)
  • node_id 4, 5, 6: Leaf (нет дочерних узлов)