Tree Data Structures

Call Me Jimmy

I'm working on a project (a game) that logically calls for the use of a tree data structure. It's in actionscript and as with most platforms there aren't really any generalised tree structures out of the box.

So I decide to implement my own. I though "hey i understand trees, no problem!" and so I made my first attempt that started off nice and elegant (as all code does) and as I got closer to completion of the thing it was a bit of a mess.

I realised that before I started writing the class(es) I hadn't thought about the specific requirements.

I'm going to have another shot at it, but I have a couple of 'philosophical' programming questions about trees.

1.If I was to make an N-Tree that can hold any data type, it doesn't seem possible in my mind that it can add duplicates. Say a tree that should be capable of holding ints as its values. If there are two 2's in the tree, and you want to retrieve a number 2, it can't possibly do anything but get the first 2.

So is my assertion correct that the values have to be unique?

2. How is data retrieval implemented and is it not redundant? Say I have an object value that I want to get from the tree, I have to supply the object value as the parameter to the hypothetical getNode(Object) function...? I already have the object, what is the point in getting it from the tree? The only reason I can think of is to get its position/relationships with other nodes.

3. Does traversal have to be done recursively (I assume it does), and is there any other way to do something for each node in the tree without function pointers? Without function pointers, you would have to write almost the same code with slight differences to do different things to the nodes.

4. I like to build my own library of classes that I use across projects whenever it is essential and keep the things I can re-use. I need an N-Tree for this project. Should I focus on implementing a generalised data structure that I can reuse or just focus on doing the exact things I need for my current project?

Most information online is for binary trees and performance (balancing etc.), whereas the trees in this project will all be small (<15 items).

Thoughts on trees?

Anima

Sounds like you're making it more complicated than it needs to be. If you're sure its only a small amount of items, just make something custom or else wrap another container type with some custom logic.

Call Me Jimmy

Yea I guess that's what I will do but the (student) programmer in me wants to be a gimp and have everything all nice and elegant and reusable... I'll probably have one more go at it and then if it still isn't working out just do a bit of a hack-job

fergalr

Your post seems quite confused?

Call Me Jimmy wrote: »

I'm working on a project (a game) that logically calls for the use of a tree data structure.

Are you sure? What are you using it for?

Call Me Jimmy wrote: »

It's in actionscript and as with most platforms there aren't really any generalised tree structures out of the box.

So I decide to implement my own. I though "hey i understand trees, no problem!" and so I made my first attempt that started off nice and elegant (as all code does) and as I got closer to completion of the thing it was a bit of a mess.

I realised that before I started writing the class(es) I hadn't thought about the specific requirements.

Also, as you code something, your understanding of what you need changes. Sometimes you have to change quite differently, from what you set out to write. That's ok. Although, certainly, if you can figure this out ahead of time, its even better.

Call Me Jimmy wrote: »

I'm going to have another shot at it, but I have a couple of 'philosophical' programming questions about trees.

1.If I was to make an N-Tree that can hold any data type, it doesn't seem possible in my mind that it can add duplicates. Say a tree that should be capable of holding ints as its values. If there are two 2's in the tree, and you want to retrieve a number 2, it can't possibly do anything but get the first 2.

So is my assertion correct that the values have to be unique?

In general, no.
Its possible to have a tree that allows duplicate values, and its also possible to have one that doesn't.
There's nothing fundamental about trees that enforce duplication, or uniqueness, you can do either, depending on how you use them.

Call Me Jimmy wrote: »

2. How is data retrieval implemented and is it not redundant? Say I have an object value that I want to get from the tree, I have to supply the object value as the parameter to the hypothetical getNode(Object) function...? I already have the object, what is the point in getting it from the tree? The only reason I can think of is to get its position/relationships with other nodes.

There doesn't seem any reason you would query a tree for an object that you already had; unless you cared, for some reason, about where it was located in your tree. (Perhaps the tree maps to a spatial representation of the world, for example).

But these questions are only meaningful with some context.
What is the tree for?

Call Me Jimmy wrote: »

3. Does traversal have to be done recursively (I assume it does),

No.
There's many ways of traversing trees, and these can generally be implemented recursively, or iteratively.

Call Me Jimmy wrote: »

