Red Black Trees are self-balancing binary seach trees which add one bit of memory to the standard BST (usually denoted by the colours red and black). With this additional tracking information; the worst case search, insert and delete time complexity drops to O(log N) [from O(N) in the BST case].
Since this is a red black tree representation, we ignore the green brown convention.
An empty tree for ease of use when constructing trees.
Generate a Red Black representation of a list.
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.
Check if a value currently exists within in a tree.
Count the number of elements in the tree.
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.
Calculate the height of the tree. 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) == TrueVerifies that a given tree is a valid red black tree by checking
It satisfies the binary search order property
The root node is coloured Black
No red node has a child node that is also red
Every path from the root to a leaf contains the same number of black nodes
Trees can be comprised of either empty leaves or nodes containing a value, a represesentative colour and two child branches.