Алгоритм дерева интервалов, который поддерживает слияние интервалов без перекрытия

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

Другими словами, если у вас есть дерево, содержащее два интервала [2,3] и [5,6], и вы добавили интервал [4,4], результатом будет дерево, содержащее только один интервал [2,6 ].

Обновление: пример использования, который я рассматриваю, вычисляет переходное закрытие. Наборы интервалов используются для хранения наборов преемников, поскольку они оказались довольно компактными. Но если вы представляете интервальные множества как связанный список, я обнаружил, что в некоторых ситуациях они могут стать довольно большими и, следовательно, время, необходимое для поиска точки вставки. Отсюда мой интерес к интервальным деревьям. Также может быть довольно много слияния одного дерева с другим (т.е. Операция set OR) - если оба дерева являются большими, то может быть лучше создать новое дерево, используя походные пути обоих деревьев, а не повторные вставки каждого интервала.

Ответы

Ответ 1

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

Я думаю, что было бы проще использовать дерево splay, как показано ниже. Для простоты каждое дерево содержит два часовых, интервал A слева от всех остальных интервалов и интервал Z справа. При вставке интервала I, splay I предшественника-to-be H в корень дерева. Дерево выглядит как

   H
  / \
...  X
    / \
  ... ...

Теперь отсоедините X и переместите I преемника J к корню.

   H       J
  /       / \
...     ... ...

В этот момент все интервалы, перекрывающиеся I, находятся в J левом поддереве. Отделите это поддерево и поместите все его узлы в свободный список, при необходимости I, если это необходимо. Сделайте I родительский элемент H и J

     I
    / \
   H   J
  /     \
...     ...

и продолжим наш веселый путь. Эта операция O (log n) амортизируется, где n - число узлов дерева (это можно доказать, исследуя потенциальную функцию splay tree и делая много алгебры).

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