Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Tree data structure in MatLab

Subject: Tree data structure in MatLab

From: Yersinio Jimenez

Date: 1 Nov, 2009 17:23:04

Message: 1 of 11

Hi every guys.

Does any one know if there is some tree like data structure in MatLab?

The questions is because some algorithms are more clear if you think in terms of tree data structure instead of matrix.


Thanks in advance.
Yersinio.

Subject: Tree data structure in MatLab

From: Rune Allnor

Date: 1 Nov, 2009 17:47:35

Message: 2 of 11

On 1 Nov, 18:23, "Yersinio Jimenez" <yersin...@hotmail.com> wrote:
> Hi every guys.
>
> Does any one know if there is some tree like data structure in MatLab?
>
> The questions is because some algorithms are more clear if you think in terms of tree data structure instead of matrix.

There is no such thing in matlab, but you might get access to
something like that from the java engine matlab is based on.

Apart from that, the whole idea behind matlab (MATrix LABoratry)
is to express absolutely everything in terms of matrices.

Rune

Subject: Tree data structure in MatLab

From: jason

Date: 11 Nov, 2009 14:14:05

Message: 3 of 11

are you looking for a structure?
i.e. Data.Field1='apples'
Data.Field2='oranges'?

in that case look up struct

Subject: Tree data structure in MatLab

From: Yersinio Jimenez

Date: 12 Dec, 2009 00:14:19

Message: 4 of 11

No, i'm not talking about structs. A have already works with that and are two very differents things.

Thanks, for reply.

Subject: Tree data structure in MatLab

From: Yersinio Jimenez

Date: 12 Dec, 2009 00:17:07

Message: 5 of 11

I will try with java tree data structure, but i belivie that it would have some implications in terms of performance.

Thanks for your reply.

Yersinio.

Subject: Tree data structure in MatLab

From: Bruno Luong

Date: 12 Dec, 2009 08:44:03

Message: 6 of 11

I would argue a CELL having nested cells having nested cells etc ... are tree. The different is inserting or removal a branch/element is a costly operation (since Matlab does not provide a notion of pointers).

This data structure can be also represented by STRUCT with nested STRUCT.

I believe there are several FEX tools that do conversion back and forth between XML and STRUCT. I have used one of those and it works OK for my need, which do not do any intensive tree manipulation.

But yes, basically, there is nothing exactly match TREE in Matlab.

Bruno

Subject: Tree data structure in MatLab

From: Davis

Date: 16 Jan, 2010 23:27:02

Message: 7 of 11

"Yersinio Jimenez" <yersinioj@hotmail.com> wrote in message <hckg5o$8t6$1@fred.mathworks.com>...
> Hi every guys.
>
> Does any one know if there is some tree like data structure in MatLab?
>
> The questions is because some algorithms are more clear if you think in terms of tree data structure instead of matrix.
>
>
> Thanks in advance.
> Yersinio.

I couldn't find a 'tree' class either, although I've looked. However, it should be possible to spin your own by implementing it using an object oriented approach. Here, you create a 'node' class (preferably inherited from the handle class), with a constructor and destructor, and properties that include links to other nodes. You then create a 'tree class' that inherits the properties of the node class and include methods for inserting and deleting nodes, one to walk the tree up and down from its root, etc. You could also include events and event listeners if the application calls for it.

In principle this could be implemented using structures (although I wouldn't even want to try, since using the object oriented class-based approach would be much, much easier). (Honesty alert: I haven't actually done this yet, but am working on it.) Comments welcome.

Subject: Tree data structure in MatLab

From: Derek O'Connor

Date: 17 Jan, 2010 13:24:03

Message: 8 of 11

"Yersinio Jimenez" <yersinioj@hotmail.com> wrote in message <hckg5o$8t6$1@fred.mathworks.com>...
> Hi every guys.
>
> Does any one know if there is some tree like data structure in MatLab?
>
> The questions is because some algorithms are more clear if you think in terms of tree data structure instead of matrix.
>
>
> Thanks in advance.
> Yersinio.
-------------------------------------------------------------------

