Иерархическая структура

← →
vlv (2001-12-28 14:51) [0]

Как лучше хранить иерархическую структуру в памяти. Можно, конечно, использовать TTreeView, но мне не надо ее отображать, а TTreeView довольно тормозная.

← →
Builder (2001-12-28 15:14) [1]

Или пиши сам - тогда, как говорится, все в твоих пальцах, или могешь использовать только ту часть, которая тебе и нужна - TTreeNodes - на них строй свою структуру - и отображаться не будет.
Основное время отображение и занимает...

← →
vuk (2001-12-28 15:21) [2]

В принципе - ничего особо сложного. Каждый узел дерева (Node) можно представить как что-то типа того:

TNode = class
//это, я думаю, понятно
property Parent : TNode ... ;
property Children[index : integer]:TNode ...;
property ChildrenCount : integer ...;
property Data : .... ;

//это не обязательно, но иногда удобнее для обхода дерева,
//да и структуру дерева можно строить именно через эти
//свойства
//FirstChild - первый "ребенок" узла
property FirstChild : TNode...;
//NextSibling - следующий "родной брат"
property NextSibling : TNode...;

end;

все нужные операции (добавление/удаление элементов), я думаю, очевидны.

Если объекты по каким-то причинам не устраивают, то можно все сделать на record"ах.
Для удобства все элементы дерева можно хранить в линейном массиве - это иногда упрощает обход элементов.

← →
Ura (2001-12-28 15:23) [3]

Вариант хранения
1. Список объектов ID,Pointer,Name и тд.
2. Список связей ID_parent,ID_child + доп параметры
Минусы: 1. Удаление, добавление объектов - перелапатить все
2. Удаление, добавление, перемещение связей - перелапатить опять все...
Можно еще сделать индексы (+ доп обработка) но скорость поиска возрастает
Работает нормально до 200 объектов (больше не проверял)

← →
vlv (2001-12-28 15:28) [4]

Всем спасибо. Учту. Я думаю, для сохранения / восстановления узлов главный объект нужно наследовать от TPersistent, там есть работа с потоками.

А вообще, я думал, то, чем я собираюсь заниматься, старо как мир и все классы давно написаны.

← →
vuk (2001-12-28 15:33) [5]

to Builder:
TTreeNodes без TTreeView не работают - завязано по реализации.

← →
Yuri-7 (2001-12-28 18:18) [6]

Не мудри особо. Возьми обычный TList, если надо с сортировкой, то TSortList, и храни там record-ы с родительскими, дочерними и, вообще с какими хочешь ссылками.

← →
Aleksandr (2001-12-28 18:48) [7]

Кстати, я в свое время делал компоненту, в которой данные из линейной таблицы (ID, ParentID...) надо было обрабатывать в виде дерева... Тоже сначала пытался через древовидный объект собачиться, пока не обнаружил, что для того же TreeView итемы все равно линейно хранятся... Так что Yuri-7 прав - лучше всего List, или создать TSortedCollection от TCollection... процедура сортировки достаточно примитивна...

← →
Юрий Зотов (2001-12-28 18:49) [8]

Посмотрите в MSDN интерфейс IXMLDOMDocument. Там действительно уже все реализовано, а поддержка живет в самой Windows (библиотека MSXML.dll - можно посмотреть средствами Delphi, как TLB).

Пишем:

var
MyTree: IXMLDOMDocument;
...

MyTree := CoDOMDocument.Create;

И далее пользуемся методами интерфейса.

← →
vuk (2001-12-28 19:02) [9]

to Yuri-7 & Aleksandr:
С линейными списками нужно поосторожнее, т.к. хранение элементов дерева в в таком виде при большом количестве этих элементов приведет к тормозам, т.к. каждое добавление элемента будет вызывать перераспределение памяти этого списка с последующим копированием.

to Юрий Зотов:
Использовать DOM модель для работы с деревьями это (ИМХО) как из пушки по воробьям стрелять...

← →
y-soft (2001-12-28 22:26) [10]

>vuk ©

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

Существуют и другие классические реализации subj со своими достоинствами и недостатками

Кое-что по проблеме можно прочитать, например, в

Род Стивенс. "Delphi. Готовые алгоритмы" ДМК, М., 2001
ISBN 5-94074-106-1

← →
Иван Шихалев (2001-12-28 22:43) [11]

Честно говоря, я бы отослал автора вопроса к классике (Кнут, Кормейн-Лейзерсон-Риверс и т.д.) Если не усложнять задачу, то ничего лучше собственной древовидной структуры не придумать (или ничего хуже :))).

← →
vuk (2001-12-28 22:53) [12]

to y-soft:
Насколько я понял, предлагается хранить все элементы списка в одном массиве. Это вполне нормальное решение, но только для случая, когда элементов не много. А если еще у в каждом узле отдельный список child"ов хранить в виде TList"а, то это может просто привести к излишним затратам памяти.

← →
y-soft (2001-12-29 09:51) [13]

>vuk ©
Я только хотел сказать, что для разных задач и решения могут быть разные, и у классиков они давно проработаны и просчитаны. Полностью согласен с Иваном Шихалевым ©, что часто целесообразно написать свой класс, основываясь на существующих алгоритмах - сам именно так и поступаю

