Module red_black_tree.api

This file implements the red-black trees described in the chapter 3.3 of Okasaki's "Purely functional data structures".

Also, it implements the removal of an element inside the tree as demonstrated in Germane and Might's functional pearl "Deletion: The curse of the red-black tree"

It is based on the implementation for the binary trees.

Red-black trees are self-balanced, and always ensure that the path from the root to the farthest leaf is no more than twice as long as the path from the root to the nearest leaf.

The operations of research, insertion and deletion are done in O(log(n)) time in the average and in the worst case.

Index

Variables

Functions