| Copyright | (c) 2017 Gabriel Aumala |
|---|---|
| License | BSD3 |
| Maintainer | gabriel@criptext.com |
| Stability | experimental |
| Portability | GHC |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.RedBlackTree
Description
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:
- Each node is either red or black.
- The root node is black.
- All leaves (empty nodes at the bottom of the tree) are black.
- If a node is red, then both its children are black.
- 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.
Synopsis
- type RedBlackTree a = BinaryTree (RedBlackNode a)
- class Ord a => BinaryTreeNode a where
- mergeNodes :: a -> a -> a
- emptyRedBlackTree :: RedBlackTree a
- find :: BinaryTreeNode a => RedBlackTree a -> a -> Maybe a
- insert :: BinaryTreeNode a => RedBlackTree a -> a -> RedBlackTree a
- getBlackHeight :: BinaryTreeNode a => RedBlackTree a -> Int
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.
Methods
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
| BinaryTreeNode a => BinaryTreeNode (RedBlackNode a) Source # | |
Defined in Data.RedBlackTree.Internal Methods mergeNodes :: RedBlackNode a -> RedBlackNode a -> RedBlackNode a Source # | |
Creation
emptyRedBlackTree :: RedBlackTree a Source #
Convenient function to "create" a new empty tree.
Operations
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.