Структура данных, вроде АВЛ-дерева

← →
partizan (2006-08-07 19:21) [0]

Есть набор елементов, а каждого елемента есть ранг (некоторое целое число).

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

Новые елементы добавляются всегда с наибольшим рангом (на 1-е место).
Удаляться может любой елемент.
Так же любой елемент может "поднятся" на 1-е место

Думаю реализовать АВЛ-деревом. Для каждой вершины хранить количество вершин в правом поддереве, тогда количество вершин с рангом больше заданной можно легко посчитать за 1 проход от этой вершины к корню дерева.

Но межет есть идеии, как это реализовать по-проще?

← →
Мефисто (2006-08-07 20:16) [1]

"Фундаментальные алгоритмы и структуры данных в Delphi" Джулиан Бакнелл (один из разработчиов в компании TurboPower).
Исходники к книге не прилагаются, только на сатах издательства. К примру тут:
http://materials.diasoft.kiev.ua/alg_delphi/alg_delphi.zip

← →
partizan (2006-08-07 20:49) [2]

Мне исходники не нужны, мне идея нужна.
Но всеравно спасибо, что хоть кто-то откликнулся

← →
Мефисто (2006-08-07 20:53) [3]

А я тебе на книгу намекнул ;)

Твоя задача решается с помощью моего юнита Arrays (смюна моем сайте из анкеты).
Достаточно будет просто завести какой-то из TSortedArray. Логический индекс элемента и будет твоим искомым числом.
Насколько это будет эффективно для твоего случая - не знаю, т.к. мало данных о твоей задаче. Работать должно быстро, но возможно, что для твоего конкретного случая можно придумать что-то и по-быстрее.

Структура данных, вроде АВЛ-дерева Найти похожие ветки