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

Решение

Задача требует классификации узлов дерева по их типам (Root, Leaf, Inner). Это типичная задача анализа иерархических структур, часто встречается при работе с каталогами, организационными структурами и ситемами меню.

Подход к решению

Логика классификации:

• Root — узел без родителя (parent IS NULL)
• Leaf — узел без потомков (отсутствует в столбце parent других строк)
• Inner — узел с потомками и есть родитель (противоположность Root и Leaf)

SQL-запрос

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

Пошаговое объяснение

1. Условие для Root

• WHEN t.parent IS NULL — проверяем, есть ли родитель
• Если родителя нет, это корневой узел

2. Условие для Leaf

• WHEN NOT EXISTS (SELECT 1 FROM tree WHERE parent = t.node) — проверяем наличие потомков
• Подзапрос ищет строки, у которых parent равен текущему узлу
• Если ничего не найдено, это листовой узел

3. Условие для Inner

• ELSE 'Inner' — все остальные узлы (есть родитель И есть потомки)

Альтернативный вариант с LEFT JOIN

SELECT 
  t.node,
  CASE 
    WHEN t.parent IS NULL THEN 'Root'
    WHEN children.node IS NULL THEN 'Leaf'
    ELSE 'Inner'
  END AS type
FROM tree t
LEFT JOIN tree children ON t.node = children.parent
GROUP BY t.node, t.parent
ORDER BY t.node;

Как работает:

• LEFT JOIN tree children ON t.node = children.parent — присоединяем потомков
• children.node IS NULL — если потомков нет, то это Leaf
• GROUP BY — группируем по узлам для удаления дубликатов

Вариант с COUNT (для подсчёта потомков)

SELECT 
  t.node,
  t.parent,
  CASE 
    WHEN t.parent IS NULL THEN 'Root'
    WHEN children_count = 0 THEN 'Leaf'
    ELSE 'Inner'
  END AS type,
  COALESCE(children_count, 0) AS children_count
FROM tree t
LEFT JOIN (
  SELECT parent, COUNT(*) AS children_count
  FROM tree
  WHERE parent IS NOT NULL
  GROUP BY parent
) child_counts ON t.node = child_counts.parent
ORDER BY t.node;

Этот вариант дополнительно показывает количество потомков.

Пример выполнения

Исходные данные:

node | parent
-----|-------
1    | NULL
2    | 1
3    | 1
4    | 2
5    | 2

Анализ каждого узла:

• Узел 1: parent = NULL → Root
• Узел 2: parent = 1 (не NULL), есть потомки (4, 5) → Inner
• Узел 3: parent = 1 (не NULL), нет потомков → Leaf
• Узел 4: parent = 2 (не NULL), нет потомков → Leaf
• Узел 5: parent = 2 (не NULL), нет потомков → Leaf

Результат:

node | type
-----|------
1    | Root
2    | Inner
3    | Leaf
4    | Leaf
5    | Leaf

Визуализация структуры

        1 (Root)
       / \
      2   3 (Leaf)
    (Inner)
     / \
    4   5 (Leaf)
  (Leaf)

Важные моменты

✓ EXISTS vs JOIN — EXISTS более эффективен для проверки наличия (не требует объединения всех строк)

✓ GROUP BY в JOIN варианте — необходим для удаления дубликатов при наличии нескольких потомков

✓ COALESCE при COUNT — нужен для обработки случаев, когда нет потомков (COUNT вернёт NULL)

✓ Множественные корни — если структура позволяет несколько корневых узлов, все будут помечены как Root

✓ Циклические ссылки — запрос не проверяет наличие циклов (узел А → Б → А). Для проверки потребуется рекурсивный CTE

✓ Рекурсивный вариант для глубины дерева — если нужна информация об уровне узла в дереве:

WITH RECURSIVE tree_levels AS (
  SELECT node, parent, 0 AS level
  FROM tree
  WHERE parent IS NULL
  UNION ALL
  SELECT t.node, t.parent, tl.level + 1
  FROM tree t
  INNER JOIN tree_levels tl ON t.parent = tl.node
)
SELECT 
  t.node,
  CASE 
    WHEN t.parent IS NULL THEN 'Root'
    WHEN NOT EXISTS (SELECT 1 FROM tree WHERE parent = t.node) THEN 'Leaf'
    ELSE 'Inner'
  END AS type,
  tl.level
FROM tree t
LEFT JOIN tree_levels tl ON t.node = tl.node
ORDER BY tl.level, t.node;