MATLAB Central Newsreader - Tree data structure in MatLab

Tree data structure in MatLab

Yersinio Jimenez — Sun, 01 Nov 2009 17:23:04 -0500

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.

Re: Tree data structure in MatLab

Rune Allnor — Sun, 01 Nov 2009 17:47:35 -0500

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

Re: Tree data structure in MatLab

jason — Wed, 11 Nov 2009 14:14:05 -0500

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

in that case look up struct

Re: Tree data structure in MatLab

Yersinio Jimenez — Sat, 12 Dec 2009 00:14:19 -0500

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

Thanks, for reply.

Re: Tree data structure in MatLab

Yersinio Jimenez — Sat, 12 Dec 2009 00:17:07 -0500

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.

Re: Tree data structure in MatLab

Bruno Luong — Sat, 12 Dec 2009 08:44:03 -0500

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

Re: Tree data structure in MatLab

Davis — Sat, 16 Jan 2010 23:27:02 -0500

"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.

Re: Tree data structure in MatLab

Derek O'Connor — Sun, 17 Jan 2010 13:24:03 -0500

"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

Re: Tree data structure in MatLab

Joao Henriques — Tue, 06 Jul 2010 21:09:05 -0400

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 = ...

Re: Tree data structure in MatLab

LESTER GARCIA — Wed, 23 Nov 2011 16:46:08 -0500