| Copyright | (c) 2017 Gabriel Aumala |
|---|---|
| License | BSD3 |
| Maintainer | gabriel@criptext.com |
| Stability | experimental |
| Portability | GHC |
| Safe Haskell | Safe-Inferred |
| Language | Haskell2010 |
Data.RedBlackTree.Internal
Description
Data types and functions used internally by Data.RedBlackTree. You don't need to know anything about this if you only want to consume the RedBlackTree library.
Synopsis
- branchIsColor :: BinaryTreeNode a => TreeBranch (RedBlackNode a) -> RedBlack -> Bool
- getBlackHeight :: BinaryTreeNode a => RedBlackTree a -> Int
- isColor :: BinaryTreeNode a => RedBlackNode a -> RedBlack -> Bool
- emptyRedBlackTree :: RedBlackTree a
- find :: BinaryTreeNode a => RedBlackTree a -> a -> Maybe a
- paintItBlack :: BinaryTreeNode a => RedBlackNode a -> RedBlackNode a
- removeBranchColor :: BinaryTreeNode a => RedBlackBranch a -> WhiteBranch a
- whiteBranch2Tree :: BinaryTreeNode a => WhiteBranch a -> RedBlack -> RedBlackTree a
- data RedBlack
- data RedBlackNode a = RedBlackNode RedBlack a
- type RedBlackBranch a = TreeBranch (RedBlackNode a)
- type RedBlackTree a = BinaryTree (RedBlackNode a)
- type RedBlackDirection a = TreeDirection (RedBlackNode a)
- type RedBlackDirections a = [RedBlackDirection a]
- data WhiteBranch a = WhiteBranch (RedBlackTree a) a (RedBlackTree a)
Documentation
branchIsColor :: BinaryTreeNode a => TreeBranch (RedBlackNode a) -> RedBlack -> Bool Source #
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.
isColor :: BinaryTreeNode a => RedBlackNode a -> RedBlack -> Bool Source #
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
paintItBlack :: BinaryTreeNode a => RedBlackNode a -> RedBlackNode a Source #
removeBranchColor :: BinaryTreeNode a => RedBlackBranch a -> WhiteBranch a Source #
whiteBranch2Tree :: BinaryTreeNode a => WhiteBranch a -> RedBlack -> RedBlackTree a Source #
Red black trees can only have two types of nodes: Red and Black.
data RedBlackNode a Source #
a RedBlackNode contains only two elements, the color of the node and the
actual content.
Constructors
| RedBlackNode RedBlack a |
Instances
type RedBlackBranch a = TreeBranch (RedBlackNode a) Source #
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
type RedBlackDirection a = TreeDirection (RedBlackNode a) Source #
type RedBlackDirections a = [RedBlackDirection a] Source #
data WhiteBranch a Source #
Constructors
| WhiteBranch (RedBlackTree a) a (RedBlackTree a) |
Instances
| (BinaryTreeNode a, Show a) => Show (WhiteBranch a) Source # | |
Defined in Data.RedBlackTree.Internal Methods showsPrec :: Int -> WhiteBranch a -> ShowS # show :: WhiteBranch a -> String # showList :: [WhiteBranch a] -> ShowS # | |
| BinaryTreeNode a => Eq (WhiteBranch a) Source # | |
Defined in Data.RedBlackTree.Internal Methods (==) :: WhiteBranch a -> WhiteBranch a -> Bool # (/=) :: WhiteBranch a -> WhiteBranch a -> Bool # | |
| BinaryTreeNode a => Ord (WhiteBranch a) Source # | |
Defined in Data.RedBlackTree.Internal Methods compare :: WhiteBranch a -> WhiteBranch a -> Ordering # (<) :: WhiteBranch a -> WhiteBranch a -> Bool # (<=) :: WhiteBranch a -> WhiteBranch a -> Bool # (>) :: WhiteBranch a -> WhiteBranch a -> Bool # (>=) :: WhiteBranch a -> WhiteBranch a -> Bool # max :: WhiteBranch a -> WhiteBranch a -> WhiteBranch a # min :: WhiteBranch a -> WhiteBranch a -> WhiteBranch a # | |