Структуры данных на практике. Глава 9: Двоичные деревья поиска

[vvbob]

Ну, в сущности ответ был понятен еще после прочтения первых строк, Теория это хорошо и правильно, но реальное железо вносит свои коррективы.

[SpiderEkb]

Слов много, слова правильные, но нет никакой новизны. Все очевидно. Двоичный поиск по отсортированному массиву - трудно (скорее даже невозможно) придумать что-то быстрее. Но все это пригодно только для "статических" (в смысле один раз заполнил, отсортировал, 100500 раз используешь - никаких добавлений и удалений) массивов. Т.е. хорошо для справочников которые формируются один раз при инициализации и потом многократно используются.

Когда же данные динамичны (массив постоянно меняется) затраты на поддержание его в отсортированном состоянии почти наверняка будут кратно превышать выигрыш в скорости поиска. И тут уже надо искать другие алгоритмы - деревья, скиплисты и т.п. - те, что проигрывая в скорости поиска будут выигрывать в скорости вставки и удаления без нарушения сортировки. Что в среднем даст выигрыш в общей скорости работы.