Re: [Q]

From

Andrew Ezhguroff ()

To

Sergei Emantayev

Date

2002-09-27T21:38:37Z

Area

RU.ALGORITHMS

From: "Andrew Ezhguroff" <eandr@com2com.ru>

Привет! "Sergei Emantayev" <sergeie@ectel.com>  сообщил(а):

 SE> Суть в том, что мне надо устроить очередь, отсортированную по
 SE> некоторому признаку. Сообщения поступают в очередь в _почти_
 SE> правильном порядке, так что я не ожидаю много операций поиска. Но все
 SE> таки хочется подстраховаться на крайний случай...

Если данные не отсортированы ("почти отсортировано" здесь не проходит), то и
массиве поиск займет O(N).

 SE> Список видится мне наиболее оптимальной структурой, поскольку операции
 SE> вставки / удаления с конца - это О(1).

И время поиска O(N).

 SE> А в бинарном дереве - О(log N)

Но и поиск - O(log(N))

 SE> , к тому же надо каждый раз балансировать.

Балансировать надо бинарные деревья. B-tree в балансировке не нуждаются.

С уважением, Андрей.



-- 
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
 * Origin: Talk.Mail.Ru (2:5020/400)