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

Question

Sometimes I myself use different types of trees in Haskell, and I don’t know what they are called, or where you can get additional information about the algorithms that use them or class instances for them, or even any previously existing hackage code or library.

Examples:

Binary trees where the labels are on leaves or 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 labels for each child node or a common 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 during development it will be reorganized into Tree1 , which seems easier to use, but I never thought about that. Is there any duality here?

In addition, if you can post several other types of trees that you think are useful, please.

In short: everything you can tell me about these trees will be helpful! :)

Thanks.

EDIT:

Clarification: this is not homework. It's just that I usually use these data types and create instances (Functor, Monad, etc.), and maybe, if I call them, I would find libraries with implemented materials and more theoretical information about them.

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

I also feel that there may be some kind of duality or isomorphism, or a way to turn code that uses Tree1 into code that uses Tree2 with some conversion. Here? Maybe this is just an impression.

Answer 1

Names I heard:

• BinTree1 is a binary tree
• BinTree2 does not know the name, but you can use such a tree to represent the code without a prefix, such as huffman encoding, for example
• Tree1 is a Tree1
• Tree2 isomoprhic for [Tree1] (Forest Tree1 ) or another way to view it is Tree1 without a label for the root.

Answer 2

A binary tree that has only labels in the sheets ( BinTree2 ) is usually used for hash maps, since the tree structure itself does not provide 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 can save them in a binary tree (implicit patricia trie), for example:

  + <- 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 B and D “start” at 0 , they are stored in the left root child. They have the same hash codes, so no forks are needed anymore. Hash codes A and C both "start" with 1, so another fork is needed. A has bit 2 as 0 , so it goes to the left, and C from 1 goes to the right.

This hash table implementation looks pretty bad, because the hashes may need to be recalculated when inserting certain elements, but it doesn't matter.

---

BinTree1 is just an ordinary binary tree and is used for quick order sets. Nothing more to say about it.

---

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