> > Сейчас, в качестве основы, для индекса юзается AVL-дерево. Но я тут на > > днях обнаружил у себя одну книженцию, в которой описаны "кучи" (это не > > те, которые управляют динамической памятью, а другие). Идея меня > > зацепила - нет накладных расходов на хранение указателей left-right- > > parent. Только сами данные. И, вроде как, поиск идет двоичный и есть > > сбалансированность. > > Что ещё за кучи? Можно ссылку в инете посмотреть? А то тут сидишь, > понимаешь, от жизни отстал совсем.
Книженция называется "Жемчужины программирования". Там был представлено такое описание. Для хранения данных используется массив. Упорядоченность элементов такая [i] > [i+2^N] [i] < [i+2^(N+1)] Я за точность вышесказанного не ручаюсь - у меня во время чтения моск периодически отключался :) Там же были приведены алгоритмы балансировки. Балансировка после добавления нового элемента точно приводилась. Коваленко Дмитрий.
