Data.Tree.AVL.Unsafe

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

Documentation

data Node :: Type -> Type where

Nodes for unsafe AVL 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 AVL :: Type -> Type where

Constructor of unsafe AVL trees.

Constructors

E :: AVL a

F :: AVL a -> Node a -> AVL a -> AVL a

data AlmostAVL :: Type -> Type where

Constructor of unsafe AlmostAVL trees. These trees have left and right AVL sub trees, but the overall tree may not be balanced.

Constructors

FF :: AVL a -> Node a -> AVL a -> AlmostAVL a

emptyAVL :: AVL a

Empty AVL tree.

height :: AVL a -> Int

Get the height of a tree.

data US

Data type that represents the state of unbalance of the sub trees:

LeftUnbalanced

height(left sub tree) = height(right sub tree) + 2

RightUnbalanced

height(right sub tree) = height(left sub tree) + 2

NotUnbalanced

tree is not unbalanced

Constructors

LeftUnbalanced

RightUnbalanced

NotUnbalanced

unbalancedState :: Int -> Int -> US

Check from two natural numbers, that represent the heights of some left and right sub trees, if the tree is balanced or if some of those sub trees is unbalanced.

data BS

Data type that represents the state of balance of the sub trees in a balanced tree:

LeftHeavy

height(left sub tree) = height(right sub tree) + 1

RightHeavy

height(right sub tree) = height(left sub tree) + 1

Balanced

height(left sub tree) = height(right sub tree)

Constructors

LeftHeavy

RightHeavy

Balanced

balancedState :: Int -> Int -> BS

Check from two natural numbers, that represent the heights of some left and right sub trees, if some of those sub trees have height larger than the other.

balance :: AlmostAVL a -> AVL a

Balance a tree.

balance' :: AlmostAVL a -> US -> AVL a

Balancing algorithm. It has the additional parameter of type US, which decides the proper rotation to be applied.

rotate :: AlmostAVL a -> US -> BS -> AVL a

Apply a rotation to a tree.

insertAVL :: Show a => Int -> a -> AVL a -> AVL a

Insert a new key and value. If the key is already present in the tree, update the value.

insertAVL' :: Node a -> AVL a -> Ordering -> AVL a

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

lookupAVL :: Int -> AVL 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.

lookupAVL' :: Int -> AVL a -> Ordering -> Maybe a

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

maxKeyDelete :: AVL a -> AVL a

Delete the node with the maximum key value.

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

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

deleteAVL :: Int -> AVL a -> AVL a

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

deleteAVL' :: Int -> AVL a -> Ordering -> AVL a

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