Data.Tree.BST.Unsafe

Implementation of unsafe BST trees. These trees have no type level information useful for compile time verification of invariants.

Documentation

data Node :: Type -> Type where

Nodes for unsafe BST trees. They only hold information at the value level: some value of type a and a key of type Int.

Constructors

Node :: Show a => Int -> a -> Node a

data BST :: Type -> Type where

Constructor of unsafe BST trees.

Constructors

E :: BST a

F :: BST a -> Node a -> BST a -> BST a

emptyBST :: BST a

Empty BST tree.

insertBST :: Show a => Int -> a -> BST a -> BST a

Entry point for inserting a new key and value. If the key is already present in the tree, update the value.

insertBST' :: Node a -> BST a -> Ordering -> BST a

Insertion algorithm. It has the additional parameter of type Ordering, which guides the recursion.

lookupBST :: Int -> BST a -> Maybe a

Lookup the given key in the tree. It returns Nothing if tree is empty or if it doesn't have the key.

lookupBST' :: Int -> BST a -> Ordering -> Maybe a

Lookup algorithm. It has the additional parameter of type Ordering, which guides the recursion.

maxKeyDelete :: BST a -> BST a

Delete the node with the maximum key value.

maxNode :: BST a -> Maybe (Node a)

Get the node with maximum key value. | It returns Nothing if tree is empty.

deleteBST :: Int -> BST a -> BST a

Delete the node with the given key. If the key is not in the tree, return the same tree.

deleteBST' :: Int -> BST a -> Ordering -> BST a

Deletion algorithm. It has the additional parameter of type Ordering, which guides the recursion.