|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Spiridonov Ed 2:5059/9.55 04 Jan 2003 15:23:56
To : All
Subject : балансировка бинарного дерева
--------------------------------------------------------------------------------
какие алгоритмы существуют?
поясню задачу - есть небольшой движок бд, используемый на слабеньких по
сегодняшним меркам машинах (палм - 33mhz процессор motorola 68k, 8b ram). в нем
для индексов используются бинарные деревья (сами индексы используются для
сортировки, поиска, фильтрации).
хочется в фоне производить балансировку этого дерева. самый простой вариант
(перестроить дерево заново) не подходит - он требует больших затрат времени и
памяти.
поэтому хочется найти некий итерационный алгоритм (многозадачности нет, так что
необходимо при появлении какого-либо события как можно быстрее остановить
балансировку и продолжить работу).
в общем-то алгоритм уже прорисовывается (взять вершину, которая должна быть в
центре, поставить её туда, повторить рекурсивно для левого и правого
поддеревьев), но наверняка это уже решено кем-нибудь красиво.
почему не используются avl-деревья или b-tree:
- b-tree оптимизированно под внешние носители, при размещении данных в озу
двоичное дерево ИМХО намного эффективнее; у avl-деревьев большие накладные
расходы на модификацию дерева
- необходимо модифицировать алгоритмы работы с этими деревьями, чтобы
поддерживать актуальной всю необходимую мне информацию (см ниже)
- проблема сбалансированности стоит не очень остро - данные подготавливаются
на обычном пк и в исходном положении все деревья сбалансированы
если кому интересно - в каждой вершине дерева хранится:
- сслыки на потомков слева и справа (вершины левого и правого поддерева)
- количество вершин в левом и в правом поддереве (чтобы можно было быстро
узнать порядковый номер вершины)
- ссылки на предыдущую и следующую вершины (для быстрого последовательного
обхода дерева - от этого можно и отказаться).
С уважением, Ed.
--- Hичего особенного
* Origin: My tiny station, Penza (2:5059/9.55)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
