red_black_tree alternatives and similar packages
Based on the "Algorithms and Data structures" category.
Alternatively, view red_black_tree alternatives based on common mentions on social networks and blogs.
-
matrex
A blazing fast matrix library for Elixir/Erlang with C implementation using CBLAS. -
simple_bayes
A Naive Bayes machine learning implementation in Elixir. -
exconstructor
An Elixir library for generating struct constructors that handle external data with ease. -
erlang-algorithms
Implementations of popular data structures and algorithms -
aja
Extension of the Elixir standard library focused on data stuctures, data manipulation and performance -
remodel
:necktie: An Elixir presenter package used to transform map structures. "ActiveModel::Serializer for Elixir" -
MapDiff
Calculates the difference between two (nested) maps, and returns a map representing the patch of changes. -
parallel_stream
A parallelized stream implementation for Elixir -
merkle_tree
:evergreen_tree: Merkle Tree implementation in pure Elixir -
bloomex
:hibiscus: A pure Elixir implementation of Scalable Bloom Filters -
sfmt
sfmt-erlang: SIMD-oriented Fast Mersenne Twister (SFMT) for Erlang -
graphmath
An Elixir library for performing 2D and 3D mathematics. -
DeepMerge
Deep (recursive) merge for maps, keywords and others in Elixir -
the_fuzz
String metrics and phonetic algorithms for Elixir (e.g. Dice/Sorensen, Hamming, Jaccard, Jaro, Jaro-Winkler, Levenshtein, Metaphone, N-Gram, NYSIIS, Overlap, Ratcliff/Obershelp, Refined NYSIIS, Refined Soundex, Soundex, Weighted Levenshtein) -
exmatrix
Elixir library implementing a parallel matrix multiplication algorithm and other utilities for working with matrices. Used for benchmarking computationally intensive concurrent code. -
ecto_materialized_path
Tree structure & hierarchy for ecto models -
dataframe
Package providing functionality similar to Python's Pandas or R's data.frame() -
parex
An elixir module for parallel execution of functions/processes -
Conrex
An Elixir implementation of the CONREC algorithm for topographic or isochrone maps. -
murmur
:speech_balloon: An implementation of the non-cryptographic hash Murmur3 -
bitmap
Bitmap implementation in Elixir using binaries and integers. Fast space efficient data structure for lookups -
Closure Table
Closure Table for Elixir - a simple solution for storing and manipulating complex hierarchies. -
combination
A simple combinatorics library providing combination and permutation.
InfluxDB - Power Real-Time Data Analytics at Scale
* Code Quality Rankings and insights are calculated and provided by Lumnify.
They vary from L1 to L5 with "L5" being the highest.
Do you think we are missing an alternative of red_black_tree or a related project?
README
RedBlackTree
Red-black tree implementation for Elixir.
Install
Add the following to your mix.exs deps:
{:red_black_tree, "~> 1.0"}
About
Provides an ordered key-value store with O(log(N))
lookup, insert, and delete
performance and O(1)
size performance.
Implements the Dict behavior, Enumerable protocol, and the Collectable protocol.
Comparison
By default, keys are compared using strict equality (see note below), allowing for polymorphic keys in the same tree:
RedBlackTree.new()
|> RedBlackTree.insert(:a, 1)
|> RedBlackTree.insert({:compound, :key}, 2)
A custom comparator may be provided at initialization via the :comparator
option.
For example, let's say we want to store maps containing order information,
sorted by the revenue generated and unique by id. We'll use the
RedBlackTree.compare_terms
function for comparisions since it takes care of
weird cases (see note below.)
order_revenue = RedBlackTree.new([], comparator: fn (value1, value2) ->
# If the ids are the same, they are the same
if value1.id === value2.id do
0
else
case RedBlackTree.compare_terms(value1.revenue, value2.revenue) do
# If the revenues are the same but the ids are different, fall back to id comparison for ordering
0 -> RedBlackTree.compare_terms(value1.id, value2.id)
# otherwise return the comparison
revenue_comparison -> revenue_comparison
end
end
end)
updated_tree = order_revenue
|> RedBlackTree.insert(%{id: 3, revenue: 40}, 40)
|> RedBlackTree.insert(%{id: 50, revenue: 10}, 10)
|> RedBlackTree.insert(%{id: 1, revenue: 50}, 50)
|> RedBlackTree.insert(%{id: 2, revenue: 40}, 40)
# => #RedBlackTree<[{%{id: 50, revenue: 10}, 10}, {%{id: 2, revenue: 40}, 40},
{%{id: 3, revenue: 40}, 40}, {%{id: 1, revenue: 50}, 50}]>
# Notice how changing the revenue of order 2 bumps it all the way to the end,
# since its revenue now equals order 1 but it loses the tie-breaker
RedBlackTree.insert(updated_tree, %{id: 2, revenue: 50}, 50)
# #RedBlackTree<[{%{id: 50, revenue: 10}, 10}, {%{id: 2, revenue: 40}, 40},
{%{id: 3, revenue: 40}, 40}, {%{id: 1, revenue: 50}, 50},
{%{id: 2, revenue: 50}, 50}]>
Note
Due to the way Erlang, and therefore Elixir, implement comparisons for floats
and integers, it is possible for a two keys to be equal (key == other_key
)
but not strictly equal (key !== other_key
).
To guarantee consistent ordering, the default :comparator
function must
fallback to hashing keys that exhibit this property on comparison. In these rare
cases, there will be a small performance penalty.
Example:
tree = RedBlackTree.new([1 => :bubbles])
# Hashing necessary since 1 != 1.0 and 1 == 1.0
updated = RedBlackTree.insert(tree, 1.0, :walrus)
# No hashing necessary, no performance impact
RedBlackTree.insert(updated, 0.5, :frank)
|> RedBlackTree.insert(1.5, :suzie)