red-black-tree- Red Black Trees implemented in Haskell
Copyright(c) 2017 Gabriel Aumala
Safe HaskellSafe-Inferred



A Red Black Tree is a self balancing binary search tree in which each node has a color: red or black. Everytime a node is inserted, the tree performs rotations and repaints nodes to ensure the following properties about the tree:

  1. Each node is either red or black.
  2. The root node is black.
  3. All leaves (empty nodes at the bottom of the tree) are black.
  4. If a node is red, then both its children are black.
  5. Every path from a given node to any of its leaf nodes contains the same number of black nodes (black height).

As long as these properties remain true, the tree is balanced. Balancing is not perfect, but it is good enough to ensure O(log(n)) lookup and insertion.


Data Structure definitions

type RedBlackTree a = BinaryTree (RedBlackNode a) Source #

A BinaryTree with only nodes of type RedBlackNode. is either a Leaf (empty) or a RedBlackNode with 2 RedBlackTree children: left and right

class Ord a => BinaryTreeNode a where Source #

Only types that are members of BinaryTreeNode can be inserted into a BinaryTree.

The purpose of the class is to provide a method to merge nodes with equal values since inserting different nodes with equal values can corrupt the tree.


mergeNodes :: a -> a -> a Source #

The BinaryTree will call this function when it tries to insert a value that already exists in the tree. The first argument is guaranteed to be the one that is already in the tree, while the second argument is the node that the tree is trying to insert. Since the two nodes can't exist in the same tree The result should be a merged node that will be inserted instead of the other two.


Instances details
BinaryTreeNode a => BinaryTreeNode (RedBlackNode a) Source # 
Instance details

Defined in Data.RedBlackTree.Internal


emptyRedBlackTree :: RedBlackTree a Source #

Convenient function to "create" a new empty tree.


find :: BinaryTreeNode a => RedBlackTree a -> a -> Maybe a Source #

Lookup a target node in the tree. The target value doesn't need to be the exact same value that is already in the tree. It only needs to satisfy the Eq instance

insert :: BinaryTreeNode a => RedBlackTree a -> a -> RedBlackTree a Source #

inserts a new node to the tree, performing the necessary rotations to guarantee that the red black properties are kept after the insertion.

getBlackHeight :: BinaryTreeNode a => RedBlackTree a -> Int Source #

Returns the black-height of a RedBlackTree, the uniform number of black nodes in any path from the root to any leaf at the bottom of the tree. This is a O(Log(n)) operation.