Copyright | (c) 2017 Gabriel Aumala |
---|---|

License | BSD3 |

Maintainer | gabriel@criptext.com |

Stability | experimental |

Portability | GHC |

Safe Haskell | Safe-Inferred |

Language | Haskell2010 |

Data types and functions used internally by Data.RedBlackTree's "insert" function. You don't need to know anything about this if you only want to consume the RedBlackTree library.

## Synopsis

- identifyRBTCase :: BinaryTreeNode a => TreeFamily (RedBlackNode a) -> RBTCase a
- insert :: BinaryTreeNode a => RedBlackTree a -> a -> RedBlackTree a
- data RBTCase a
- = Case1 (WhiteBranch a)
- | Case2 (RedBlackDirections a) (RedBlackBranch a)
- | Case3 (RedBlackDirections a) a (WhiteBranch a) (WhiteBranch a)
- | Case4 (RedBlackDirections a) (RedBlackDirection a) (RedBlackNode a) (RedBlackTree a) (RedBlackBranch a)
- | Case5 (RedBlackDirections a) (RedBlackDirection a) a (RedBlackTree a) (RedBlackBranch a)

# Documentation

identifyRBTCase :: BinaryTreeNode a => TreeFamily (RedBlackNode a) -> RBTCase a Source #

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.

The 5 possible cases of red–black tree insertion to handle:

- inserted node is the root node, i.e., first node of red–black tree.
Stored as a
`WhiteBranch`

because it should always be black. - inserted node has a parent, and it is black. The inserted node is stored
as a
`RedBlackBranch`

along with a`RedBlackDirections`

to reconstruct all of the ancestors. - inserted node has a parent and an uncle, and they are both red.
4th parameter is the inserted node as a
`WhiteBranch`

because it is assumed to be red. 3rd parameter is the uncle as`WhiteBranch`

because it is also assumed to be red. 2nd parameter is the node content of the grandparent. 1st parameter is a`RedBlackDirections`

to reconstruct all of the remaining ancestors. - inserted node is placed to right of left child of grandparent, or to left
of right child of grandparent. 5th parameter is the inserted node as a
`RedBlackBranch`

because it is assumed to be red but we don't care about it right now. 4th parameter is the sibling of the inserted node as a`RedBlackTree`

. 3rd parameter is the parent as a`RedBlackNode`

. 2nd parameter is a`RedBlackDirection`

used to reconstruct the grandparent. 1st parameter is a`RedBlackDirections`

to reconstruct all of the remaining ancestors. - inserted node is placed to left of left child of grandparent, or to right
of right child of grandparent. 5th parameter is the inserted node as a
`RedBlackBranch`

because it is assumed to be red but we don't care about it right now. 4th parameter is the sibling of the inserted node as a`RedBlackTree`

. 3rd parameter is content of the parent. 2nd parameter is a`RedBlackDirection`

used to reconstruct the grandparent. 1st parameter is a`RedBlackDirections`

to reconstruct all of the remaining ancestors.

This datatype holds the minimum information about the tree to be able to handle each case.

Case1 (WhiteBranch a) | |

Case2 (RedBlackDirections a) (RedBlackBranch a) | |

Case3 (RedBlackDirections a) a (WhiteBranch a) (WhiteBranch a) | |

Case4 (RedBlackDirections a) (RedBlackDirection a) (RedBlackNode a) (RedBlackTree a) (RedBlackBranch a) | |

Case5 (RedBlackDirections a) (RedBlackDirection a) a (RedBlackTree a) (RedBlackBranch a) |

#### Instances

(BinaryTreeNode a, Show a) => Show (RBTCase a) Source # | |

BinaryTreeNode a => Eq (RBTCase a) Source # | |

BinaryTreeNode a => Ord (RBTCase a) Source # | |

Defined in Data.RedBlackTree.InsertionAlgorithm |