ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Dmitriy Krylov                       2:5020/400     01 Nov 2002  02:22:50
 To : Eduard Vatutin
 Subject : Re: Обработка деревьев
 -------------------------------------------------------------------------------- 
 

 Привет, 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) Hепонятно еще как размещать деревья. Можно попробовать размещать их в
 виде пирамиды (если дерево бинарное) - кстати, тогда ссылки (n) не
 понадобятся, они сразу вычисляются; да и дерево будет заранее упорядочено.
 
 Зато появляется куча бонусов:
 
 1) Компактное размещение в памяти (=> меньшая фрагментация, легко из/в файла
 читать и т.п.),
 2) Быстрое копирование/построение деревьев/поддеревьев
 3) Быстрое сравнение
 4) Hу и прочие ништяки
 
 Удачи!
 __________________________________________________
 --{ Dmitriy Krylov aka "Abulafia"   }-------------
 --{ mailto: krylov@mail.primorye.ru }-------------
 --- ifmail v.2.15dev5
  * Origin: Demos online service (2:5020/400)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор