Структура данных для операций быстрого набора ⇐ C#

[Anonymous]

Я работаю над реализацией интервального двоичного дерева поиска на C#, разработанной Хэнсоном и Чаабуни. Короче говоря, это структура данных для динамических коллекций интервалов, которая позволяет быстро находить интервалы, перекрывающие точку. Структура данных представляет собой расширенное двоичное дерево поиска (BST) с использованием схемы балансировки AVL.

Каждый узел в дереве содержит три набора интервалов. При вращении нам нужно выполнить множество операций над множествами, чтобы сохранить инвариант. Нам нужна поддержка перебора интервалов в наборе, сложения и вычитания наборов и пересечений наборов. Если коллекция содержит повторяющиеся интервалы (интервалы, которые имеют одинаковые конечные точки, но не являются одним и тем же объектом), они будут содержаться в одних и тех же наборах.

Мы должны иметь возможность выполнять эти операции над множеством как можно быстрее — это наш ограничивающий фактор. Существуют ли какие-либо структуры данных, которые эффективно поддерживают эти операции?

Дополнительная информация:

• Интервал состоит из нижней и верхней конечной точки. Это все, что мы о них знаем.
• Мы можем хэшировать эти конечные точки, но повторяющийся интервал с теми же конечными точками, естественно, будет иметь один и тот же хеш-код.
• Интервалы различаются по принципу равенства ссылок.
• Мы можем сортировать конечные точки, но повторяющиеся интервалы с одинаковыми конечными точками, естественно, будут иметь одинаковый порядок сортировки.
• Никакой другой информации, которую можно было бы использовать для хеширования или сортировки, у нас нет.

Подробнее здесь: https://stackoverflow.com/questions/196 ... operations