загрузка бинарного дерева

← →
ford © (2012-04-06 18:27) [0]

Доброго времени суток!
Есть довольно большое бинарное дерево. Как быстрее всего сохранить и загрузить данные и саму структуру.
Т.е. например, есть бинарное дерево с миллионом узлов. Если просто сохранить в файл данные каждого узла, то потом при загрузке (восстановлении) дерева, придется добавлять каждый узел, т.е. строить все дерево заново, что не есть хорошо.
Подскажите алгоритм, как быстрее всего можно сохранить и восстановить уже созданное бинарное дерево.

(наверняка это уже обмусоливалось 1000 раз :) но я ничего не могу найти :( )

← →
Rouse_ © (2012-04-06 19:07) [1]

Ну добавь оффсет, указывающий на начало данных, откуда узел грузиться будет.

← →
RWolf © (2012-04-06 19:09) [2]

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

← →
ford © (2012-04-06 19:23) [3]

> Rouse_

> RWolf

А подробнее можно? :)

Самый простой пример, есть дерево
3
/ \
1 2

каждый элемент дерева это объект класса
само дерево тоже объект класса, у которого есть ссылка на корень дерева т.е. в данном случае на "3"
Если сохраним в файл как массив элементов, то получаем
3,1,2
при восстановлении загружаем этот файл в массив
и потом каждый элемент добавляем в объект класса "дерево"
Это то от чего я хочу уйти, т.е.
поясните, как Вы представляете сохранить это дерево?
и естественно его потом восстановить :)

← →
Rouse_ © (2012-04-06 19:26) [4]

Точнее, в логике дерева добавь свойство Fetch - определяющее, был ли зачитан узел или нет, плюс для каждого узла оффсет на данные откуда читать.

← →
Rouse_ © (2012-04-06 19:33) [5]

> поясните, как Вы представляете сохранить это дерево?
> и естественно его потом восстановить :)

Я обычно читаю не само дерево, а его элементы, которые умеют зачитывать своих чайлдов из переданного стрима. При сохранении естественно стримиться все дерево целиком. Ну это если не оптимально...
Можно использовать древовидные хранилища данных типа IStorage (ну или любая другая фигня, на основе которой можно проэмулировать дерево) позволяющие перезаписывать только сами изменяемые данные.

← →
RWolf © (2012-04-06 19:59) [6]

> > поясните, как Вы представляете сохранить это дерево?

> каждый элемент дерева это объект класса

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

← →
ford © (2012-04-06 20:00) [7]

Спасибо, Rouse_

> Я обычно читаю не само дерево, а его элементы, которые умеют
> зачитывать своих чайлдов из переданного стрима

Я тоже думал так сделать :) Но мало-ли :) вдруг есть более интересные варианты :)
Сами понимаете, самый быстрый вариант это записать массив и считать его соответственно :)

← →
Ega23 © (2012-04-06 20:02) [8]

Зачитать стрим целиком, а на элементы расставить свои оффсеты.

← →
ford © (2012-04-06 20:18) [9]

> RWolf

> если же узел дерева можно представить в виде записи без
> полей с автоматическим управлением памятью, то просто создаётся
> массив таких структур и сохраняется/загружается целиком.
>
>

Вы же понимаете, что элемент дерева это не что иное как
TElement = class
mean:Ineteger; //данные узла
Left:TElement; //ссылка на правую ветвь
right:TElement; //ссылка на левую ветвь
parent:TElement; //родитель
balans:Integer; //баланс
...
end;
т.е. ссылки формируются динамически и сохранить их как структуру ...
а как восстановить?
может подскажите, как тогда сформировать узел дерева, чтобы его можно было представить "статической" структурой.

> ford © (06.04.12 20:18) [9]

ссылка на левую/правую ветвь — необязательно указатель.
в предлагаемом варианте массива это просто индексы левого и правого дочерних элементов.
как сформировать? например, так:
TElement = record mean:Integer; //данные узла Left:Integer; //ссылка на правую ветвь right:Integer; //ссылка на левую ветвь parent:Integer; //родитель balans:Integer; //баланс ... end;

> а на элементы расставить свои оффсеты.

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

Не знаю, может я не совсем правильно излагаю или не правильно понимаю ваши предложения :)

есть сбалансированное дерево, готовое, построенное в памяти, где каждый элемент это объект класса (пример см. выше)
Если я сохраню в поток элементы как значения, то при чтении элементов мне придется заново формировать дерево, т.е. при добавлении производить балансировку.
Как вариант, который я рассматривал, схож с описанием
>>Rouse_

> Я обычно читаю не само дерево, а его элементы, которые умеют
> зачитывать своих чайлдов из переданного стрима.

т.е. грубо говоря:

Procedure Save (el:TElement);
begin
SaveEl(mean);
Save(self.right);
Save(self.left);
end;

и

Procedure load(el:TElement);
Begin
...
if el=nil Then LoadEl(mean);
Load(self.Right);
Load(self.Left);
End;

как-то так...

Если дерево сбалансированное, то проще всего записать его в массив в порядке полного дерева, т.е. корень по индексу 1, а дети i-го узла по индексам 2*i и 2*i +1. Если с балансом плохо -то обойти дерево в preorder порядке, записывая в этом порядке в массив (нулевые ячейки означают лист или другой признак придумать).

спасибо за ответы!
собственно я так и думал сделать, просто хотелось услышать мнение других людей.
Огромное всем спасибо:
MBo, RWolf, Ega23, Rouse_

загрузка бинарного дерева Найти похожие ветки