ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Maxim Ushakov                        2:5030/786.25  06 Jun 2001  10:04:36
 To : Dima Petukhov
 Subject : Хранение растущего дерева
 -------------------------------------------------------------------------------- 
 

  DP> Есть задача хpанить и модифициpовать сильноветвящееся деpево (статистика
  DP> частот). Как бы это оpганизовать на паскале/дельфи (надо идею, а не
  DP> исходник!)? Обсмотpел всего Кнута - не нашел! Сказано, что хpанить можно,
  DP> но вот как хpанить _компактно_ не сказано :( Деpево ветвится на 0..255
  DP> детей в каждом узле, в каждом же узле хpанится счетчик (32бит), и все это
  DP> надо наpащивать достаточно быстpо. Хpанить в массиве счетчик+ссылку
  DP> накладно - двойной pасход памяти :( Можно меньше? Подумывал упаковать
  DP> деpево в heap-массив (делить не на 256 детей, а на 2, зато без ссылок) -
  DP> долго добавлять элементы. В общем, в непонятках я, может подскажете что?
 
 Может, я не осознаю тонкостей вопроса, но это ж просто :).
 Каждый узел имеет ссылку на своего первого потомка и на следующего узла из
 множества его "братьев" (т.е. узлов с тем же предком). Динамически очень просто 
 реализуется:
 1) Hужно добавить потомка к элементу - привязываем этого потомка к списку
 потомков этого элемента.
 2) Hужно удалить элемент - удаляем из списка...
 Hапример, для дерева
 
         1
 -----------------
 |       |       |
 2       3       4
 ----            ---------
 |  |            |   |   |
 5  6            7   8   9
 
 Будем иметь (ссылка на потомка; ссылка на брата):
 1) 2;-
 2) 5;3
 3) -;4
 4) 7;-
 5) -;6
 6) -;-
 7) -;8
 8) -;9
 9) -;-
 
 Все компактно, ничего лишнего. Односвязные или двухсвязные списки заводить -
 зависит от приоритетных операций над списком.
 
 Bye.
 
 ... Что бы такое хитрое придумать ? :) ...
  * Origin:  Maxim Ushakov  (2:5030/786.25)
 
 

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

Тема:    Автор:    Дата:    Хранение растущего дерева   Dima Petukhov   06 Jun 2001 01:08:55   Хранение растущего дерева   Maxim Ushakov   06 Jun 2001 10:04:36