The simplest tree data structure is an array of parent 'pointers'

A tree with n nodes can be stored using two arrays : Node(1:n)
stores node data such as name, geographical coordinates, etc.,
and Parent(1:n), where Parent(i) contains an number in (1:n)
which is the location of node i's parent in array Node(1:n).

Example: Tree with 14 nodes labelled with letters of the alphabet

            1 2 3 4 5 6 7 8 9 10 11 12 13 14
--------------------------------------------------------
Node: y q g s t e k w l x y v f m
Parent: 8 4 2 0 4 4 12 6 8 7 8 13 8 3

The root of the tree is Node(4) = s because Parent(4) = 0.

This data structure is fine if all you want to do is climb up the tree, otherwise you need a more complicated data structure. If you don't need node data omit array Node(1:n).

Read Cormen, Leiserson, and Rivest : Intro. to Algorithms, or Aho and Ullman: Foundations of Computer Science

 Derek O'Connor

Subject: Tree data structure in MatLab

From: Joao Henriques

Date: 6 Jul, 2010 21:09:05

Message: 9 of 11

Derek's answer is the right one for Matlab, it may be strange for someone with a different background (eg. C++, Java) but the only way to deal with this sort of data structures is to re-interpret them in terms of vectors or matrices. Sometimes it's not obvious how to do so, and the result is very inefficient and hard to maintain code because you're trying to hammer foreign concepts into ML! This may change as OOP matures within ML (but IMO it's not there right now).

You can keep your data structures tidy by using structs, I'll describe this at the end.

For the tree structure, if the number of children is fixed (for example, a binary tree), a tree with N nodes can be represented with an Nx2 matrix, where each row has the indexes of the children of each node (0 if none). This makes it easier to traverse from the root.

Another example is when dealing with general graphs. For a graph with N nodes and M arcs, you can store it as two length M vectors, "heads" and "tails" (an arc points from the head node to the tail node), with the indexes of the corresponding nodes. Node data is kept separately, typically in other length N vectors (or cell arrays if the data has different shapes). Notice that this can also store trees, as they're just graphs after all!

Storing these vectors as structs to pass them around easily, I'd have a struct representing the arcs:
arcs.tails = ...
arcs.heads = ...
arcs.costs = ...
(etc etc)
And another representing the nodes if necessary:
nodes.names = ...

Subject: Tree data structure in MatLab

From: LESTER GARCIA

Date: 23 Nov, 2011 16:46:08

Message: 10 of 11

"Yersinio Jimenez" <yersinioj@hotmail.com> wrote in message <hckg5o$8t6$1@fred.mathworks.com>...
> Hi every guys.
>
> Does any one know if there is some tree like data structure in MatLab?
>
> The questions is because some algorithms are more clear if you think in terms of tree data structure instead of matrix.
>
>
> Thanks in advance.
> Yersinio.

Please Review this tutorial from matlab about Tree operations,
maybe what you are looking for is in there.

I know the post is from long time ago, but, maybe this comment will
help to others who are asking the same question, dont you think?

Subject: Tree data structure in MatLab

From: Jean-Yves Tinevez

Date: 15 Mar, 2012 12:53:15

Message: 11 of 11

"LESTER GARCIA" wrote in message <jaj80g$mi$1@newscl01ah.mathworks.com>...
> "Yersinio Jimenez" <yersinioj@hotmail.com> wrote in message <hckg5o$8t6$1@fred.mathworks.com>...
> > Hi every guys.
> >
> > Does any one know if there is some tree like data structure in MatLab?
> >



As stated before, this post is from long ago, but since it is the one I have found when I was searching for help the week before, I thought I would add to it.

I followed the recommendations from Derek O'Connor and implemented a simple class that handle tree data structure. You can find it in the FEX if you are interested:

http://www.mathworks.com/matlabcentral/fileexchange/35623-tree-data-structure-as-a-matlab-class

There is a tutorial to exxplain how to play with it:

http://www.mathworks.com/matlabcentral/fileexchange/35623-tree-data-structure-as-a-matlab-class/content/TreeDataStructure/TreeDemo.html

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us