Любая причина, по которой я должен использовать дерево AVL, а не использовать двоичный поиск в массиве, когда я заранее знаю количество элементов, которые должны быть сохранены, и имеет фиксированный размер. Также должна выполняться только операция поиска ?? Есть ли какая-либо другая структура данных или алгоритм, который лучше их обоих для целей поиска?
Как правило, ваше решение для двоичного поиска будет работать лучше, если вы храните массив в непрерывном фрагменте памяти, а дерево AVL будет использовать разреженный набор узловых объектов, что приведет к плохой локализации пространственного кеша.
В зависимости от типа данных вы можете использовать поиск с интерполяцией, который обеспечит производительность O(loglogn)
- хотя это увеличит временную сложность наихудшего случая до O(n)
. Это используется, если данные следуют равномерному распределению, поэтому вы должны основывать индекс предположения не на середине, а скорее на позиции ожидал. Другой вариант - иметь хеш-таблицу, которая обычно является O(1)
get, которая с хешированием Cuckoo гарантирует O(1)
, если она создана правильно, независимо от коллизий.