Tree data structure as a MATLAB class

A per-value class that implements a generic tree data structure.

Description

A tree is a hierarchical data structure where every node has exactly one parent (expect the root) and no or several children.

Along with this relational structure, each node can store any kind of data.

This class implements it using plain MATLAB syntax and arrays. Most useful methods are implemented, using overloading of MATLAB functions for tree objects.

For instance you can type:

>> find ( (a.^2 .* b) > (c - 5) & d )

with a, b, c and d being tree objects.

Very handy, trivial to use. A rather long tutorial is included to walk you through trees, and show how to make the best out of them.

• MATLAB release: MATLAB 7.14 (R2012a)

[Steve Goley]

Excellent implementation of the tree data structure. I really like the automatic plotting function although it gets a bit crowded for large trees.

[Alexander]

 

[Jean-Yves Tinevez]

@Skirt: Thanks! Unfortunately this class cannot do what you want. What you describe here is a simple graph, of which this tree is just a specialization (this is actually an even more specialized *rooted tree* in a tree, all nodes but the root have exactly one parent, and edges have a direction).

You can make a tree out of a simple undirected graph (simple pick one particular node, and name it "the root"), but I think that you could beneficiate from a proper data structure class for what you want.

There exist some basis on which you could build in MATLAB, using e.g. the adjacency matrix (used in gplot http://www.mathworks.fr/fr/help/matlab/ref/gplot.html) which is an unspecialized sparse matrix.

Best
jy

[Skirt Zhang]

@Jean-Yves Tinevez
This is a great application. I need to build up a tree where the some nodes have multiple parents, so far I have not found the solution... can you help me about this? thanks a lot in advance

[Jean-Yves Tinevez]

@per isakson: Thanks! I would like to add your function to the class. Do you have the metrics that shows that it is 1 order of magnitude faster? I could put it in a new published file.

[per isakson]

I experiment with this Tree class to keep meta-data of a HDF5-file in memory. The file contains thousands of time series and it will be a back-end of a visualization tool. I want to read the series at random and present the result promptly. That is a bit of a challenge. Now I have something running, which looks promising. The Tree class plays a key role.

The code works well; I have had no real problems. The documentation is good. The class fills a gap; how come there isn’t a tree class in Matlab?

I added one method to the class, findpath2root. It is order of magnitude faster than findpath when one of the nodes is the root. It could be included in findpath.

Thanks a lot for this contributions!
/ per

function path2root = findpath2root( this, nix )
path2root = cat( 2, nix, parent_ixs( nix ) );
function p2r = parent_ixs( ix )
if ix == 1
p2r = [];
else
pix = this.Parent( ix );
p2r = cat( 2, pix, parent_ixs( pix ) );
end
end
end

[per isakson]

 

[Wolfgang Garn]

Excellent tool! I like the overloaded Matlab operators. Simple search and display methods.

[zain]

Just found what i need.
Thanks Jean-Yves Tinevez for this great tool.

[Werner]

 

[lixin fan]

@Jean-Yves: I am starting to use your tool. So far I haven't encountered any problems. I will keep you updated when deeper trees are created. Thanks for your assistance.

[dai zhengguo]

A well defined tool for tree data structure, Thanks for your submission.

[Jean-Yves Tinevez]

@lixin: as for memory, I am pretty sure that the overhead is kept minimal. Speed performance, however, I don't know. If you want, we can work to solve your issues if you encounter then as your project goes.

[lixin fan]

Looks a quite nice tool. Solid and elegant!

I am planning to create some deep trees, probably with dozens (or hundreds) of depths and thousands of nodes. Just wonder if performance will be an issue.