5
\$\begingroup\$

A friend of mine and I recently started a project and at this moment we are writing a common library. He began writing an N-ary three and he is convinced that he has the best design with which I am not agree.

I want to convince him, that his design of the N-ary Tree is very bad, and with this design we will face problems. Due to lack of experience in complex projects from my side -- I can't convince him with my arguments.

Here is the current design and implementation:

template <typename T>
class Tree {
private:
    T data;
    vector< Tree<T> > successors;

public:
    Tree(T x) {
      data = x;
    }

    T root() {
        return data;
    }
    vector< Tree<T> > succ() {
        return successors;
    }
    void addChild(Tree<T> t) {
        successors.push_back(t);
    }
    void member(T element) {
        if (element == data)
            return true;
        for (int i = 0; i < successors.size(); i++) {
            if(successors[i].member(element)) {
                return true;
            }
        }
        return false;
    }
    void fromRightParentToLeft() {
        if (successors.empty()) {
            cout << data << "\n";
            return;
        }
        if (successors.size() == 1) {
            successors[0].fromRightParentToLeft();
            cout << data << "\n";
        }
        else {
          for (int i = succ().size(); i > 1; i--) {
            succ()[i-1].fromRightParentToLeft();
          }

          cout << data << "\n";
          succ()[0].fromRightParentToLeft();
        }
    }
};

So far I can see few problems:

  1. We will face problem when he will implement a method for node deletion, because it is somehow wrong a node to have the ability to delete itself.

  2. He traverses the tree in a inorder-ish manner, which is pointless when dealing with general N-ary trees.

Can someone point other potential traps with this approach?

The tree must meet the following requirements:

  • Inteface: node addition, node deletion, search for a particular node, basic tree traversal.
  • Other: It should be: easily maintainable, with fast performance.

In the general case the tree will have ~10k nodes, which will contain integers.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ As stated we can comment on the code and best practices. But there are a million valid ways to do something correctly. If you want us to comment on the fitness of the design for a particular purpose then you need to define the design requirements of your tree and what purpose it is designed to solve. We could also potentially comment on its fitness to achieve that specific goal. \$\endgroup\$ Dec 4, 2014 at 18:59

3 Answers 3

5
\$\begingroup\$

Some things:

By definition, an N-ary tree is a tree where any node must have no more than N children. However, you never allow the user to define that N, and nowhere do you specify the invariant that for any node, said node must have at most N children. Your tree is not an N-ary tree, it's just a "tree" (with an arbitrary number of children per node).

You're returning bool values in void member(T).

You should decouple traversal from the tree itself. Instead of thinking about traversal like tree.traverse() you should think like traverse(tree).

Reason: to separate and clear up responsibilities. A data structure holds data and nothing else. If you implement traversal behavior inside the tree, the user implementing his own would break any sort of consistency, unless he modifies the structure itself or extends it, which is not exactly desired in this kind of situations (class MySpecialPostOrderTraversalTree : Tree). Furthermore, separating the behavior from the data structure leaves room for other extensions (e.g. a generic traversal algorithm that works on your tree, and on some other kinds of trees, defined by your user).

You should definitely remove the console output from your tree, even if you leave traversal there. At least, you should allow your user to specify a method to call for each visited node. If he wants to print the content of the nodes, he can do it himself. You don't want to give someone a tree that randomly starts to print out stuff to stdout. Also see the concept of mapping functions over collections.

You keep working with values. For example, succ() returns a copy of the vector of children. On large trees this will have a negative effect, constantly copying vectors of elements which contain vectors of elements (and so on) is not exactly a good idea. Look into pointers, and base your tree on them. Start with std::unique_ptr and std::shared_ptr, don't use naked pointers.

See janos's answer for naming suggestions that I feel there's no need to duplicate here :)

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the answer Alex, could you post a comment on problems 1 and 2, which I pointed in the question? \$\endgroup\$
    – user15992
    Dec 5, 2014 at 9:44
  • \$\begingroup\$ I'd have chosen level traversal for an example traversal method. I'm not particularly sure how you'll want to delete a node. A node is the root of another tree (subtree). Do you want to remove the whole subtree or reattach the existing children of the node you're deleting to some other node? \$\endgroup\$
    – user29120
    Dec 7, 2014 at 13:34
  • \$\begingroup\$ I want to remove the whole subtree rooted at this node \$\endgroup\$
    – user15992
    Dec 8, 2014 at 10:28
3
\$\begingroup\$

So far I see mostly naming problems:

  • root() method returns the data of the node? I would have expected it to return the root node of the entire tree. getData would be better
  • addChild makes me think: do you intend to add parents? If not I'd call it simply add
  • Instead of member(), I'd use the more common contains(). Btw the code in your question returns void instead of bool, which looks like a bug
  • Instead of succ(), I'd call it successors()

In addition, instead of this:

Tree(T x) {
  data = x;
}

A more compact way to initialize:

Tree(T x) : data(x) {}

The repeated calls to succ() in this code are not great:

      for (int i = succ().size(); i > 1; i--) {
        succ()[i-1].fromRightParentToLeft();
      }

To avoid it, it would be better to use STL iterators instead, or at least cache that vector in a local variable.

I hope you're not using namespace std, which is a bad practice. This is better:

using std::cout;
using std::vector;
\$\endgroup\$
3
\$\begingroup\$

Requirements:

Inteface: node addition
          node deletion
          search for a particular node
          basic tree traversal.
Other:    It should be: easily maintainable, with fast performance.

This are not very good requirements.

Interface:

As your tree is a just a container of data you should not define your requirements in terms of modifying the structure of the container (so you should not mention nodes (nodes is an internal representation that should be transparent to the user)). Better would be to define the characteristics you want to see from the container.

Example:

Adding/deleting data from the tree should have a complexity of O(log(n)) or better. (Note log(n) is the standard characteristics of a binary search tree (BST)).

Searching

Your tree does not define very efficient searching. This is becuase the data in your tree is not structured in any particular way. So to search the tree you need to search every node in the tree. If you were using a BST then you would only need to search log(n) members of the tree to determine if the tree contained a specific piece of data.

Traversal

Your tree does not really provide any mechanism for traversal. You have a traversal function that prints the nodes but it is not generic enough to be useful for anything else. What you should have done was implement the visitor pattern.

Performance:

To be blunt the performance of your tree is diabolically bad. Because you don't specify any ordering you have to manually find a place in the tree to insert your data. You return by value (thus copying) rather than by reference or const reference.

Overall

You would be much better using one of the standard containers.

you can use std::map it has add/delete/access characteristics similar to BST O(log(n)) (it probably implemented as one underneath but you don't need to know that). You can increase speed by giving up space by using std::unordered_map here you get much better add/delete/access characteristics O(1) the disadvantage is that the elements are not ordered so traversal of the container returns the elements in a random order. If you want some manual control you can use a std::vector. Adding/deleting stuff from the end and accesses is cheap but deleting/adding in the middle is expensive. You could use a heap ontop of the vector to mitigate these issues.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.