Data.RedBlackTree.InsertionAlgorithm

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.

Documentation

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

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

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

data RBTCase a

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

1. inserted node is the root node, i.e., first node of red–black tree. Stored as a WhiteBranch because it should always be black.
2. 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.
3. 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.
4. 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.
5. 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.

Constructors

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)

Defined in Data.RedBlackTree.InsertionAlgorithm

Methods

showsPrec :: Int -> RBTCase a -> ShowS

show :: RBTCase a -> String

showList :: [RBTCase a] -> ShowS

BinaryTreeNode a => Eq (RBTCase a)

Defined in Data.RedBlackTree.InsertionAlgorithm

Methods

(==) :: RBTCase a -> RBTCase a -> Bool

(/=) :: RBTCase a -> RBTCase a -> Bool

BinaryTreeNode a => Ord (RBTCase a)

Defined in Data.RedBlackTree.InsertionAlgorithm

Methods

compare :: RBTCase a -> RBTCase a -> Ordering

(<) :: RBTCase a -> RBTCase a -> Bool

(<=) :: RBTCase a -> RBTCase a -> Bool

(>) :: RBTCase a -> RBTCase a -> Bool

(>=) :: RBTCase a -> RBTCase a -> Bool

max :: RBTCase a -> RBTCase a -> RBTCase a

min :: RBTCase a -> RBTCase a -> RBTCase a