RedBlackTrees

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].

Types

type RedBlackTree comparable

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

type Colour

= Red

| Black

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

Building

empty : RedBlackTree comparable

An empty tree for ease of use when constructing trees.

empty == Empty

singleton : comparable -> RedBlackTree comparable

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

fromList : List comparable -> RedBlackTree comparable

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))

insert : comparable -> RedBlackTree comparable -> RedBlackTree comparable

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

Utilities

isMember : comparable -> RedBlackTree comparable -> Bool

Check if a value currently exists within in a tree.

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

size : RedBlackTree comparable -> Int

Count the number of elements in the tree.

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

blackHeight : RedBlackTree comparable -> Maybe Int

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.

height : RedBlackTree comparable -> Int

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

flatten : RedBlackTree comparable -> List comparable

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 ]

Validation

isValid : RedBlackTree comparable -> Bool

Verifies 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

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

Modules

RedBlackTrees