Copyright | (C) Frank Staals |
---|---|

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

Several types of Binary trees.

## Synopsis

- data BinLeafTree v a
- = Leaf !a
- | Node (BinLeafTree v a) !v (BinLeafTree v a)

- node :: Measured v a => BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a
- asBalancedBinLeafTree :: NonEmpty a -> BinLeafTree Size (Elem a)
- foldUp :: (b -> v -> b -> b) -> (a -> b) -> BinLeafTree v a -> b
- foldUpData :: (w -> v -> w -> w) -> (a -> w) -> BinLeafTree v a -> BinLeafTree w a
- zipExactWith :: (u -> v -> w) -> (a -> b -> c) -> BinLeafTree u a -> BinLeafTree v b -> BinLeafTree w c
- toRoseTree :: BinLeafTree v a -> Tree (TreeNode v a)
- drawTree :: (Show v, Show a) => BinLeafTree v a -> String
- data BinaryTree a
- = Nil
- | Internal (BinaryTree a) !a (BinaryTree a)

- access :: BinaryTree a -> Maybe a
- asBalancedBinTree :: [a] -> BinaryTree a
- foldBinaryUp :: b -> (a -> b -> b -> b) -> BinaryTree a -> BinaryTree (a, b)
- toRoseTree' :: BinaryTree a -> Maybe (Tree a)
- drawTree' :: Show a => BinaryTree a -> String

# Documentation

data BinLeafTree v a Source #

Binary tree that stores its values (of type a) in the leaves. Internal nodes store something of type v.

Leaf !a | |

Node (BinLeafTree v a) !v (BinLeafTree v a) |

#### Instances

node :: Measured v a => BinLeafTree v a -> BinLeafTree v a -> BinLeafTree v a Source #

smart constructor

asBalancedBinLeafTree :: NonEmpty a -> BinLeafTree Size (Elem a) Source #

Create a balanced tree, i.e. a tree of height \(O(\log n)\) with the elements in the leaves.

\(O(n)\) time.

foldUp :: (b -> v -> b -> b) -> (a -> b) -> BinLeafTree v a -> b Source #

Given a function to combine internal nodes into b's and leafs into b's, traverse the tree bottom up, and combine everything into one b.

foldUpData :: (w -> v -> w -> w) -> (a -> w) -> BinLeafTree v a -> BinLeafTree w a Source #

Traverses the tree bottom up, recomputing the assocated values.

zipExactWith :: (u -> v -> w) -> (a -> b -> c) -> BinLeafTree u a -> BinLeafTree v b -> BinLeafTree w c Source #

Takes two trees, that have the same structure, and uses the provided functions to "zip" them together

# Converting into a Data.Tree

toRoseTree :: BinLeafTree v a -> Tree (TreeNode v a) Source #

\( O(n) \) Convert binary tree to a rose tree, aka `Tree`

.

drawTree :: (Show v, Show a) => BinLeafTree v a -> String Source #

2-dimensional ASCII drawing of a tree.

# Internal Node Tree

data BinaryTree a Source #

Binary tree in which we store the values of type a in internal nodes.

Nil | |

Internal (BinaryTree a) !a (BinaryTree a) |

#### Instances

access :: BinaryTree a -> Maybe a Source #

Get the element stored at the root, if it exists

asBalancedBinTree :: [a] -> BinaryTree a Source #

Create a balanced binary tree.

running time: \(O(n)\)

foldBinaryUp :: b -> (a -> b -> b -> b) -> BinaryTree a -> BinaryTree (a, b) Source #

Fold function for folding over a binary tree.

toRoseTree' :: BinaryTree a -> Maybe (Tree a) Source #

Convert a `BinaryTree`

into a RoseTree