геометрический поиск в красном черном двоичном дереве поиска

Question

В настоящее время я реализую дерево черного дерева с красным черным для поиска геометрических интервалов. Я сохраняю в дереве сегменты, содержащие начальную точку и endpoinit, где начальная точка является ключевым элементом дерева. Моя забота заключается в том, чтобы иметь возможность сохранять в сегменты дерева, у которых есть повторяющаяся начальная точка (или, если хотите, с одним и тем же ключом). Это разновидность мультимапа C++ для геометрического поиска. Решение, которое я придумал, - это: для каждой записи, у которой есть дубликаты ключей, сохраните список (или вектор) сегментов с соответствующими дублирующими ключами. Проблемы, которые я вижу при таком подходе, двоякие: 1. Это уменьшает эффективность поиска, если имеется большое количество дубликатов ключей. 2. Я буду использовать больше памяти для хранения дубликатов ключей.

Мой вопрос: есть ли другой способ реализовать это более эффективно?

Answer 1

Я бы порекомендовал не, чтобы использовать обычное двоичное дерево поиска! Вместо этого взгляните на interval trees: Я подозреваю, что эта структура вам подходит лучше.