>Юрий Зотов ©
Использование парсера XML для таких задач нежелательно хотя бы потому, что MSXML.dll появилась, начиная с IE4, т.е. в той же NT4 изначально отсутствует

← →
SergVlad (2001-12-29 10:08) [14]

Кроме всего прочего, необходимо учитывать для каких целей создается иерарх. структура (дерево).
Так,для поиска, весьма эффективными являются сбалансированные AVL-деревья (Адельсон, Вельский, Ландиса).

← →
sky3d (2001-12-29 10:15) [15]

2vuk : Смотря как представлять загрузку дерева, например, у меня элементы дерева хрянятся в лин. массиве структур (в файле) и загрузка и сохранение дерева с числом до 100 тыс. элементов происходит очень быстро, не говоря уж о 5-10 тысячах.
Основные тормоза в следующем :
- Использование AbsoluteIndex
- Добавление к родителю (по конкретному индексу) детей..

Лечится это рекурсивным добавлением детей (как при обходе TTreeNode.AbsoluteIndex), а также представление данных в массиве структур тоже в порядке обхода дерева.
Т.е. добавляем не сразу всех детей к родителю, а если у ребенка тоже есть дети, то первого и потом для добавленного аналогично... - я думаю понятен принцип рекурсии.

← →
vuk (2001-12-29 14:50) [16]

to sky3d:
Все зависит от того, важен ли порядок следования узлов в линейном массиве. Если нет, то все достаточно просто.
Если да, то операция добавления узла несколько усложняется. Опять же, если дерево загружается один раз и не модифицируется то все просто. А теперь представьте что последовательность важна, дерево уже загружено, и после этого идут операции вставки...

Да и в любом случае, линейная структура хороша только для произвольного доступа к ее элементам. Но часто ли оно необходимо? Скорее всего, чаще приходится использовать последовательный перебор. А для этого достаточно и ссылочной структуры типа дерева или списка (только не того, что TList зовется, а настоящего, одно- или двухсвязного). К тому же скорость обычной вставки в ссылочных структурах, в отличие от линейных, не зависит от количества элементов.

К стати о птичках... Тут писали что в TTreeView элементы хранятся линейно. Дык вот:

function TTreeNode.GetItem(Index: Integer): TTreeNode; begin Result := GetFirstChild; while (Result <> nil) and (Index > 0) do begin Result := GetNextChild(Result); Dec(Index); end; if Result = nil then TreeViewError(SListIndexError); end; function TTreeNode.GetNextChild(Value: TTreeNode): TTreeNode; begin if Value <> nil then Result := Value.GetNextSibling else Result := nil; end; function TTreeNode.GetNextSibling: TTreeNode; begin with FOwner do Result := GetNode(TreeView_GetNextSibling(Handle, ItemId)); end;

Так что все равно получается хождение по дереву для эмуляции прямого доступа. Эффективность такого подхода при переборе с использованием индексного доступа представляете? :o(

← →
sky3d (2001-12-29 15:07) [17]

>А теперь представьте что последовательность важна, дерево уже
>загружено, и после этого идут операции вставки...

Ну и работайте с деревом, а массив используйте при сохранении изменений или загрузки дерева.
Почему же нельзя переформировывать массив при сохранении изменений, зачем вставлять в середину массива данные сразу при вставке узла ?

>линейная структура хороша только для произвольного доступа к ее >элементам
Почему же по ней нельзя сделать перебор при желании ?

← →
vuk (2001-12-29 15:31) [18]

to sky3d:
>Почему же по ней нельзя сделать перебор при желании ?
Я немного не верно выразился. Линейная структура хороша при прямом индексном доступе. При переборе она тоже эффективна. Не эффективна она при массовых операциях вставки и (в меньшей степени) удаления.
Что же касается перебора элементов дерева или списка, то при правильном обходе дерева обычный итератор по ссылочной структуре обеспечит вполне нормальную скорость перебора. Она будет немного меньше скорости прохода по линейному списку (если его хранить, а не эмулировать). Однако затраты на поддержание правильной структуры дерева в случае использования только ссылочной структуры намного меньше.

>Ну и работайте с деревом, а массив используйте при сохранении
>изменений или загрузки дерева.
Способ сериализации (хранения данных) дерева - это отдельный вопрос. Хранить дерево в массиве можно, однако в любом случае придется дополнительно сохранять связи элементов. Здесь все зависит от свойств самого хранилища. Если это какое-либо объектное хранилище, то массивы здесь вовсе не нужны, поскольку, скорее всего, можно каким-то образом хранить вложенные объекты. Если же используется, например, реляционная БД, то соответственно, нужно и методы сохранения связей использовать другие.

← →
sky3d (2001-12-29 15:48) [19]

>Хранить дерево в массиве можно, однако в любом случае придется >дополнительно сохранять связи элементов.

У меня в массиве хранится данные по тек. эл-ту и количество детей - этого вполне достаточно для рекурсивного построения дерева. Связи получаются сами собой, т.е. ЯВНО код(индекс) родителя я не храню, поэтому при построении дерева массив просматривается 1 раз по порядку, т.е. в один проход от 0 до Length-1 без скачков назад на родителя и прочих мотыляний.

Иерархическая структура Найти похожие ветки