Red-black tree implementation for Elixir.
Add the following to your mix.exs deps:
{:red_black_tree, "~> 1.0"}
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.
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)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent