Здравствуйте, c-smile, Вы писали:

CS>Приводится случай когда O(N) lookup кроет O(1) как бык овцу[/url].

Поэтому Кнута и ко надо читать с осторожностью — хоть парни и толковые, но инфа несколько устарела, если не учитывать устройство современного процессора (всякие кеши, предсказание переходов), то можно легко напороться на то, что алгоритм с худшей асимптоматикой внезапно уделывает алгоритм с хорошей. Ну и вообще стоит прикидывать стоимость операций — внезапно может оказаться, что при вставке на небольшом массиве со сдвигом, чтобы сохранить упорядоченность и бинарный поиск, уделывают деревья только так.