1) Нет, сплей дерево всегда работает за log n амортизировано. Его лучше использовать как временную структуру данных. То есть на серверах для поиска пользователей оно иногда будет долго работать (а это недопустимо), но в сумме быстро. Здесь написано, что такое амортизированный алгоритм
https://ru.m.wikipedia.org/wiki/%D0%90%D0%BC%D0%BE...
2) Нет, отсортированный массив занимает меньше места и бинарный поиск происходит быстрее.
Так же если хотите ускорить двоичный поиск, то можно использовать интерполиционный поиск (е
это работает только для массивов)
https://ru.m.wikipedia.org/wiki/%D0%98%D0%BD%D1%82... 