and is there any other way to do something for each node in the tree without function pointers? Without function pointers, you would have to write almost the same code with slight differences to do different things to the nodes.

There is almost always a way to avoid having to write the same code with slight differences, which is generally a sign of bad design, and hence worth thinking about how to avoid.

Call Me Jimmy wrote: »

4. I like to build my own library of classes that I use across projects whenever it is essential and keep the things I can re-use. I need an N-Tree for this project. Should I focus on implementing a generalised data structure that I can reuse or just focus on doing the exact things I need for my current project?

That depends, and is quite a hard judgement to make.
In general, focus on writing code for your current project, first, and when its working, and stably fulfilling its role, consider making it more general. Try not to make decisions that prevent you later making a more general solution; but don't get caught up in architecture, or generalisation, to the extent that you dont get anything done.

Call Me Jimmy wrote: »

Most information online is for binary trees and performance (balancing etc.), whereas the trees in this project will all be small (<15 items).

Why would you put 15 items in a tree?
It'll almost always be as quick to scan over a list of 15 items, vs. traverse a tree structure - so the usual 'efficient querying' reason doesn't make sense.

This is the most important thing you should have mentioned in your post - why you are using a tree - and should be something you think about.

Before spending time thinking about designing your tree well - why do you even need one?

Call Me Jimmy wrote: »

Thoughts on trees?

They are great.

Call Me Jimmy

fergalr wrote: »

Your post seems quite confused?



Are you sure? What are you using it for?



Also, as you code something, your understanding of what you need changes. Sometimes you have to change quite differently, from what you set out to write. That's ok. Although, certainly, if you can figure this out ahead of time, its even better.


In general, no.
Its possible to have a tree that allows duplicate values, and its also possible to have one that doesn't.
There's nothing fundamental about trees that enforce duplication, or uniqueness, you can do either, depending on how you use them.



There doesn't seem any reason you would query a tree for an object that you already had; unless you cared, for some reason, about where it was located in your tree. (Perhaps the tree maps to a spatial representation of the world, for example).

But these questions are only meaningful with some context.
What is the tree for?



No.
There's many ways of traversing trees, and these can generally be implemented recursively, or iteratively.



There is almost always a way to avoid having to write the same code with slight differences, which is generally a sign of bad design, and hence worth thinking about how to avoid.


That depends, and is quite a hard judgement to make.
In general, focus on writing code for your current project, first, and when its working, and stably fulfilling its role, consider making it more general. Try not to make decisions that prevent you later making a more general solution; but don't get caught up in architecture, or generalisation, to the extent that you dont get anything done.


Why would you put 15 items in a tree?
It'll almost always be as quick to scan over a list of 15 items, vs. traverse a tree structure - so the usual 'efficient querying' reason doesn't make sense.

This is the most important thing you should have mentioned in your post - why you are using a tree - and should be something you think about.

Before spending time thinking about designing your tree well - why do you even need one?


They are great.

Yea I should have mentioned what it was for. Basically the main objects in the games are 'combo nodes', i.e. one main shape that has a bunch of smaller shapes connected to it. The player has to go through each node (shape), match that nodes shape and can continue on to the next node node until they've reached the central or main shape.

So the root node or 'mother shape' can have any number of children, and the children need to have children etc. so the player can basically attach to a leaf ( the outer shapes) and travel along the path to main the node, gaining combo points all along by changing shape to match the next parent. The player can go directly from parent to parent until they reach the central shape (quickest) but I want them to be able to choose at each shape if they want to get a bigger combo by going choosing to go visit siblings as well.

Actually I've got an image, im pretty sure a tree is what's needed. See attached, i try to show a stepping through of one situation

Giblet

That looks more like a graph than a tree? Also with a limit of 15, you are probably better with a flattened hierarchy for searching directly.

Call Me Jimmy

As soon as i opened the attached image and looked at it again thats exactly what i thought for the first time hah

fergalr

Call Me Jimmy wrote: »

Yea I should have mentioned what it was for. Basically the main objects in the games are 'combo nodes', i.e. one main shape that has a bunch of smaller shapes connected to it. The player has to go through each node (shape), match that nodes shape and can continue on to the next node node until they've reached the central or main shape.

