balanced-binary-search-tree-1.0.0.0: Type safe BST and AVL trees
Copyright(c) Nicolás Rodríguez 2021
LicenseGPL-3
MaintainerNicolás Rodríguez
Stabilityexperimental
PortabilityPOSIX
Safe HaskellSafe
LanguageHaskell2010

Data.Tree.BST.Unsafe

Description

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

Synopsis

Documentation

data Node :: Type -> Type where Source #

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 Source #

Constructor of unsafe BST trees.

Constructors

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

emptyBST :: BST a Source #

Empty BST tree.

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

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 Source #

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

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

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 Source #

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

maxKeyDelete :: BST a -> BST a Source #

Delete the node with the maximum key value.

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

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

deleteBST :: Int -> BST a -> BST a Source #

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 Source #

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