Copyright	(c) Nicolás Rodríguez 2021
License	GPL-3
Maintainer	Nicolás Rodríguez
Stability	experimental
Portability	POSIX
Safe Haskell	Safe
Language	Haskell2010

Data.Tree.AVL.Unsafe

Description

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

Synopsis

data Node :: Type -> Type where
- Node :: Show a => Int -> a -> Node a
data AVL :: Type -> Type where
- E :: AVL a
- F :: AVL a -> Node a -> AVL a -> AVL a
data AlmostAVL :: Type -> Type where
- FF :: AVL a -> Node a -> AVL a -> AlmostAVL a
emptyAVL :: AVL a
height :: AVL a -> Int
data US
- = LeftUnbalanced
- | RightUnbalanced
- | NotUnbalanced
unbalancedState :: Int -> Int -> US
data BS
- = LeftHeavy
- | RightHeavy
- | Balanced
balancedState :: Int -> Int -> BS
balance :: AlmostAVL a -> AVL a
balance' :: AlmostAVL a -> US -> AVL a
rotate :: AlmostAVL a -> US -> BS -> AVL a
insertAVL :: Show a => Int -> a -> AVL a -> AVL a
insertAVL' :: Node a -> AVL a -> Ordering -> AVL a
lookupAVL :: Int -> AVL a -> Maybe a
lookupAVL' :: Int -> AVL a -> Ordering -> Maybe a
maxKeyDelete :: AVL a -> AVL a
maxNode :: AVL a -> Maybe (Node a)
deleteAVL :: Int -> AVL a -> AVL a
deleteAVL' :: Int -> AVL a -> Ordering -> AVL a

Documentation

data Node :: Type -> Type where Source #

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

Constructor of unsafe AVL trees.

Constructors

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

data AlmostAVL :: Type -> Type where Source #

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

Empty AVL tree.

height :: AVL a -> Int Source #

Get the height of a tree.

data US Source #

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

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

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

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

Balance a tree.

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

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

Apply a rotation to a tree.

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

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

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

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

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

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

maxKeyDelete :: AVL a -> AVL a Source #

Delete the node with the maximum key value.

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

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

deleteAVL :: Int -> AVL a -> AVL a Source #

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

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