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 #