Add m-ary trees

[czgdp1807]

Description of the problem

Adding m-ary trees will be a nice idea. May be a array based(allows printing the trees) or pointer(better space utilisation) or both would be better.

Example of the problem

References/Other comments

.. [1] https://en.wikipedia.org/wiki/M-ary_tree

[vibhu18116]

Hi, can I start working on this issue as a part of RGSoC20?

[czgdp1807]

Hi, @vibhu18116 Please start by designing an API for m-ary trees. Please let us know if you face any problem/queries.

[vibhu18116]

Thank you for allowing me to work on this.

I believe the API design would closely follow that of binary trees. Hence these are a few APIs I think should form a basis:

• __new__(cls, m_value = 2, array_flag = 0, key=None, root_data=None, comp=None)

This would initialise a new m-ary tree. m_value will be used to determine the maximum value of m (the number of children of a node), default to 2 (binary tree in that case). array_flag can be set to indicate that an array implementation is required and it can remain 0 for pointer implementation.

Rest of the parameters will be same as binary tree implementation.

• insert(self, key, data)
• delete(self, key, **kwargs)
• search(self, key, **kwargs)
• __str__(self)

The above four will behave in the same way as in the binary tree. Implementation of the __str__ function will vary depending upon if the tree is implemented through array or pointers.

• height(self)
  Will return the height of the tree.

• width(self)
  Will return the width of the tree.

• convert_to_binary(self, array_flag = 0)
  This will convert an m-ary tree to binary tree and return the pointer to root if array_flag is not set and the array if array_flag is set.

Kindly check if these APIs work.

[czgdp1807]

__new__(cls, m_value = 2, array_flag = 0, key=None, root_data=None, comp=None)

IMO, using only array based implementation will be better here as pointers are somewhat unsafe, so avoid them where ever possible. Instead of m_value, a better name would be max_children. This suggests a nice way to implement using arrays.

Can you please explain the use of the values returned by height and width methods?

convert_to_binary(self, array_flag = 0)

IMO, just to_binary_tree(self) would better.

You may refer, https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/trees/binary_trees.py while implementing the above APIs.

[czgdp1807]

Note that m-ary tree is not a search tree, so we don't need to worry about the manner in which nodes are stored. We need a creative way to avoid the exponential space complexity of array based implementation. May be a new type of node inheriting TreeNode can be made which will be having an array storing the indices of it's children node in the array of m-ary trees. Please let me know if you are unable to get my point.

[vibhu18116]

I thought height and width of a tree can provide additional functionality to the user, however other than from feature point of view, I don't find any suitable use case.
So, if you suggest I would drop them.

I would update the names of functions as suggested.

[vibhu18116]

You may refer, https://github.com/codezonediitj/pydatastructs/blob/master/pydatastructs/trees/binary_trees.py while implementing the above APIs.

I checked this implementation, but a lot of functions like insert, delete are not implemented, probably because they depend on comparision key. Since the insert, delete API would follow the same pattern, should I first implement them?

[czgdp1807]

Actually, binary trees are quite abstract, hence their insert and delete operations are left unimplemented. What logic should be followed while making insertions to a binary tree? Both the operations are well defined for binary search trees.
IMO, we can keep insert, delete operations undefined for m-ary trees. We can a complementary m-ary search tree inheriting m-ary tree with insert and delete well defined for them. Here is defined for these kind of trees.
You can do the work in two separate PRs for m-ary and m-ary search trees, one after the previous one.

[vibhu18116]

I get your point. I will try to come up with actual implementation and try to create a PR in a day or two for m-ary tree.

[vibhu18116]

Can I keep to_binary_tree method abstract in m-ary tree, or a concrete implementation is required?

If a concrete implementation is required, then should I modify the m-ary tree itself or create a new binary tree with nodes of type TreeNode?

Currently, I have made a new node type extending TreeNode as suggested earlier which form nodes of m-ary tree.

[czgdp1807]

Can I keep to_binary_tree method abstract in m-ary tree, or a concrete implementation is required?

We can keep it as abstraction in m-ary tree but a concrete implementation can be added in m-ary search tree.

If a concrete implementation is required, then should I modify the m-ary tree itself or create a new binary tree with nodes of type TreeNode?

IMO, a new tree should returned.