Быстрый поиск в Tree по значению TPointer

← →
AndbyOne © (2002-09-04 11:53) [0]

Проблема стоит достаточно остро: найти ветку в Tree по значению (integer) которое хранится в Pointer ветки. Значение уникально(ID из базы). Простой перебор с сравниваем не подходит, т.к. в дереве 500000 записей и он 10 мин только перебирает. Может у кого будут, какие-нить идеи по оптимизации поиска. Буду очень признателен.

← →
MBo © (2002-09-04 12:31) [1]

Если нельзя дерево отсортировать по этому значению, то увы...

← →
Макс Черных © (2002-09-04 16:55) [2]

Можно попробовать создать некое подобие индекса,
это правда хорошо прокатывает тольео когда дерево не изменяется
часто.

1. Делаем record с полями ID и TTreeNode.
2. При построении дерева в момент создания node
заполняем record и добавляем его в список - индекс.
Можно например TList использовать, только не
динамический массив - медленно на больших обьемах.
3. Сортируем этот лист по полю ID
4. Ну и обычный поиск половинным делением

← →
AFrolov © (2002-09-04 17:00) [3]

> 4. Ну и обычный поиск половинным делением
Лучше не половинный а т.н. "золотое сечение" - скорость в среднем выше.

Если вы строите дерево по данным из базы, то вероятно ваша база имеет примерно такую структуру:
ID - идентификатор
ParentID - идентификатор элемента верхнего уровня
... - другие поля.

Если база имеет такую структуру, то с помощью запросов к базе можно получить ID элементов верхнего уровня, т.е.
ID lev0
ID lev1
ID lev2
ID lev3 - искомый элемент.
Затем в дереве среди TreeNode нулевого уровня находите тот, у которого Date^ равно ID lev0. После этого просматриваете его Child в поиках TreeNode c ID lev1, и так далее пока не найдете искомый элемент. Скорость поиска будет зависеть от разветвленности дерева. Чем меньше элементов в ветви, а соответственно больше ветвей, тем быстрее поиск.

А Б-Деревья тебя не устраивают? Они как раз под эту задачу подходят.

Быстрый поиск в Tree по значению TPointer Найти похожие ветки