Re: Обработка деревьев

From

Dmitriy Krylov ()

To

Eduard Vatutin

Date

2002-11-01T01:22:50Z

Area

RU.ALGORITHMS

From: "Dmitriy Krylov" <krylov@mail.primorye.ru>

Привет, Eduard!
Вы писали to Serge Nozhenko on Wed, 30 Oct 2002 12:12:58 +0300:

 EV> Такой вариант у меня был. Только я до конца не решил, когда
 EV> сортировать: то ли при построении дерева, то ли перед поиском
 EV> поддерева. Что одно, что другое достаточно труднореализуемо (в
 EV> смысле ресурсоемко ;), а операций таких надо будет проводить
 EV> достаточно много (к примеру, среди 50 деревьев найти такую пару, в
 EV> которой одно дерево является поддеревом другого, модифицировать
 EV> набор деревьев (их станет на одно меньше) и опять то же самое, пока
 EV> будут находиться поддеревья).
 EV> Может есть еще какие задумки?

Имхо, стоит строить дерево, _расположенное_ в строке.

Т.е., "ссылочная" структура будет такая:

           [1]
           / \
         [2] [3]
         / \ / \

Где узлы расположены в памяти произвольно. А можно располагать их
не произольно, а последовательно, в одном массиве, который и будет строкой:


[1^2^3][2^n^k][3^l^m]   (здесь [] - узел, он же элемент массива, ^n - ссылка
на n-ый узел)

Правда, возникнут следующие проблемы:

1) Ссылку придется сделать относительной (текущего узла), т.е. первый узел в
примере будет выглядеть так: [1(1)(2)][2()()][3()()].

2) Непонятно еще как размещать деревья. Можно попробовать размещать их в
виде пирамиды (если дерево бинарное) - кстати, тогда ссылки (n) не
понадобятся, они сразу вычисляются; да и дерево будет заранее упорядочено.

Зато появляется куча бонусов:

1) Компактное размещение в памяти (=> меньшая фрагментация, легко из/в файла
читать и т.п.),
2) Быстрое копирование/построение деревьев/поддеревьев
3) Быстрое сравнение
4) Ну и прочие ништяки

Удачи!
__________________________________________________
--{ Dmitriy Krylov aka "Abulafia"   }-------------
--{ mailto: krylov@mail.primorye.ru }-------------


--- ifmail v.2.15dev5
 * Origin: Demos online service (2:5020/400)