What are the names used in computer science for some of the following tree data types?

Question

Sometimes I get myself using different types of trees in Haskell and I don't know what they are called or where to get more information on algorithms using them or class instances for them, or even some pre-existing code or library on hackage.

Examples:

Binary trees where the labels are on the leaves or the branches:

data BinTree1 a = Leaf | 
                  Branch {label :: a, leftChild :: BinTree1 a, rightChild :: BinTree1 a}

data BinTree2 a = Leaf {label :: a} | 
                  Branch {leftChild :: BinTree2 a, rightChild :: BinTree2 a}

Similarly trees with the labels for each children node or a general label for all their children:

data Tree1 a = Branch {label :: a, children :: [Tree1 a]}

data Tree2 a = Branch {labelledChildren :: [(a, Tree2 a)]}

Sometimes I start using Tree2 and somehow on the course of developing it gets refactored into Tree1, which seems simpler to deal with, but I never gave a lot of thought about it. Is there some kind of duality here?

Also, if you can post some other different kinds of trees that you think are useful, please do.

In summary: everything you can tell me about those trees will be useful! :)

Thanks.

EDIT:

Clarification: this is not homework. It's just that I usually end up using those data types and creating instances (Functor, Monad, etc...) and maybe if I new their names I would find libraries with stuff implemented and more theoretical information on them.

Usually when a library on Hackage have Tree in the name, it implements BinTree2 or some version of a non-binary tree with labels only on the leaves, so it seems to me that maybe Tree2 and BinTree2 have some other name or identifier.

Also I feel that there may be some kind of duality or isomorphism, or a way of turning code that uses Tree1 into code that uses Tree2 with some transformation. Is there? May be it's just an impression.

Answer 1

The names I've heard:

• BinTree1 is a binary tree
• BinTree2 don't know a name but you can use such a tree to represent a prefix-free code like huffman coding for example
• Tree1 is a Rose tree
• Tree2 is isomoprhic to [Tree1] (a forest of Tree1) or another way to view it is a Tree1 without a label for the root.

Answer 2

A binary tree that only has labels in the leaves (BinTree2) is usually used for hash maps, because the tree structure itself doesn't offer any information other than the binary position of the leaves.

So, if you have 4 values with the following hash codes:

...000001 A
...000010 B
...000011 C
...000010 D

... you might store them in a binary tree (an implicit patricia trie) like so:

     +          <- Bit #1 (least significant bit) of hash code
    / \            0 = left, 1 = right
   /   \
[B, D]  +       <- Bit #2
       / \
      /   \
     [A]  [C]

We see that since the hash codes of B and D "start" with 0, they are stored in the left root child. They have exactly the same hash codes, so no more forks are necessary. The hash codes of A and C both "start" with 1, so another fork is necessary. A has bit 2 as 0, so it goes to the left, and C with 1 goes to the right.

This hash table implementation is kind of bad, because hashes might have to be recomputed when certain elements are inserted, but no matter.

---

BinTree1 is just an ordinary binary tree, and is used for fast order-based sets. Nothing more to say about it, really.

---

The only difference between Tree1 and Tree2 is that Tree2 can't have root node labels. This means that if used as a prefix tree, it cannot contain the empty string. It has very limited use, and I haven't seen anything like it in practice. Tree1, however, obviously has an use as a non-binary prefix tree, as I said.