Наиболее эффективная структура данных: быстрая сортировка вставки, поиск ближайшего значения

Question

В основном:

• Быстрая сортированная вставка.
• Возвращает позицию, в которой элемент будет вставлен, если он не найден в структуре данных.

Массив с бинарным поиском удовлетворяет моему второму требованию, но он все еще слишком медленный для вставки. Какое решение может работать лучше всего?

Answer 1

Красно-черные деревья и пропускают списки удовлетворяют ваши требования, среди прочего. Для примера в C ++ посмотрите std :: set, std :: map и т. Д. И их методы lower_ / upper_bound и equal_range.

Answer 2

Двоичное дерево поиска.

Answer 3

Многие варианты дерева поиска соответствуют вашим требованиям.Я бы использовал 2-3 дерева или, может быть, трепу, если бы мне было лень.