Data.RedBlackTree.BinaryTree

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.

Documentation

class Ord a => BinaryTreeNode a where

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.

Methods

mergeNodes :: a -> a -> a

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)

Defined in Data.RedBlackTree.Internal

Methods

mergeNodes :: RedBlackNode a -> RedBlackNode a -> RedBlackNode a

data BinaryTree a

A BinaryTree is either a Leaf (empty) or a BinaryTreeNode with 2 BinaryTree children: left and right.

Constructors

Leaf

Branch (BinaryTree a) a (BinaryTree a)

Instances

(BinaryTreeNode a, Show a) => Show (BinaryTree a)

Defined in Data.RedBlackTree.BinaryTree

Methods

showsPrec :: Int -> BinaryTree a -> ShowS

show :: BinaryTree a -> String

showList :: [BinaryTree a] -> ShowS

Eq a => Eq (BinaryTree a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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

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

Ord a => Ord (BinaryTree a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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

A BinaryTree can only have two types of branches: Left or Right

Constructors

LeftBranch

RightBranch

Instances

Show BranchType

Defined in Data.RedBlackTree.BinaryTree

Methods

showsPrec :: Int -> BranchType -> ShowS

show :: BranchType -> String

showList :: [BranchType] -> ShowS

Eq BranchType

Defined in Data.RedBlackTree.BinaryTree

Methods

(==) :: BranchType -> BranchType -> Bool

(/=) :: BranchType -> BranchType -> Bool

Ord BranchType

Defined in Data.RedBlackTree.BinaryTree

Methods

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)

A TreeBranch zipper. It is identical to TreeZipper except for the fact that Leaf values are not allowed in the zipper.

data TreeBranch a

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

Constructors

TreeBranch (BinaryTree a) a (BinaryTree a)

Instances

(BinaryTreeNode a, Show a) => Show (TreeBranch a)

Defined in Data.RedBlackTree.BinaryTree

Methods

showsPrec :: Int -> TreeBranch a -> ShowS

show :: TreeBranch a -> String

showList :: [TreeBranch a] -> ShowS

Eq a => Eq (TreeBranch a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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

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

Ord a => Ord (TreeBranch a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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

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.

Constructors

TreeDirection BranchType a (BinaryTree a)

Instances

(Show a, BinaryTreeNode a) => Show (TreeDirection a)

Defined in Data.RedBlackTree.BinaryTree

Methods

showsPrec :: Int -> TreeDirection a -> ShowS

show :: TreeDirection a -> String

showList :: [TreeDirection a] -> ShowS

Eq a => Eq (TreeDirection a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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

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

Ord a => Ord (TreeDirection a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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]

List of TreeDirection

data TreeInsertResult a

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

Constructors

InsertOk (TreeBranch a) (TreeDirection a)

InsertNotYet (BinaryTree a) (TreeDirection a) a

InsertMerge (TreeBranch a)

Instances

(BinaryTreeNode a, Show a) => Show (TreeInsertResult a)

Defined in Data.RedBlackTree.BinaryTree

Methods

showsPrec :: Int -> TreeInsertResult a -> ShowS

show :: TreeInsertResult a -> String

showList :: [TreeInsertResult a] -> ShowS

Eq a => Eq (TreeInsertResult a)

Defined in Data.RedBlackTree.BinaryTree

Methods

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

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

type TreeZipper a = (BinaryTree a, TreeDirections a)

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

appendRightChild :: BinaryTreeNode a => TreeBranch a -> a -> TreeInsertResult a

binaryTreeInsert :: BinaryTreeNode a => BinaryTree a -> a -> BranchZipper a

inserts an item to the BinaryTree. Returns a BranchZipper focusing on the recently inserted branch.

binaryTreeFind :: BinaryTreeNode a => BinaryTree a -> a -> Maybe a

Looks up an item in the BinaryTree. Returns Nothing if it was not found.

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