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?