Алгоритм дерева интервала, который поддерживает слияние интервалов без перекрытия
Я ищу алгоритм дерева интервала, подобный красно-черному дереву интервала в CLR, но это поддерживает слияние интервалов по умолчанию так, чтобы никогда не было никаких перекрывающихся интервалов.
Другими словами, если бы у Вас было дерево, содержащее два интервала [2,3] и [5,6], и Вы добавили интервал [4,4], то результатом было бы дерево, содержащее всего один интервал [2,6].
Спасибо
Обновление: вариант использования, который я рассматриваю, вычисляет переходное закрытие. Наборы интервала используются для хранения наборов преемника, потому что они, как находили, были довольно компактны. Но если Вы представляете наборы интервала так же, как связанный список, я нашел, что в некоторых ситуациях они могут стать довольно большими, и следовательно так делает время, требуемое найти точку вставки. Следовательно мой интерес к деревьям интервала. Также может быть довольно большое слияние одного дерева с другим (т.е. набор ИЛИ операция) - если оба дерева являются большими затем, может быть лучше создать новое дерево с помощью inorder обходы обоих деревьев, а не повторенные вставки каждого интервала.
1 ответ
Я вижу проблему в том, что вставка большого интервала может стереть большой кусок дерева, что затрудняет восстановление красно-черных инвариантов.
Я думаю, что было бы проще использовать растягиваемое дерево следующим образом. Для простоты каждое дерево содержит два стража, интервал 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 - количество узлов дерева (это можно доказать, исследуя потенциальную функцию развернутого дерева и выполняя много алгебр).
Я должен добавить, что существует естественное рекурсивное слияние дерева с деревом путем вставки корня одного дерева и последующего слияния левого и правого поддеревьев. Я не знаю, как анализировать это прямо.