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