Re: балансировка бинарного дерева

From

Protopopov Michael ()

To

Spiridonov Ed

Date

2003-01-05T10:29:24Z

Area

RU.ALGORITHMS

From: "Protopopov Michael" <mkp@ist.ru>


"Spiridonov Ed" <Spiridonov.Ed@p55.f9.n5059.z2.fidonet.org> wrote in message
news:1041690263@p55.f9.n5059.z2.ftn...
> Здравствуй All!
>
> какие алгоритмы существуют?
>
> поясню задачу - есть небольшой движок бд, используемый на слабеньких по
> сегодняшним меркам машинах (палм - 33mhz процессор motorola 68k, 8b ram).
в нем
> для индексов используются бинарные деревья (сами индексы используются для
> сортировки, поиска, фильтрации).
> хочется в фоне производить балансировку этого дерева. самый простой
вариант
> (перестроить дерево заново) не подходит - он требует больших затрат
времени и
> памяти.
>
ИМХО для этой задачи хорошо подходят расширяемые деревья (splay trees).
Это, в некотором роде, обобщение LRU цепочек, используемых для организации
кэша (когда элемент, к которому осуществляется доступ переносится в начало
списка)

Суть заключается в том, что узел, к которому происходит доступ (или который
вставляется), переносится в корень дерева. Во время его продвижения к корню
дерева, заодно осуществляется некоторая перебалансировка дерева вдоль путь
переноса.

Для этих деревьев доказано, что, при сравнительно небольших затратах, они
обеспечивают достаточно хорошую "взвешенную" балансировку дерева (т.е. с
учетом частоты обращения к узлу).

Подробности лучше искать в и-нете.



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