So the root node or 'mother shape' can have any number of children, and the children need to have children etc. so the player can basically attach to a leaf ( the outer shapes) and travel along the path to main the node, gaining combo points all along by changing shape to match the next parent. The player can go directly from parent to parent until they reach the central shape (quickest) but I want them to be able to choose at each shape if they want to get a bigger combo by going choosing to go visit siblings as well.

Actually I've got an image, im pretty sure a tree is what's needed. See attached, i try to show a stepping through of one situation

I'm not sure I fully understand you - might be my fault - but would a graph representation not be a better fit than a tree?

Edit - ninja'd by Giblet :-)

Call Me Jimmy

Giblet wrote: »

That looks more like a graph than a tree? Also with a limit of 15, you are probably better with a flattened hierarchy for searching directly.

A flattened hierarchy? As in just an associated 'level' of the hierarchy for each item in a normal collection?

stevenmu

Actually looks much more like a Finite State Automoton or State Machine to me, could be worth lokoing at those.

Wiki link

fergalr

stevenmu wrote: »

Actually looks much more like a Finite State Automoton or State Machine to me, could be worth lokoing at those.

Wiki link

I don't fully understand what the OP is trying to do, but the data on the connections in the world still needs to be stored somewhere, right?

If the where the process can go next is determined purely by where its at (markov property) then a graph would be fine? If there's need for a memory - so that where it can go depends on where it has been recently, then you might have a graph as your datastructure, but use a finite-state-machine to hold the state of the walker of the graph, so that the rules about matching shapes aren't violated.

But, unless the topology is completely regular, and simple, wouldn't it make more sense to capture that topology as a graph, rather than a FSM?

Again, I don't fully understand the problem spec.

Call Me Jimmy

Thanks for the advice btw. Thing is, the logic of at what nodes you can go to based on where you are could well be represented in a fsm but as ferg says, I am also containing the sub-objects themselves, position, shape type, state etc. for each one. So while an fsm might work for the logic, I still need a datastructure.

The problem is it's hard for me to explain it fully, I did my best with the drawing but it will be a fast-paced action game with the core gameplay being about attaching to one of those nodes and 'combo-ing' your way into the center until it blows up.

I actually did out a (not exactly formal) fsm last night, attached, it was me trying to figure out a pattern for defining the rules and hopefully seeing what type of data structure lends itself to the typical movements...

Procasinator

Struggling to see exactly what you are trying to do, but it seems like a tree might fit.

My assumptions:

• You start at a leaf node and have to make your way up to the root node (which then is the last possible move).
  
• To get to a sibling, you have to go through the parent node.
  
• From a given node, you can only visit each leaf at most once (do not have to visit at all).

If it is like that, you could delete the branch after traversing up to the parent. As in, when moving from 1 to 2, remove that node. When moving from 3 to 4, remove that node. When there is no brances left, a user will have to move up the next parent (deleting that node) where it can visit siblings, etc.

What is confusing here is the central or main shape. You would expect this to be the root node. Is this a 2 or more player game where people approach from different sides?

Off-topic: When you say player changes shape, is this a kinect-like game or something?

Call Me Jimmy

Procasinator wrote:

Struggling to see exactly what you are trying to do, but it seems like a tree might fit.

My assumptions:

• You start at a leaf node and have to make your way up to the root node (which then is the last possible move).
  
• To get to a sibling, you have to go through the parent node.
  
• From a given node, you can only visit each leaf at most once (do not have to visit at all).

Yes. You are correct, with the exception being that when you get the central/root/main node, you can optionally go traverse its other branches as well out to each leaf. When you reach a leaf on another branch you traverse back up and (as you rightly describe) each node you have visited is then destroyed. So as long as a node has other siblings or children that havent been destroyed, you can branch out to them, and as you work your way back they destroy behind you.

Procrastinator wrote:

What is confusing here is the central or main shape. You would expect this to be the root node. Is this a 2 or more player game where people approach from different sides?

It is designed for single player at the moment, but the logic is the same. A single player can approach from any leaf, and while the node is not a leaf (and including the root or central node) they can go and traverse the remaining branches. So reaching the central node can result in an end state, but the player can decide to go after all the other nodes on other sides that they havent been through to get to the root node in the first place. Aghh so hard to explain!

