Могу ли я переформулировать ваши вопросы, чтобы они были более ясными? <br/><br/> 1. Имеют ли сплей-деревья высокую эффективность при работе с запросами, характеризующимися горбатым нормальным распределением по данным? <br/> 2. Насколько целесообразно использовать сплей-деревья в сравнении с отсортированными массивами в случае, когда операции модификации данных не планируются, но имеется нормальное распределение запросов с явным пиком? В каких случаях использование сплей-деревьев предпочтительнее?
Да, конечно! Вот переформулированные вопросы: 1. Как эффективно сплей-деревья работают с запросами, которые имеют горбатое нормальное распределение данных? 2. В каких случаях использование сплей-деревьев предпочтительнее отсортированных массивов, если операции модификации данных не предполагаются, но есть явный пик в нормальном распределении запросов?
1) Нет, сплей дерево всегда работает за log n амортизированно. Его лучше использовать как временную структуру данных. То есть на серверах для поиска пользователей оно иногда будет долго работать (а это недопустимо), но в сумме быстро. Почитайте про то что такое амортизированный алгоритм.
2) Нет, отсортированный массив занимает меньше места и поиск происходит быстрее.
https://ru.m.wikipedia.org/wiki/%D0%90%D0%BC%D0%BE...
Так же если хотите ускорить двоичный поиск, то можно использовать интерполиционный поиск (е
это работает только для массивов) https://ru.m.wikipedia.org/wiki/%D0%98%D0%BD%D1%82...