SOLVED Creating Custom Tree data Structure

[samspade]

I'm working on a tree data structure tutorial and I thought I should post the code here first to see if anyone wanted to offer feedback on whether this is a good way to do it or whether I would be steering people the wrong way.

Here's the basic core code to create and add:

/// @function tree_create()
/// @description Creates and returns a tree

return [];



/// @function tree_node_add(tree, data, [position])
/// @param {array} tree
/// @param {variable} data
/// @param {variable} data
/// @description add a node


#region rename for ease of use
var _tree, _data, _position;
_tree = argument[0];
_data = argument[1];
_position = 0;

if (argument_count == 3) {
    _position = argument[2];
}
#endregion

if (_position == 0) {
    array_add_to_end(_tree, tree_node_create(_data));
} else {
    var _new_node, _parent_node;
    _new_node = tree_node_create(_data);
    _parent_node = tree_node_get(_tree, _position);
    array_add_to_end(_parent_node[tree_node.children], _new_node);
}



/// @function tree_node_create(data)
/// @param {variable} data
/// @description Creates a node

/*
node = [
    data = data,
    children = [
        node,
        ...,
        node
    ]
]
*/

enum tree_node {
    data,
    children
}

return [argument0, []];

It would probably be easier to create a tree off of maps, but I thought arrays would be more interesting require less background as I wouldn't have to explain about data structure clean up.

 

[Homunculus]

I'm not sure I understand what you are trying to implement here honestly... First of all, what kind of tree are we talking about? Binary tree? N-Ary tree? BST?
I also don't get the position variable, shouldn't that be the parent node the new node gets added to?

Representing a node as an array with positions indexed by an enum is great, but the tree itself probably should be something else, like a ds_list or simply a "linked list", due to GML not allowing removing array entries (can happen for example when deleting a node).

 

[samspade]

Tree type would be a tree where any node can have multiple children defined by the user. Essentially image a tree that would work much like the inheritance model in GML.

It's true that using data structures provide some benefits (the primary being built in removal) but for the purpose of a tutorial I want to keep the things I need to explain to a minimum and data structures require talking about data clean up and in this particular case also the json structure as that would be the safest way to handle clean up for a large tree. For arrays all you have to do is write a script to copy a smaller portion of the array for removal.

 

[Homunculus]

I see your point about not using other data structures, and it's ok, it was just a nitpick.

I still don't get the code you provided (and maybe it's totally my problem), specifically the "position" argument, what does that mean in a tree structure? In a generic tree, I expect the tree_node_add to be declared something like this:

tree_node_add(data_or_node_struct, parent)

If you want to go for the simplest implementation possible, you don't even need to keep the "tree" as an array of nodes, you can just traverse it starting from the root node like a linked list (although keeping the node list as well also has its advantages).

 

[samspade]

Sorry, position is just what I named parent. That would be a good change for me to make. Using the root as the tree makes sense, and would clean up some of the other code since it wouldn't have to check for an empty tree. I think I would still need to reference it though in the function so that you know which tree to search the parent in.

 

[FrostyCat]

I use the exact same kind of architecture in GMStrategist (MctsNode.gml / MmNode.gml), so I would naturally not be opposed to this kind of setup. In fact, if you really want to keep this simple, you would ideally support only adding a single children to the end (which arrays support well) and traversals, not deletes or in-the-middle inserts.

Alternatively you can build the tree using maps and lists for this tutorial, but not release it until after you finish the video for JSON. Then the cleanup would only involve a ds_map_destroy() on the topmost node map (assuming you taught the map- and list-marking functions properly), and deletes and in-the-middle inserts are trivial.