Re: [Q] Быстpый поиск в отсоpтиpованном списке

From

Oleg Shatalov ()

To

Andrey Belyakov

Date

2002-09-18T23:47:34Z

Area

RU.ALGORITHMS

From: Oleg Shatalov <oleg@lakes-environmental.com>


Привет, Андрей!

> Хммм... Осталось выяснить, как ты собираешься получить L[size/2]
> в _списке_, пусть даже двунаправленном и отсортированном...  :)

Дело в том, что списки можно представить как динамический массив и доступ к
каждому элементу происходит по его индексу без каких-либо дополнительных
затрат времени.

При этом, такая организация выгоднее бинарного дерева за счет того, что не
нужно хранить ссылки на дочерние ветви, т.е. получается экономия памяти.
Единственный минус - при вставке элемента в такой массив приходится
перемещат все элементы, стоящие после него.

Пока,
Олег.

--- ifmail v.2.15dev5
 * Origin: Golden Triangle On Line Inc. (2:5020/400)