Структура данных для операций быстрого набора
Я работаю над реализацией межсервисного дерева двоичного поиска на C# Хансоном и Чаабуни. Вкратце, это структура данных для динамических коллекций интервалов, которая позволяет быстро находить интервалы, которые перекрывают точку. Структура данных представляет собой расширенное дерево двоичного поиска (BST), использующее схему балансировки AVL.
Каждый узел в дереве содержит три набора интервалов. При выполнении вращений нам нужно выполнить множество операций над множествами, чтобы сохранить инвариант. Нам нужна поддержка для итерации интервалов в множестве, сложения и вычитания множеств и пересечений множеств. Если коллекция содержит повторяющиеся интервалы (интервалы, которые имеют одинаковые конечные точки, но не являются одним и тем же объектом), они будут содержаться в одинаковых наборах.
Мы должны быть в состоянии выполнять эти операции над множествами как можно быстрее - это наш ограничивающий фактор атм. Существуют ли какие-либо структуры данных, которые эффективно поддерживают эти операции?
Информация о бонусе:
- Интервал состоит из низкой и высокой конечной точки. Это все, что мы знаем о них.
- Мы можем хэшировать эти конечные точки, но дублирующий интервал с одинаковыми конечными точками, естественно, будет иметь одинаковый хэш-код.
- Интервалы дифференцируются по эталонному равенству.
- Мы можем отсортировать конечную точку, но дублированные интервалы с одинаковыми конечными точками, естественно, будут иметь одинаковый порядок сортировки.
- У нас нет другой информации, которую можно было бы использовать для хеширования или сортировки.