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 aRedBlackDirections
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 asWhiteBranch
because it is also assumed to be red. 2nd parameter is the node content of the grandparent. 1st parameter is aRedBlackDirections
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 aRedBlackTree
. 3rd parameter is the parent as aRedBlackNode
. 2nd parameter is aRedBlackDirection
used to reconstruct the grandparent. 1st parameter is aRedBlackDirections
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 aRedBlackTree
. 3rd parameter is content of the parent. 2nd parameter is aRedBlackDirection
used to reconstruct the grandparent. 1st parameter is aRedBlackDirections
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 |