Блог

Я пытаюсь решить проблему с HackerRank, связанную здесь.

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

 SELECT N, 'Root'
FROM BST
WHERE ISNULL(P)

UNION

SELECT N, 'Inner'
FROM BST
WHERE N IN (SELECT P FROM BST) AND NOT ISNULL(P)

UNION

SELECT N, 'Leaf'
FROM BST
WHERE N NOT IN (SELECT P FROM BST)

ORDER BY N
  

Мне кажется, что мой подход к идентификации листьев правильный — лист определяется как узел, который не является родительским. Однако, когда я пытаюсь SELECT N, 'Leaf' ... выполнить запрос самостоятельно, я не получаю никаких результатов.

Кто-нибудь может заметить мою ошибку? Правильно ли я использую NOT IN оператор?

редактировать: просто чтобы уточнить, N — это значение узла, а соответствующий P — его родительский элемент. N и P оба являются целыми числами.

Если вы запустите конечный запрос, вы ничего не получите:

 mysql> select n, 'Leaf' from bst where n not in (select p from bst);
Empty set (0.00 sec)
  

Причина в том, что результат подзапроса включает NULL:

 mysql> select distinct p from bst;
 ------ 
| p    |
 ------ 
| NULL |
|    1 |
|    3 |
|    4 |
 ------ 
  

Сравнение N not in (NULL, 1, 3, 4) обязательно не вернет совпадений из-за NULL. Это эквивалентно:

 WHERE NOT (N = NULL OR N = 1 OR N = 3 OR N = 4)
  

Но любое сравнение с NULL равно NULL, а не false . Вы можете получить true / false для других терминов, но не для первого термина. Это упрощает:

 WHERE NOT (NULL OR FALSE OR FALSE OR FALSE)
  

Что, в свою очередь, упрощает:

 WHERE NOT (NULL)
  

Но отрицание NULL также равно NULL, а не true . Поэтому условие в вашем запросе обязательно блокирует все узлы, независимо от того, являются ли они листьями или нет.

Вы можете исправить это, удалив нули:

 mysql> select n, 'Leaf' from bst where n not in (select p from bst where not isnull(p));
 --- ------ 
| n | Leaf |
 --- ------ 
| 2 | Leaf |
| 5 | Leaf |
| 6 | Leaf |
 --- ------ 
  

Вам также следует изучить возможность использования рекурсивных запросов CTE в MySQL 8.0, если у вас есть такие данные:

 WITH RECURSIVE cte (N, Label) AS
( 
  SELECT bst.N, CAST('Root' AS CHAR(20)) FROM bst WHERE ISNULL(P)
  UNION ALL
  SELECT bst.N, IF(below.P IS NULL, 'Leaf', 'Inner') FROM bst JOIN cte ON bst.P=cte.N
  LEFT OUTER JOIN bst AS below ON bst.N=below.P
)
SELECT DISTINCT N, Label FROM cte

 ------ ------- 
| N    | Label |
 ------ ------- 
|    1 | Root  |
|    2 | Leaf  |
|    3 | Inner |
|    4 | Inner |
|    5 | Leaf  |
|    6 | Leaf  |
 ------ ------- 
  

Вы могли бы использовать case выражение:

 select n, 
    case when p is null then 'root'
         when not exists (select 1 from bst b1 where b1.p = b.n) then 'leaf'
         else 'inner'
    end as res
from bst b
  

Эти фразы как:

• если p есть null , у узла нет родительского элемента, следовательно, он является (the?) root

• если нет узла, который p равен n текущему узлу, то у узла нет дочернего элемента: это лист

• в противном случае это внутренний узел

Обратите внимание, что, по крайней мере, теоретически, узел может быть как корневым, так и конечным; в проблемном вопросе не упоминается такая возможность. Если это когда-либо произойдет, запрос будет помечен как корневой (потому что это первая ветвь, которая будет соответствовать case выражению).