Procrastinator wrote:

Off-topic: When you say player changes shape, is this a kinect-like game or something?

Nah it's a simple 3-button setup for changing shape (1 is triangle, 2 is square and 3 is circle).

Call Me Jimmy

Just after drawing it out again with graphs in mind, and I am actually sold on the idea that its best represented with a graph as there actually isn't a hierarchical nature to what I'm trying to do as I first assumed. I was thinking in terms of parents and children connections between each node but each node simply has a n-connections, no need for parents and children just navigable paths.

Thanks for the input guys!

Procasinator

A tree is a graph with no cycles. From your description, it sounds like you have a tree to me.

fergalr

Procasinator wrote: »

A tree is a graph with no cycles.

A tree is a bit stricter than that, right? Each node only has one parent.

Procasinator wrote: »

From your description, it sounds like you have a tree to me.

I'm still not 100% clear on what is needed, and on what the OP wants to represented.

From the diagram, though, there are multiple shapes that the player can initially 'enter the combo node at', so that sounds like a tree structure, which only has one root node, would be a less good fit.

But I'm not sure if we are talking about representing the possible states that can be moved through (which looks like a graph) or the the traverse of those states.

Call Me Jimmy

A tree is also hierarchical, right? There is no hierarchical structure in a graph, just nodes and connections/edges with optional weights attached...?

I thought the group of shapes was hierarchical but realise now that it isn't. The parent/child relationships seemed redundant the more I looked at it.

Sorry yer still not sure of what I'm tryin to do ferg, I know if I spoke to you for 30 seconds ye'd see but i'm not too great on paper!

EDIT: Well, it is kinda hierarchical but for some reason thinking of each node having just n-connections rather than parent-child relationships had the code writing itself. Maybe I'm cheating if the true representation is a tree structure but god damnit it's making a lot more sense this way than with a tree.

fergalr

Call Me Jimmy wrote: »

A tree is also hierarchical, right?

Yes, very hierarchical - each node only has a single parent - so somewhere, there is a single node that is the 'root' of the tree, which everything is below.

You can have a directed graph like that too, but a graph is more general. People also talk about 'directed acyclic graphs' a lot, which are a bit like halfway between a tree and a graph.

If you don't want the hierarchical structure, you probably don't want a tree.

Call Me Jimmy wrote: »

There is no hierarchical structure in a graph, just nodes and connections/edges with optional weights attached...?

Graphs can be directed, or undirected - its possible to make hierarchical structure in a directed graph, but, unlike a tree (which is always hierarchical) graphs also allow non-hierarchical structure.

Call Me Jimmy wrote: »

I thought the group of shapes was hierarchical but realise now that it isn't. The parent/child relationships seemed redundant the more I looked at it.

Sorry yer still not sure of what I'm tryin to do ferg, I know if I spoke to you for 30 seconds ye'd see but i'm not too great on paper!

Yeah - I think this is one of those things its just easier to explain with gestures in the air, and questions, rather than on paper.

I'm kind of interested in where you are going with this - if you get it implemented, maybe show us a video of it running :-)

Procasinator

fergalr wrote: »

A tree is a bit stricter than that, right? Each node only has one parent.

Well, if a node had more than one parent, then it would have a cycle (assuming a root node).

fergalr

Procasinator wrote: »

fergalr wrote: »

A tree is a bit stricter than that, right? Each node only has one parent.

Well, if a node had more than one parent, then it would have a cycle (assuming a root node).

That is not the case - think about a DAG.

Procasinator

fergalr wrote: »

That is not the case - think about a DAG.

Oops, I should have added the word undirected as it was part of the OPs description (at least, what I gathered). It also has to be connected graph to be a tree (which also seems to be the case in the OPs description).

Procasinator

Wolfram puts it better than me:

http://mathworld.wolfram.com/Tree.html wrote:

[...] it is a simple, undirected, connected, acyclic graph

Call Me Jimmy

So if through whatever process every node can eventually be reached from any other node it is a tree? Is there a difference between an un-directed graph and a tree then?

EDIT: Procrast got there before me.

So are we splitting hairs then at this point between synonyms?

