Copyright | (c) 2017 Gabriel Aumala |
---|---|
License | BSD3 |
Maintainer | gabriel@criptext.com |
Stability | experimental |
Portability | GHC |
Safe Haskell | Safe-Inferred |
Language | Haskell2010 |
A Binary Search Tree implementation. It exposes various functions to operate on the tree that are used internally by Data.RedBlackTree. This is meant to be used exclusively by Data.RedBlackTree.Internal, it is not adequate to be used as a standalone binary tree structure.
Synopsis
- class Ord a => BinaryTreeNode a where
- mergeNodes :: a -> a -> a
- data BinaryTree a
- = Leaf
- | Branch (BinaryTree a) a (BinaryTree a)
- data BranchType
- type BranchZipper a = (TreeBranch a, TreeDirections a)
- data TreeBranch a = TreeBranch (BinaryTree a) a (BinaryTree a)
- data TreeDirection a = TreeDirection BranchType a (BinaryTree a)
- type TreeDirections a = [TreeDirection a]
- data TreeInsertResult a
- = InsertOk (TreeBranch a) (TreeDirection a)
- | InsertNotYet (BinaryTree a) (TreeDirection a) a
- | InsertMerge (TreeBranch a)
- type TreeZipper a = (BinaryTree a, TreeDirections a)
- appendLeftChild :: BinaryTreeNode a => TreeBranch a -> a -> TreeInsertResult a
- appendRightChild :: BinaryTreeNode a => TreeBranch a -> a -> TreeInsertResult a
- binaryTreeInsert :: BinaryTreeNode a => BinaryTree a -> a -> BranchZipper a
- binaryTreeFind :: BinaryTreeNode a => BinaryTree a -> a -> Maybe a
- branch2Tree :: BinaryTreeNode a => TreeBranch a -> BinaryTree a
- branchZipperInsert :: BinaryTreeNode a => BranchZipper a -> a -> BranchZipper a
- getTreeRoot :: BinaryTreeNode a => BranchZipper a -> BranchZipper a
- goLeft :: BinaryTreeNode a => BranchZipper a -> TreeZipper a
- goUp :: BinaryTreeNode a => BranchZipper a -> Maybe (BranchZipper a)
- goRight :: BinaryTreeNode a => BranchZipper a -> TreeZipper a
- reconstructAncestor :: BinaryTreeNode a => TreeBranch a -> TreeDirection a -> TreeBranch a
Documentation
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.
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 mergeNodes :: RedBlackNode a -> RedBlackNode a -> RedBlackNode a Source # |
data BinaryTree a Source #
A BinaryTree
is either a Leaf
(empty) or a BinaryTreeNode
with 2 BinaryTree
children: left and right.
Leaf | |
Branch (BinaryTree a) a (BinaryTree a) |
Instances
(BinaryTreeNode a, Show a) => Show (BinaryTree a) Source # | |
Defined in Data.RedBlackTree.BinaryTree showsPrec :: Int -> BinaryTree a -> ShowS # show :: BinaryTree a -> String # showList :: [BinaryTree a] -> ShowS # | |
Eq a => Eq (BinaryTree a) Source # | |
Defined in Data.RedBlackTree.BinaryTree (==) :: BinaryTree a -> BinaryTree a -> Bool # (/=) :: BinaryTree a -> BinaryTree a -> Bool # | |
Ord a => Ord (BinaryTree a) Source # | |
Defined in Data.RedBlackTree.BinaryTree compare :: BinaryTree a -> BinaryTree a -> Ordering # (<) :: BinaryTree a -> BinaryTree a -> Bool # (<=) :: BinaryTree a -> BinaryTree a -> Bool # (>) :: BinaryTree a -> BinaryTree a -> Bool # (>=) :: BinaryTree a -> BinaryTree a -> Bool # max :: BinaryTree a -> BinaryTree a -> BinaryTree a # min :: BinaryTree a -> BinaryTree a -> BinaryTree a # |
data BranchType Source #
A BinaryTree can only have two types of branches: Left or Right
Instances
Show BranchType Source # | |
Defined in Data.RedBlackTree.BinaryTree showsPrec :: Int -> BranchType -> ShowS # show :: BranchType -> String # showList :: [BranchType] -> ShowS # | |
Eq BranchType Source # | |
Defined in Data.RedBlackTree.BinaryTree (==) :: BranchType -> BranchType -> Bool # (/=) :: BranchType -> BranchType -> Bool # | |
Ord BranchType Source # | |
Defined in Data.RedBlackTree.BinaryTree compare :: BranchType -> BranchType -> Ordering # (<) :: BranchType -> BranchType -> Bool # (<=) :: BranchType -> BranchType -> Bool # (>) :: BranchType -> BranchType -> Bool # (>=) :: BranchType -> BranchType -> Bool # max :: BranchType -> BranchType -> BranchType # min :: BranchType -> BranchType -> BranchType # |
type BranchZipper a = (TreeBranch a, TreeDirections a) Source #
A TreeBranch
zipper. It is identical to TreeZipper
except for the fact
that Leaf
values are not allowed in the zipper.
data TreeBranch a Source #
Holds the data of a BinaryTree
created with the Branch
constructor. Useful
type when you want to guarantee that the element is not a Leaf
TreeBranch (BinaryTree a) a (BinaryTree a) |
Instances
(BinaryTreeNode a, Show a) => Show (TreeBranch a) Source # | |
Defined in Data.RedBlackTree.BinaryTree showsPrec :: Int -> TreeBranch a -> ShowS # show :: TreeBranch a -> String # showList :: [TreeBranch a] -> ShowS # | |
Eq a => Eq (TreeBranch a) Source # | |
Defined in Data.RedBlackTree.BinaryTree (==) :: TreeBranch a -> TreeBranch a -> Bool # (/=) :: TreeBranch a -> TreeBranch a -> Bool # | |
Ord a => Ord (TreeBranch a) Source # | |
Defined in Data.RedBlackTree.BinaryTree compare :: TreeBranch a -> TreeBranch a -> Ordering # (<) :: TreeBranch a -> TreeBranch a -> Bool # (<=) :: TreeBranch a -> TreeBranch a -> Bool # (>) :: TreeBranch a -> TreeBranch a -> Bool # (>=) :: TreeBranch a -> TreeBranch a -> Bool # max :: TreeBranch a -> TreeBranch a -> TreeBranch a # min :: TreeBranch a -> TreeBranch a -> TreeBranch a # |
data TreeDirection a Source #
Minimum necessary to reconstruct the parent of any focused node. First argument
is the BranchType
of the focused node relative to the parent. Second argument
is the parent's node. The third argument is the sibling tree of the focused
node.
Instances
(Show a, BinaryTreeNode a) => Show (TreeDirection a) Source # | |
Defined in Data.RedBlackTree.BinaryTree showsPrec :: Int -> TreeDirection a -> ShowS # show :: TreeDirection a -> String # showList :: [TreeDirection a] -> ShowS # | |
Eq a => Eq (TreeDirection a) Source # | |
Defined in Data.RedBlackTree.BinaryTree (==) :: TreeDirection a -> TreeDirection a -> Bool # (/=) :: TreeDirection a -> TreeDirection a -> Bool # | |
Ord a => Ord (TreeDirection a) Source # | |
Defined in Data.RedBlackTree.BinaryTree compare :: TreeDirection a -> TreeDirection a -> Ordering # (<) :: TreeDirection a -> TreeDirection a -> Bool # (<=) :: TreeDirection a -> TreeDirection a -> Bool # (>) :: TreeDirection a -> TreeDirection a -> Bool # (>=) :: TreeDirection a -> TreeDirection a -> Bool # max :: TreeDirection a -> TreeDirection a -> TreeDirection a # min :: TreeDirection a -> TreeDirection a -> TreeDirection a # |
type TreeDirections a = [TreeDirection a] Source #
List of TreeDirection
data TreeInsertResult a Source #
The result from inserting a node to the left or right of a tree can be:
- (
InsertOk insertedTree directionToNewTree
) if there is a leaf at the attempted insert position - (
InsertNotYet obstructingTree directionToObstructingTree nodeToInsert
) if there already is a tree obstructing the desired position, we must go further down - (
InsertMerge mergedBranch
) the node to insert is equal to the tree's node so they were merged and the tree's size remains the same
InsertOk (TreeBranch a) (TreeDirection a) | |
InsertNotYet (BinaryTree a) (TreeDirection a) a | |
InsertMerge (TreeBranch a) |
Instances
(BinaryTreeNode a, Show a) => Show (TreeInsertResult a) Source # | |
Defined in Data.RedBlackTree.BinaryTree showsPrec :: Int -> TreeInsertResult a -> ShowS # show :: TreeInsertResult a -> String # showList :: [TreeInsertResult a] -> ShowS # | |
Eq a => Eq (TreeInsertResult a) Source # | |
Defined in Data.RedBlackTree.BinaryTree (==) :: TreeInsertResult a -> TreeInsertResult a -> Bool # (/=) :: TreeInsertResult a -> TreeInsertResult a -> Bool # |
type TreeZipper a = (BinaryTree a, TreeDirections a) Source #
A BinaryTree
zipper. the first value of the tuple is the focused BinaryTree
,
while the second argument is the list of directions used to move up to the
parent and other ancestors.
It is used to navigate up an down in a BinaryTree.
appendLeftChild :: BinaryTreeNode a => TreeBranch a -> a -> TreeInsertResult a Source #
appendRightChild :: BinaryTreeNode a => TreeBranch a -> a -> TreeInsertResult a Source #
binaryTreeInsert :: BinaryTreeNode a => BinaryTree a -> a -> BranchZipper a Source #
inserts an item to the BinaryTree. Returns a BranchZipper
focusing
on the recently inserted branch.
binaryTreeFind :: BinaryTreeNode a => BinaryTree a -> a -> Maybe a Source #
Looks up an item in the BinaryTree. Returns Nothing if it was not found.
branch2Tree :: BinaryTreeNode a => TreeBranch a -> BinaryTree a Source #
branchZipperInsert :: BinaryTreeNode a => BranchZipper a -> a -> BranchZipper a Source #
getTreeRoot :: BinaryTreeNode a => BranchZipper a -> BranchZipper a Source #
goLeft :: BinaryTreeNode a => BranchZipper a -> TreeZipper a Source #
goUp :: BinaryTreeNode a => BranchZipper a -> Maybe (BranchZipper a) Source #
goRight :: BinaryTreeNode a => BranchZipper a -> TreeZipper a Source #
reconstructAncestor :: BinaryTreeNode a => TreeBranch a -> TreeDirection a -> TreeBranch a Source #