У вложенных множеств есть интересное свойство, которое мы можем использовать для поиска всех общих предков. Свойство состоит просто в том, что все дочерние элементы узла имеют левый угол, который больше, чем его левый, И правый, который меньше, чем его правый.
Это означает, что нам нужно найти узлы, которые имеют левую и правую границу, содержащую ВСЕ интересующие нас узлы. Мы можем сделать это, используя наш набор узлов, которые нам нужны, чтобы установить границы, которые мы ищем. Мы можем сделать это довольно легко следующим образом:
Возьмите нижний левый и верхний правый из всех узлов, для которых вы хотите иметь общего предка. В этом случае нижний левый из выбранных вами узлов равен 3 для мастей, а самый верхний правый — 21 для женских. Затем вы можете выполнить запрос предков в этом едином пространстве узлов 3:21.
В этом случае вы должны искать набор узлов, где левое ‹ 3 и правое > 21. Это даст вам набор всех общих предков. В этом случае единственным совпадением является одежда. 1 на одежде меньше 3, а 22 больше 21.
Если у вас есть несколько общих предков, но вы хотите найти самого низкого, вы можете отсортировать их по левому столбцу в порядке убывания и выбрать первого.
Это может выглядеть примерно так в SQL. Я использую T-SQL, поэтому «верхний 1» может быть пределом 1 или чем-то еще в вашем вкусе SQL.
select top 1 * from Clothing where [left] < 3 and [right] > 21 order by [left] desc
person
Devin
schedule
21.04.2017
