Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

Быстрый поиск в Tree по значению TPointer [D6, Win95/98]

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

a413 (2002-09-04 20:15:00) [1]
А Б-Деревья тебя не устраивают? Они как раз под эту задачу подходят.

TTCustomDelphiMaster (2002-09-04 20:04:00) [2]
Если вы строите дерево по данным из базы, то вероятно ваша база имеет примерно такую структуру:
ID - идентификатор
ParentID - идентификатор элемента верхнего уровня
... - другие поля.

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

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

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

Макс Черных (2002-09-04 16:55:00) [4]
Можно попробовать создать некое подобие индекса,
это правда хорошо прокатывает тольео когда дерево не изменяется
часто.

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

MBo (2002-09-04 12:31:00) [5]
Если нельзя дерево отсортировать по этому значению, то увы...

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »