Найти самого низкого общего предка во вложенном множестве

Question

Я ищу способ найти самого низкого общего предка во вложенном множестве, используя одно уравнение.

Например, из изображения по адресу: https://commons.wikimedia.org/wiki/File:Clothing-hierarchy-traversal.svg

LCA между костюмами и женщинами - это одежда. Я мог бы использовать систему, основанную на уровнях, чтобы выяснить, где встречаются родители, но сценарий использования этого в разработке базы данных, поэтому повышение уровней будет пагубно влиять на производительность.

Я надеюсь, что смогу использовать один расчет, используя Костюмы (3:8) и Женщины (10:21), чтобы получить комбинацию (1:22) для одежды, то есть, если такое уравнение существует.

Answer 1

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

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

Возьмите самый нижний левый и самый верхний правый из всех узлов, для которых вы хотите общего предка. В этом случае самый нижний левый из выбранных вами узлов - 3 на костюмах, а верхний правый - 21 на женских. Затем вы можете выполнить запрос предка для этого унифицированного пространства узлов 3:21.

В этом случае вы будете искать набор узлов, где слева < 3 и справа> 21. Это даст вам набор всех общих предков. В этом случае единственный матч - одежда. 1 на одежде меньше 3, а 22 больше 21.

Если у вас есть несколько общих предков, но вы хотите наименьшего, вы можете отсортировать их по левому столбцу в порядке убывания и выбрать первого.

Это может выглядеть примерно так в SQL. Я использую T-SQL, так что "top 1" может быть пределом 1 или чем-то еще в вашем вкусе SQL.

select top 1 * from Clothing where [left] < 3 and [right] > 21 order by [left] desc