Ответ 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 и делая много алгебры).
Я должен добавить, что существует естественное рекурсивное слияние дерева к дереву, вставив корень одного дерева, а затем сменив левое и правое поддеревья. Я не знаю, как его анализировать.