Ответ 1
Пока я видел примеры для вложенных наборов, я не видел много для вложенных интервалов, хотя теоретически это не должно быть трудно конвертировать из одного в другое. Вместо того, чтобы делать предварительный обход, чтобы обозначить узлы, выполните рекурсию ширины. Хитрость заключается в разработке наиболее эффективного способа маркировки n детей node. Так как node между a/b и c/d является (a + c)/(b + d), плохо обусловленная вставка (например, вставка детей слева направо), рискует создать тот же экспоненциальный рост значений индекса, например, с использованием полного материализованного пути. Нетрудно противодействовать этому эффекту - создавать новые индексы по одному, вставляя каждый в место, где создается самый низкий результирующий знаменатель.
Что касается снижения производительности, многое зависит от операций, которые вы намереваетесь сделать. Есть еще некоторые операции, которые потребуют полной перемаркировки всего дерева - методы вложенного набора или вложенного интервала работают лучше всего для структур, которые редко меняются. Если вы выполняете много структурных изменений в иерархии, с "стандартной" табличной структурой родитель-ребенок может быть проще работать. помните также, что некоторые операции (например, количество потомков) намного проще с целыми обозначениями вложенных множеств, чем интервальные методы.