|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Andrey Tarasevich 2:5020/400 24 Feb 2002 02:33:59
To : ‘ҐаЈҐ© „ў®ап楢
Subject : Re: Построение дерева
--------------------------------------------------------------------------------
"Сергей Дворянцев" wrote:
>
> > > ...>
> > > Index - уникальные значения, а Parent - значение Index элемента-предка
> > > Hужен быстрый алгоритм формирования дерева из этих элементов.
> > > Может кто пнет в нужном направлении?
> > > ...
> >
> > Все-таки что такое 'Parent' - это значение 'Index' элемента-предка или
> > индекс этого предка во входном массиве?
>
> Parent - содержит значение IndexKey предка, а значение IndexKey - не
> совпадает с индексом объекта в массиве.
> Если-бы не последнее обстоятельство - дерево строилось-бы за один проход.
> ...
Ага. То есть на корректные входные данные налагается следующее
требование:
Если есть элемент с Parent == N, то обязательно есть один и только один
элемент с Index = N
(Только для корневого элемента это требование может не выполняться.
Кстати, а чему равно значение 'Parent' в корне?)
Если у тебя есть возможность эффективно отобразить значения 'Index' на
указатели на узлы создаваемого дерева - то задача решается следуюшим
алгоритмом:
1. Берем очередной элемент E входного массива.
2. Вычисляем узел S, являюшийся образом значения E.Index. Если такового
нет, то создаем его.
3. Вычисляем узел P, являюшийся образом значения E.Parent. Если такового
нет, то создаем его.
4. Связываем узлы P и S ссылкой: узел S яляется сыном узла P в дереве.
5. Идем на шаг 1.
(Если корневой элемент немедленно распознаваем, то для него шаги 3 и 4
делать не надо).
Если значения 'Index' лежат в некотором достаточно плотно заполненном
ими диапазоне, то требуемое отображение можно представить прямой
таблицей. Тогда задача решится за время O(n). В противном случае можно
использовать ассоциативный массив и получить время O(n log n).
Best regards,
Андрей.
--- ifmail v.2.15dev5
* Origin: good enough (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
