Saving a tree structure to disk...
Hey ppl!
i would like to get some different ideas for saving and loading a tree like structure to and from disk. my structure looks similiar to this:
struct node
{
bool isDivided; // true is this node has subnodes
nodeData *data; // node data
node *subNode[8]; // eight subnodes
}
at the moment i am just recursing the tree and saving each node as i come accross it. So i am not saving the links between the nodes, to load the tree, i am recursing throught the file and creating a tree from scratch.
Is there a more efficient way of saving/loading a tree like structure??
Should the links between the nodes be preserved??
Cheers
Paul
Without making things more complicated, that''s pretty much the way you want to go. It''s always hard to come up with a good approach for storing these types of structures to disk, because it''s the pointers that make them so flexible, and you loose that when it''s time to linearize the data. But as long as you have a consistent file saving/loading system, you''re doing well
XML is very well suited (and designed) for storing tree-like structures. Maybe you could write a binary implementation, using roughly same architecture otherwise?
-Nik
-Nik
Save each node''s data while traversing the tree breadth-first, so that each piece of data is followed immediately by the data for the eight subnodes below it, making it easy to reconstruct the tree.
This assumes that all eight subNodes exist whenever isDivided is true. If that''s not the case then you''ll need to store information about which of the eight subNodes exist, so that you know where they go (and how many to read back) when reconstructing each node.
This assumes that all eight subNodes exist whenever isDivided is true. If that''s not the case then you''ll need to store information about which of the eight subNodes exist, so that you know where they go (and how many to read back) when reconstructing each node.
Kindly forget that I said "followed immediately", because it''s not true. What I''m trying to say is that you should store the data for each of the eight subNodes before travelling down the tree.
Better yet, forget everything I''ve said so far. An easier approach is to save/load the tree using depth-first traversal, like this:
To save a tree:
Save data of root node.
Save subtrees of root node.
To save subtrees of N:
Save data of (each subnode of N).
Save subtrees of (each subnode of N).
To load a tree:
Create root node.
Load data of root node.
Load subtrees of root node.
To load subtrees of N:
Create subnodes of N.
Load data of (each subnode of N).
Load subtrees of (each subnode of N).
To save a tree:
Save data of root node.
Save subtrees of root node.
To save subtrees of N:
Save data of (each subnode of N).
Save subtrees of (each subnode of N).
To load a tree:
Create root node.
Load data of root node.
Load subtrees of root node.
To load subtrees of N:
Create subnodes of N.
Load data of (each subnode of N).
Load subtrees of (each subnode of N).
lol anonymous poster hehe thanks m8!
thankyou all for your input
One of my friends tried to describe the method thats used for a bsp tree, something to do with paralel arrays, where the first array stores the node and its link to other nodes, and the second array stores data???
is he dreaming? and pardon my ignorance, but whats XML?
thankyou all for your input
One of my friends tried to describe the method thats used for a bsp tree, something to do with paralel arrays, where the first array stores the node and its link to other nodes, and the second array stores data???
is he dreaming? and pardon my ignorance, but whats XML?
XML is a text-based system, eXtensible Markup Language, which was developed for data transmission across different computing platforms. The format is inherently defined as a root node (document), which contains child nodes, which can contain child nodes etc...
If parsing speed or storage requirements are not critical, then it's a very good way to store any tree-like data.
It's a web standard, therefore it's specification is found here.
-Nik
EDIT:
AFAIK raw hard disk data is stored this way, for example.
One array (partition header) contains the file indices and relations, while another array (the rest of disk space) contains the files.
[edited by - Nik02 on October 13, 2003 9:07:07 AM]
If parsing speed or storage requirements are not critical, then it's a very good way to store any tree-like data.
It's a web standard, therefore it's specification is found here.
-Nik
EDIT:
quote:One of my friends tried to describe the method thats used for a bsp tree, something to do with paralel arrays, where the first array stores the node and its link to other nodes, and the second array stores data???
AFAIK raw hard disk data is stored this way, for example.
One array (partition header) contains the file indices and relations, while another array (the rest of disk space) contains the files.
[edited by - Nik02 on October 13, 2003 9:07:07 AM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement