examples - 0.0.0

Data.Set.AVL

Description

AVL trees are a type of self-balancing binary search tree, where the heights of the left and right subtrees of every node differ by at most 1. This ensures that the height of the tree is logarithmic in the number of nodes, which guarantees efficient insertion, deletion, and search operations (all are guaranteed to run in 𝒪(log 𝓃) time). This module defines an AVL tree data type and provides functions for constructing, modifying, and querying AVL trees.

Definitions

type AVLTree (A : Type)Source#

A self-balancing binary search tree.

Constructors

| empty

An empty AVL tree.

| node A Nat (AVLTree A) (AVLTree A)

A node of an AVL tree.

height {A} : AVLTree A -> NatSource#

𝒪(1) Retrieves the height of an AVLTree. The height is the distance from the root to the deepest child.

type BalanceFactorSource#

Constructors

| LeanLeft

Left children is higher.

| LeanNone

Equal heights of children.

| LeanRight

Right children is higher.

diffFactor {A} : AVLTree A -> IntSource#

balanceFactor {A} (t : AVLTree A) : BalanceFactorSource#

𝒪(1). Computes the balance factor, i.e., the height of the right subtree minus the height of the left subtree.

mknode {A} (val : A) (l : AVLTree A) (r : AVLTree A) : AVLTree ASource#

𝒪(1). Helper function for creating a node.

rotateLeft {A} : AVLTree A -> AVLTree ASource#

𝒪(1). Left rotation.

rotateRight {A} : AVLTree A -> AVLTree ASource#

𝒪(1). Right rotation.

balance : {A : Type} -> AVLTree A -> AVLTree ASource#

𝒪(1). Applies local rotations if needed.

lookupWith {A K} {{o : Ord K}} (f : A -> K) (x : K) : AVLTree A -> Maybe ASource#

𝒪(log 𝓃). Lookup a member from the AVLTree using a projection function. Ord A, Ord K and f must be compatible. i.e cmp_k (f a1) (f a2) == cmp_a a1 a2

member? {A} {{Ord A}} (x : A) : AVLTree A -> BoolSource#

𝒪(log 𝓃). Queries whether an element is in an AVLTree.

insertWith {A} {{o : Ord A}} (f : A -> A -> A) (x : A) : AVLTree A -> AVLTree ASource#

𝒪(log 𝓃). Inserts an element into and AVLTree using a function to deduplicate entries. Assumption: Given a1 == a2 then f a1 a2 == a1 == a2 where == comes from Ord a.

insert {A} {{Ord A}} : A -> AVLTree A -> AVLTree ASource#

𝒪(log 𝓃). Inserts an element into and AVLTree.

delete {A} {{o : Ord A}} (x : A) : AVLTree A -> AVLTree ASource#

𝒪(log 𝓃). Removes an element from an AVLTree.

lookupMin {A} : AVLTree A -> Maybe ASource#

𝒪(log 𝓃). Returns the minimum element of the AVLTree.

lookupMax {A} : AVLTree A -> Maybe ASource#

𝒪(log 𝓃). Returns the maximum element of the AVLTree.

deleteMany {A} {{Ord A}} (d : List A) (t : AVLTree A) : AVLTree ASource#

𝒪(𝒹 log 𝓃). Deletes d elements from an AVLTree.

isBalanced {A} : AVLTree A -> BoolSource#

𝒪(𝓃). Checks the AVLTree height invariant. I.e. that every two children do not differ on height by more than 1.

fromList {A} {{Ord A}} (l : List A) : AVLTree ASource#

𝒪(𝓃 log 𝓃). Create an AVLTree from an unsorted List.

size {A} : AVLTree A -> NatSource#

𝒪(𝓃). Returns the number of elements of an AVLTree.

toList {A} : AVLTree A -> List ASource#

𝒪(𝓃). Returns the elements of an AVLTree in ascending order.

prettyDebug {A} {{Show A}} : AVLTree A -> StringSource#

𝒪(𝓃). Formats the tree in a debug friendly format.

toTree {A} : AVLTree A -> Maybe (Tree A)Source#

𝒪(𝓃).

pretty {A} {{Show A}} : AVLTree A -> StringSource#

Returns the textual representation of an AVLTree.

instance eqAVLTreeI {A} {{Eq A}} : Eq (AVLTree A)Source#

instance ordAVLTreeI {A} {{Ord A}} : Ord (AVLTree A)Source#