Trees can be comprised of either empty leaves or nodes containing a value, a represesentative colour and two child branches.

The DoubleEmpty value is only used when deleting, so isn't needed when constructing trees manually.

Since this is a red black tree representation, we ignore the green brown convention.

The additional DoubleBlack and NegativeBlack colours are required for deletion purposes, thus aren't usually used when building trees.

An empty tree for ease of use when constructing trees.

empty
--> Empty

A tree with a single value inserted into it. Since this is a single node tree, it's colour is black by definition.

singleton 5
--> Node 5 Black Empty Empty

Generate a Red Black representation of a list.

fromList [ 2, 7, 8, 3, 9, 1, 5, 10 ]
--> Node 7 Black (Node 3 Red (Node 2 Black (Node 1 Red Empty Empty) Empty) (Node 5 Black Empty Empty)) (Node 9 Red (Node 8 Black Empty Empty) (Node 10 Black Empty Empty))

Adds a new value to the tree. Since this may cause on of the four red black constraints to be broken, there may be a need to recolour nodes or rebalance the tree.

singleton 8 |> insert 1
--> Node 8 Black (Node 1 Red Empty Empty) Empty

Remove a node from the tree. Most of the time this is a straightforward matter, except for when a black node with no children is removed. This ultimately changes the (blackHeight)[#blackHeight] and thus the entire tree must be rebalanced and recoloured.

tree = fromList [1,2,3,4]
--> Node 2 Black (Node 1 Black Empty Empty) (Node 3 Black Empty (Node 4 Red Empty Empty))


delete 1 tree
--> Node 3 Black (Node 2 Black Empty Empty) (Node 4 Black Empty Empty)


delete 2 tree
--> Node 3 Black (Node 1 Black Empty Empty) (Node 4 Black Empty Empty)


delete 3 tree
--> Node 2 Black (Node 1 Black Empty Empty) (Node 4 Black Empty Empty)


delete 4 tree
--> Node 2 Black (Node 1 Black Empty Empty) (Node 3 Black Empty Empty)

A pre-order depth-first search: start at the root, then traverse the left branch followed by the right branch.

fromList [ 2, 5, 6, 7, 1, 8, 4, 3 ] |> preOrder
--> [ 5, 3, 2, 1, 4, 7, 6, 8 ]

An in-order depth-first search: traverse the left branch, add the root, then finish with the right branch. This ordering is sorted by convention.

fromList [ 2, 5, 6, 7, 1, 8, 4, 3 ] |> inOrder
--> [ 1, 2, 3, 4, 5, 6, 7, 8 ]

A post-order depth-first search: traverse the left branch followed by the right branch and finishing with the root.

fromList [ 2, 5, 6, 7, 1, 8, 4, 3 ] |> postOrder
--> [ 1, 2, 4, 3, 6, 8, 7, 5 ]

A breadth-first search traversing the tree in level order, starting from the root and travering down.

fromList [ 2, 5, 6, 7, 1, 8, 4, 3 ] |> levelOrder
--> [ 5, 3, 7, 2, 4, 6, 8, 1 ]

Check if a value currently exists within in a tree.

fromList [ 1, 2, 3 ] |> isMember 72
--> False

Count the number of elements in the tree.

fromList [ 3, 8, 16 ] |> size
--> 3

Every path from the root to the leaves of a red black tree must contain the same number of black nodes. The blackHeight is the value of this path length. Notably, this is also the shortest path from root to leaf.

fromList [ 2, 7, 4, 9, 1, 3, 18, 10 ] |> blackHeight
--> Just 2

Calling blackHeight on a valid red black tree will return a count, but if the tree is not correctly balanced, this function will return Nothing.

Calculate the height of the tree.

fromList [ 8, 24, 17, 32, 9, 1, 12, 7 ] |> height
--> 4

The longest path from the root to a leaf is at most twice the length of the shortest path.

height tree <= 2 * (Maybe.withDefault 0 <| blackHeight tree)
--> True

Finds largest element in tree. Returns Nothing if tree is Empty.

fromList [1,9,2,7] |> maximum
--> Just 9

Generate a list of values contained in the tree. Since Red Black trees are an extention of Binary Search Trees, the resultant list will be sorted. Colour is ignored in this operation.

tree = fromList [ 8, 1, 2, 6, 29, 42, 7, 22, 18, 36 ]
--> Node 7 Black (Node 2 Black (Node 1 Black Empty Empty) (Node 6 Black Empty Empty)) (Node 29 Black (Node 18 Red (Node 8 Black Empty Empty) (Node 22 Black Empty Empty)) (Node 42 Black (Node 36 Red Empty Empty) Empty))


flatten tree
--> [ 1, 2, 6, 7, 8, 18, 22, 29, 36, 42 ]

Verifies that a given tree is a valid red black tree by checking

1. It satisfies the binary search order property
2. The root node is coloured Black
3. No red node has a child node that is also red
4. Every path from the root to a leaf contains the same number of black nodes

fromList [ 1, 2, 3, 4 ] |> isValid
--> True