gleamy/red_black_tree_set

This module provides an implementation of a red-black tree set, a self-balancing binary search tree data structure that maintains a balanced shape which ensures tree operations stay efficient. This is an ordered set implementation, meaning the tree will contains values that are unique and ordered according to the comparison function.

Types

Set

opaque </>

pub opaque type Set(a)

Functions

clear

</>

pub fn clear(tree: Set(a)) -> Set(a)

Removes all elements from the set, resulting in an empty set. Time complexity: O(1)

delete

</>

pub fn delete(tree: Set(a), key: a) -> Set(a)

Removes an element from the set, if it exists. Time complexity: O(log n)

find

</>

pub fn find(tree: Set(a), key: a) -> Result(a, Nil)

Searches for an element in the set and returns it if found. Time complexity: O(log n)

fold

</>

pub fn fold(tree: Set(a), acc: b, fun: fn(b, a) -> b) -> b

Applies a function to every element in the set, accumulating the results with the provided initial accumulator value. Time complexity: O(n)

foldr

</>

pub fn foldr(tree: Set(a), acc: b, fun: fn(b, a) -> b) -> b

Applies a function to every element in set, accumulating the results with the provided initial accumulator value, but in reverse order. Time complexity: O(n)

insert

</>

pub fn insert(tree: Set(a), key: a) -> Set(a)

Inserts a new element into the set, preserving the set property (no duplicates). Time complexity: O(log n)

new

</>

pub fn new(compare: fn(a, a) -> Order) -> Set(a)

Creates a new empty set with the provided comparison function.