двоичное дерево вложенных множеств, запрос крайнего левого и правого узлов - PullRequest
Новая
       26

двоичное дерево вложенных множеств, запрос крайнего левого и правого узлов

0 голосов
/ 22 сентября 2018

У меня есть таблица MySQL, хранящая двоичное дерево в модели вложенного множества с некоторыми дополнительными свойствами.Двоичное дерево не является ни полным, ни полным, поэтому в середине могут быть узлы только с одним дочерним элементом.

Это выглядит примерно так (но с гораздо большим количеством данных): 

+----+------+-------+-----------+-------+----------+--------------------+
| id | left | right | parent_id | level | position | number_of_children |
+----+------+-------+-----------+-------+----------+--------------------+
|  1 |    1 |     8 | NULL      |     1 | LEFT     |                  3 |
|  2 |    2 |     3 | 1         |     2 | LEFT     |                  0 |
|  3 |    4 |     7 | 1         |     2 | RIGHT    |                  1 |
|  4 |    5 |     6 | 2         |     3 | LEFT     |                  0 |
+----+------+-------+-----------+-------+----------+--------------------+

Как я могу запросить крайний левый или самый правый узелдерева или поддерева?

Некоторое графическое объяснение: https://imgur.com/w7gxtOC

Я пробовал это несколькими способами, но они работают не во всех сценариях (это примеры для самого левого):

SELECT * FROM nodes
  WHERE position = 'LEFT' 
    AND number_of_children < 2
  HAVING `right` = `left` + 1
  ORDER BY element.`left` ASC
  LIMIT 1;

Или этот, он определенно находит решение, но также находит некоторые ложные: 

SELECT * FROM nodes AS element
  JOIN nodes AS upline ON element.parent_id = upline.id
  WHERE upline.position = 'LEFT'
    AND element.position = 'LEFT'
    AND element.number_of_children < 2
  ORDER BY element.`left` ASC;
...