4
$\begingroup$

I am not so familiar with trees.

How is a tree stored in memory? what is the data structure type used for storing it?

As a string?linked list? stack (!)?

Or is there some kind of data storage model for trees?

$\endgroup$
  • 3
    $\begingroup$ Depends. Naive implementation would be a node what has pointers to its children. This one is used in 2-3 trees. For implementing heap as a binary tree, people use a vector, where for node $i$ its children are at indices $2i$ and $2i+1$. So the answer is, depends what eventually you want to do with a tree. $\endgroup$ – Eugene May 15 '17 at 10:29
  • $\begingroup$ There are many different ways. What are your goals? What specific flavor of tree are you looking at? $\endgroup$ – Raphael May 17 '17 at 4:42
2
$\begingroup$

Usually it's stored as an adjacency list. Which is basically a linked list for every single node. So the linked list of a node u contains every node v such that (u,v) is a valid edge of the tree. enter image description here

The adjacency list of this tree would be:

 1 ->
 3 -> 1, 4
 4 ->
 5 -> 3, 8
 7 -> 
 8 -> 7, 10
10 ->

It can also be stored using an adjacency matrix. But that's used when the nodes of the tree are less (since it requires more memory). Adjacency list is better for sparse graphs.

$\endgroup$
2
$\begingroup$

the simplest data representation is Nodes and Links; so a list of Nodes such as 1,2,3,4,5, and a list of links such as 1:2, 1:3, 2:4, 2:5 would represent the tree below:

        1
      /  \
     2    3
    / \
   4   5 

This data representation also allows additional meta-data to be defined and stored at any of the elements [ie Nodes], or relationships [ ie Links] For example: Age of a node can be added as an Attribute. or PostalAdress of Node can be added as a set of attributes [ie Struct] Beyond that Nodes can be typed, and Links constrained or defined to link certain types only - and hence may carry different set of attributes depending on type of link or types of Nodes joined by that type of link. Traversing the tree is following it from any node in any direction . In reverse directions we would optimize by storing the Link 1:2 as well as the alt-Link 2:1 .

$\endgroup$
  • $\begingroup$ Nodes and links can also be called 'Leaves' and 'Branches' to describe trees - but it is the same as graphs. $\endgroup$ – newObserver May 17 '17 at 3:53
1
$\begingroup$

It depends on what data structure you want to represent it with.

I'll illustrate how its represented and how its stored in memory for a linked list 
implementation.

enter image description here

linked-list-of-children representation of the tree on the left.
  • Left link points to the first node in the linked list of its children

     Its clear the root node has three children, so the left link
     point to its first child, whose right link points to the 2nd and
     3rd children
     And so for the other sub-tress.
    
  • Right links of nodes point to siblings

    the right link of the first child points to its next siblings and so on(am considering from left to right).

That's how they are stored in memory for this implimentation. And hence the binary tree can be traverse. eg, in-order( Visit the left sub-tree, then the parent node, and then the right sub-tree ) this is done recusively.

$\endgroup$
  • $\begingroup$ The representation above by @Indo Ubt is, as far as i know for graphs rather than trees. $\endgroup$ – Tobi Obadiah May 16 '17 at 21:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.