1
$\begingroup$

I'm currently experimenting with some tree-like data structures and came up with a structure that has the following properties:

  • It consists of nodes and leaves
  • It has a single root element
  • Both nodes and leaves each hold a single element
  • Each node can have a non empty list of subtrees (a leaf could be considered a node with an empty list of children)
  • All elements inside the tree are of the same type and can be compared against each other
  • There are no duplicated elements inside a tree (this is especially interesting when it comes to inserting elements)

An implementation of this in Haskell could look like this (without the Eq constraint on a that would be required to compare the elements):

data Tree a = Node a (NonEmpty (Tree a)) | Leaf a

From my (rather limited) theoretical knowledge about data structures like this I think that it is some kind of unordered, unique tree. I guess that there is a well-known data structure somewhere out there and I'm hoping that someone can point me to the name as well as some resources about it.

I'm especially interested in algorithms for typical operations on this data structure:

  • Traversing the tree
  • Adding a single element to a tree
  • Removing a single element from a tree
  • Adding a tree to another tree (if the root element is already contained in the target tree, the tree should become a subtree to this element)
  • Removing an element (including its children) from a tree

To summarize: Is this data strucure well known? If so, what is the name for it and where can I find more information about efficient algorithms for operations on this data structure?

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ It seems to me u r just talking about a general tree structure, not a Binary Search Tree, not even a binary or ternary tree, just a general 1D tree with no duplicates $\endgroup$
    – ShAr
    May 9, 2020 at 22:05
  • $\begingroup$ Asking for the "name" of something is often not the best strategy. The great thing about language is that it lets us describe things we don't have an agreed name for; there are many more useful concepts and structures than there are standard "names". It's often more helpful to ask some specific question about that concept (e.g., identify what you'd do with a name if you had it, and then use that to ask a specific technical question about the data structure). If you want to know how to perform a particular operation, specify the operation and ask about that. $\endgroup$
    – D.W. ♦
    May 9, 2020 at 22:11
  • $\begingroup$ I see your point, the question wasn't too clear The point i was struggling the most with was the insertion of new elements into a tree. Also (and I didn't mention this in the question) I thought about whether or not it's possible to implement this as an immutable (or even persistent) data structure $\endgroup$
    – l7r7
    May 10, 2020 at 18:54

2 Answers 2

Reset to default
2
$\begingroup$

This is simply a tree, where all elements are unique. I'm not aware of any special name.

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ Not only is it just another tree datastructure, but it is even difficult to see what benefit the uniqueness constraint gives. In that way it seems like a slow tree datastructure. Lookup and insert are O(n). $\endgroup$
    – Pål GD
    May 10, 2020 at 10:54
  • $\begingroup$ @PålGD In my particular case it is important to keep the relationship between parent and children elements. That's why I came up with this kind of tree. I'm aware of the fact that operations will be slow, but it should be okay in this particular case as the trees will be relatively small $\endgroup$
    – l7r7
    May 10, 2020 at 18:58
  • $\begingroup$ The uniqueness constraint doesn't really seem to be a property of the data structure, but rather the dataset. That is, any implementation of the data structure would never need to know about this constraint if it was always given a compliant dataset. And if it was given a non-compliant one, the behavour isn't exactly specified anyway - is it supposed to fail? $\endgroup$
    – Steve Bennett
    May 21, 2020 at 1:24
1
$\begingroup$

The data structure that is the closest to what's needed here seems to be the rose tree. It has all the properties except the uniqueness constraint.

There is also an implementation of this data structure in the containers package, where the implementation looks like this:

data Tree a = Node {
        rootLabel :: a,
        subForest :: Forest a
    }

type Forest a = [Tree a]

which almost matches the type definition in the question.

This data structure doesn't seem to be widely used in the Haskell community, but there are some functions that are interesting to understand, like the implementation for Eq and Ord1.

Improve this answer
$\endgroup$

Your Answer

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

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