gleamy/red_black_tree_map
This module provides an implementation of a red-black tree map, a self-balancing binary search tree data structure that maintains a balanced shape which ensures tree operations stay efficient. It associates keys with values, where each key is unique and ordered according to the comparison function.
Types
Functions
pub fn clear(tree: Map(a, b)) -> Map(a, b)Removes all elements from the map, resulting in an empty map. Time complexity: O(1)
pub fn delete(tree: Map(a, b), key: a) -> Map(a, b)Removes a key-value pair from the map, if the key exists. Time complexity: O(log n)
pub fn find(tree: Map(a, b), key: a) -> Result(b, Nil)Searches for a key in the map and returns the associated value if found. Time complexity: O(log n)
pub fn fold(tree: Map(a, b), acc: c, fun: fn(c, a, b) -> c) -> cApplies a function to every key-value pair in the map, accumulating the results with the provided initial accumulator value. Time complexity: O(n)
pub fn foldr(tree: Map(a, b), acc: c, fun: fn(c, a, b) -> c) -> cApplies a function to every key-value pair in the map, accumulating the results with the provided initial accumulator value, but in reverse order. Time complexity: O(n)
pub fn insert(tree: Map(a, b), key: a, value: b) -> Map(a, b)Inserts a new key-value pair into the map. If the key already exists, its associated value is updated with the new value. Time complexity: O(log n)
pub fn larger(tree: Map(a, b), key: a) -> Result(#(a, b), Nil)Find the smallest key that is larger than the given key. Time complexity: O(log n)
pub fn new(compare: fn(a, a) -> Order) -> Map(a, b)Creates a new empty map with the provided comparison function for keys.