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

From

Spiridonov Ed (2:5059/9.55)

To

All

Date

2003-01-04T14:23:56Z

Area

RU.ALGORITHMS

Здравствуй All!

какие алгоритмы существуют?

поясню задачу - есть небольшой движок бд, используемый на слабеньких по
сегодняшним меркам машинах (палм - 33mhz процессор motorola 68k, 8b ram). в нем
для индексов используются бинарные деревья (сами индексы используются для
сортировки, поиска, фильтрации).
хочется в фоне производить балансировку этого дерева. самый простой вариант
(перестроить дерево заново) не подходит - он требует больших затрат времени и
памяти.

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

в общем-то алгоритм уже прорисовывается (взять вершину, которая должна быть в
центре, поставить её туда, повторить рекурсивно для левого и правого
поддеревьев), но наверняка это уже решено кем-нибудь красиво.

почему не используются avl-деревья или b-tree:
 - b-tree оптимизированно под внешние носители, при размещении данных в озу
двоичное дерево ИМХО намного эффективнее; у avl-деревьев большие накладные
расходы на модификацию дерева
 - необходимо модифицировать алгоритмы работы с этими деревьями, чтобы
поддерживать актуальной всю необходимую мне информацию (см ниже)
 - проблема сбалансированности стоит не очень остро - данные подготавливаются
на обычном пк и в исходном положении все деревья сбалансированы

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

                    С уважением, Ed.

--- Ничего особенного
 * Origin: My tiny station, Penza (2:5059/9.55)