Where to put data for tree structure which every node requires?

Question

I have a quad-tree structure where each node has some of its own data, but there is also data which applies to the tree as a whole.

I'll explain my current solution and I would appreciate feedback on whether this is the best solution or whether better solutions exist.

I have two classes:

• One for the node
• One for the tree

The tree class contains a root node pointer and the data relevant for that tree. The nodes in the tree need to access that data, so one option would be to have the node class include a data member which is a pointer to the tree object, and then invoke its accessor methods to get at the data.

This would increase the side of each node, though, so I decided to have a single static pointer for the node class. When a tree object wants to do something to all the nodes (most of the algorithms are recursive beginning at the root), it first sets the static pointer to point to its tree data (which I put in a struct) and then invokes the static pointer to point to its data.

Here is some pseudo-code:

struct TreeData {
    // data relevant to tree as a whole
};

class Tree {
public:
    void algorithm() {
        root.set_data(&data);
        root.algorithm();
    };

private:
    Node root;
    TreeData data;
};

class Root {
public:
    static void set_data(TreeData * data) {
        tree_data = data;
    }

    void algorithm() {
        // code that uses tree_data
    }

private:
    static TreeData * tree_data;
};

I wanted to avoid having every node increase in size, but there can be multiple trees instantiated at a time, so it couldn't just be static data for the node class.

So where should I put data for tree structure which every node requires?

Answer 1

Your current solution has a major down side in that it is not thread safe. I would definitely redesign so that you can have multiple tree operations preformed in parallel.

Assuming that nodes are purely internal to the tree structure, and always called via the tree, I would consider simply having their owner tree passed in as a parameter when you call any of their methods that needs access to this data.