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

Question

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

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

Спасибо

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

Answer 1

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

Я думаю, что было бы проще использовать Splay Tree следующим образом. Для простоты каждое дерево содержит двух часовых: интервал A слева от всех остальных интервалов и интервал Z справа. Вставляя интервал I, добавьте предшественника I в H к корню дерева. Дерево выглядит как

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

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

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

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

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

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

---

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