The only reason I can see that pushes it towards a tree structure is the fact that the central node is a root and conceptually a hierarchy is there, but if an un-directed, acyclical graph is a tree, why doesn't a UDAG not have parent/child relationships? or does it? damn i was close to having this sorted in my head!

Procasinator

Call Me Jimmy wrote: »

So if through whatever process every node can eventually be reached from any other node it is a tree? Is there a difference between an un-directed graph and a tree then?

EDIT: Procrast got there before me.

So are we splitting hairs then at this point between synonyms?

The only reason I can see that pushes it towards a tree structure is the fact that the central node is a root and conceptually a hierarchy is there, but if an un-directed, acyclical graph is a tree, why doesn't a UDAG not have parent/child relationships? or does it? damn i was close to having this sorted in my head!

Sorry, didn't mean to confuse you.

A tree in computer science usually means a ordered directed tree (in it's most common use), so it can be a bit hazy. :P

I wouldn't concern yourself too much in what it is. Use a graph, and make sure the rules of adding vertices and the edges doesn't allow cycles.

That, or try and use a pre-built Tree and see if it does fit. This AS3 library looks to have some useful data structures (including Trees):
http://code.google.com/p/polygonal/wiki/DataStructures

Call Me Jimmy

Yea got it sorted, using a tree, just implementing it with a clearer head.

That link is great procrastinator, i couldn't find that library after searching (I failed at googling...). It has loadsa cool stuff, but i decided to write my own tree for experience.

fergalr wrote: »

I'm kind of interested in where you are going with this - if you get it implemented, maybe show us a video of it running :-)

Yea I'll probably come to boards for feedback as people are anonymous so they don't care if they hurt my feelings.

This whole project came from a third year project I just did (after 2 years out of coding so it needed to be simple enough).

http://www.student.dcu.ie/~courtnc3

the rules and controls are below, give it a shot if yer interested. It's alright but as I said I wanted to keep it as simple as possible coz I didn't want to fail by over-reaching and messing it up!

fergalr

Call Me Jimmy wrote: »

Yea got it sorted, using a tree, just implementing it with a clearer head.

That link is great procrastinator, i couldn't find that library after searching (I failed at googling...). It has loadsa cool stuff, but i decided to write my own tree for experience.




Yea I'll probably come to boards for feedback as people are anonymous so they don't care if they hurt my feelings.

This whole project came from a third year project I just did (after 2 years out of coding so it needed to be simple enough).

http://www.student.dcu.ie/~courtnc3

the rules and controls are below, give it a shot if yer interested. It's alright but as I said I wanted to keep it as simple as possible coz I didn't want to fail by over-reaching and messing it up!

Finished it. Its very good, I really like it. You've made a compelling mechanic with very few rules, good game design.

The mechanic seems like it might be inspired by Ikaruga http://en.wikipedia.org/wiki/Ikaruga
but with the third class.

Call Me Jimmy

thanks a lot, really appreciate it! the levels were done so that I could demonstrate the whole game to my supervisors, last level is the only challenging one really.

Yea, i was aware of the idea of ikaruga but it wasn't in my head when making it. Someone else said it was like Tetris so I suppose in a game that simple the core mechanics are more exposed and obvious so it's easier to see likenesses etc.

Anyway, I noticed that adding up combo's has the potentially really cool, hence my fascination with trees over the last couple of days

ChRoMe

I just played it a few times, couldnt get past level 1

On each occasion it seemed that it was impossible, i.e not enough triangles were displayed to get to 15?

However, it is a nice simple mechanic, well done

Just curious what course are you doing?

fergalr

ChRoMe wrote: »

I just played it a few times, couldnt get past level 1

On each occasion it seemed that it was impossible, i.e not enough triangles were displayed to get to 15?

However, it is a nice simple mechanic, well done

Just curious what course are you doing?

RTFM noob ;-)
you can change shape by pressing mouse, and collect shapes other than triangle.

Call Me Jimmy

ChRoMe wrote: »

I just played it a few times, couldnt get past level 1

On each occasion it seemed that it was impossible, i.e not enough triangles were displayed to get to 15?

However, it is a nice simple mechanic, well done

Just curious what course are you doing?

lol, I thought you were a retarded person until I realised you probably didn't know ye could change shape! press mouse to change shape and its relatively easy!

I'm studying Computer Applications at DCU.