# AVLTree v1.0.0 AVLTree

Pure Elixir AVL tree implementation.

This data structure is very similar to `MapSet`, but unlike the latter, elements in the `AVLTree` are always sorted in ascending or descending order.

To sort items, `AVLTree` uses a comparison function that looks like:

`less(a, b) :: boolean`

This function returns `true` if element `a` must be placed strictly before element `b`, otherwise it returns false.

`AVLTree` can store duplicate elements. It is important to understand that duplicate elements are not necessarily the same.

Values `a` and `b` are considered equal if they satisfy the following condition:

`less(a, b) == false and less(b, a) == false`, where `less(x, y)` is comparison function

For example, if the comparison function is `fn {a, _}, {b, _} -> a < b end`, then the elements `{1, 10}` and `{1, 20}` are considered equal, although actually they aren't.

By default, comparison function is `Kernel.</2`.

## Basic Usage

By default, inserted elements are sorted in ascending order:

``````iex> tree = AVLTree.new()
#AVLTree<[]>
iex> tree = AVLTree.put(tree, 5)
iex> tree = AVLTree.put(tree, 2)
iex> tree = [1, 3, 6, 4] |> Enum.into(tree)
iex> tree
#AVLTree<[1, 2, 3, 4, 5, 6]>``````

You can specify ordering when creating a tree:

``````iex> tree1 = AVLTree.new(:asc)
iex> tree2 = AVLTree.new(:desc)
iex> [4, 2, 1, 3] |> Enum.into(tree1)
#AVLTree<[1, 2, 3, 4]>
iex> [4, 2, 1, 3] |> Enum.into(tree2)
#AVLTree<[4, 3, 2, 1]>``````

Also you can use a custom comparison function.

Example of a tree with tuples as elements, ordered by the first field

``````iex> tree = AVLTree.new(fn {a, _}, {b, _} -> a < b end)
iex> [{2, "A"}, {3, "B"}, {1, "C"}] |> Enum.into(tree)
#AVLTree<[{1, "C"}, {2, "A"}, {3, "B"}]>``````

Checks if the tree contains a value

``````iex> tree = [5, 2, 1, 3] |> Enum.into(AVLTree.new())
iex> AVLTree.member?(tree, 2)
true``````

`AVLTree` fully supports `Enumerable` protocol

``````iex> tree = [4, 2, 1, 3] |> Enum.into(AVLTree.new())
iex> Enum.to_list(tree)
[1, 2, 3, 4]
iex> Enum.sum(tree)
10``````

## Sorted list of dates

Let's create an ascending list of `DateTime` values.

``````iex> tree = AVLTree.new(fn a, b -> DateTime.compare(a, b) == :lt end)
iex> [
...>   ~U[2020-02-03 01:01:01Z],
...>   ~U[2020-01-01 01:01:01Z],
...>   ~U[2019-10-10 02:11:01Z],
...>   ~U[2020-01-01 01:01:02Z]
...> ] |> Enum.into(tree)
#AVLTree<[~U[2019-10-10 02:11:01Z], ~U[2020-01-01 01:01:01Z], ~U[2020-01-01 01:01:02Z], ~U[2020-02-03 01:01:01Z]]>``````

## AVLTree as a map.

If you use a key-value pairs as elements, `AVLTree` can work as a map:

Create a tree

``tree = AVLTree.new(fn {a, _}, {b, _} -> a < b end)``

Insert key-value pairs:

``````tree =
tree
|> AVLTree.put({:a, "first value"})
|> AVLTree.put({:c, "third value"})
|> AVLTree.put({:b, "second value"})``````

or

``````    tree =
[a: "first value", c: "third value", b: "second value"]
|> Enum.into(tree)``````

Retrieve element by key. We can use anything as a value since comparison function cares only about keys.

``AVLTree.get(tree, {:b, nil}) # {:b, "second value"}``

Delete element:

``AVLTree.delete(tree, {:b, nil}) # #AVLTree<[a: "first value", c: "third value"]>``

Benefits? Elements are always ordered by keys. Custom comparison function.

## Performance

All inserts, removes and searches in general has complexity of `Ο(lg(n))`.

This implementation is about 4-5 times slower than `MapSet`.

To run benchmark use:

``mix run bench/run.exs``

# Link to this section Summary

## Functions

Deletes an element equal to the given `value`.

Deletes an element equal to the given `value`.

Deletes an element equal to the given `value`.

Retrieves an element equal to `value`.

Retrieves the first value in the tree.

Retrieves the last value in the tree.

Retrieves an element equal to `value`.

Retrieves an element equal to `value`.

Returns height of the tree.

Checks if the tree contains an element equal to `value`.

Creates a new tree with default ascending order.

Creates a new tree with the given `ordering` or comparison function.

Puts the given `value` in the tree.

Puts the given `value` in the tree.

Puts the given `value` in the tree.

Returns the number of elements in the tree

Displays the tree in human readable form.

# less()

## Specs

`less() :: (value(), value() -> boolean())`

(opaque)

`t()`

# value()

## Specs

`value() :: term()`

# delete(avl_tree, value)

## Specs

`delete(t(), value()) :: t()`

Deletes an element equal to the given `value`.

If the tree contains more than one element equal to `value`, deletes one of them. It is undefined which one.

If no element is found, returns the tree unchanged.

``````iex> tree = [3, 2, 1, 4] |> Enum.into(AVLTree.new())
#AVLTree<[1, 2, 3, 4]>
iex> AVLTree.delete(tree, 3)
#AVLTree<[1, 2, 4]>
iex> AVLTree.delete(tree, 5)
#AVLTree<[1, 2, 3, 4]>``````

# delete_lower(avl_tree, value)

## Specs

`delete_lower(t(), value()) :: {:ok, t()} | :error`

Deletes an element equal to the given `value`.

If the tree contains more than one element equal to `value`, deletes the first of them.

If no element is found, returns the tree unchanged.

``````iex> tree = [b: 21, a: 1, b: 22, c: 3, b: 23] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 1, b: 21, b: 22, b: 23, c: 3]>
iex> AVLTree.delete_lower(tree, {:b, nil})
#AVLTree<[a: 1, b: 22, b: 23, c: 3]>``````

# delete_upper(avl_tree, value)

## Specs

`delete_upper(t(), value()) :: {:ok, t()} | :error`

Deletes an element equal to the given `value`.

If the tree contains more than one element equal to `value`, deletes the last of them.

If no element is found, returns the tree unchanged.

``````iex> tree = [b: 21, a: 1, b: 22, c: 3, b: 23] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 1, b: 21, b: 22, b: 23, c: 3]>
iex> AVLTree.delete_upper(tree, {:b, nil})
#AVLTree<[a: 1, b: 21, b: 22, c: 3]>``````

# get(avl_tree, value, default \\ nil)

## Specs

`get(t(), value(), term()) :: value() | term()`

Retrieves an element equal to `value`.

If the tree contains more than one element equal to `value`, retrieves one of them. It is undefined which one.

Returns `defailt` if nothing is found.

``````iex> tree = AVLTree.new(fn {a, _}, {b, _} -> a < b end)
#AVLTree<[]>
iex> tree = [a: "A", c: "C", d: "D", b: "B"] |> Enum.into(tree)
#AVLTree<[a: "A", b: "B", c: "C", d: "D"]>
iex> AVLTree.get(tree, {:c, nil}, :error)
{:c, "C"}
iex> AVLTree.get(tree, {:e, nil}, :error)
:error``````

# get_first(avl_tree, default \\ nil)

## Specs

`get_first(t(), term()) :: value() | term()`

Retrieves the first value in the tree.

Returns `default` if the tree is empty.

``````iex> tree = [3, 2, 4, 6] |> Enum.into(AVLTree.new())
#AVLTree<[2, 3, 4, 6]>
iex> AVLTree.get_first(tree)
2``````

# get_last(avl_tree, default \\ nil)

## Specs

`get_last(t(), term()) :: value() | term()`

Retrieves the last value in the tree.

Returns `default` if the tree is empty.

``````iex> tree = [3, 2, 4, 6] |> Enum.into(AVLTree.new())
#AVLTree<[2, 3, 4, 6]>
iex> AVLTree.get_last(tree)
6``````

# get_lower(avl_tree, value, default \\ nil)

## Specs

`get_lower(t(), value(), term()) :: value() | term()`

Retrieves an element equal to `value`.

If the tree contains more than one element equal to `value`, retrieves the first of them

Returns `default` if nothing is found.

``````iex> tree = [b: 21, a: 1, b: 22, c: 3, b: 23] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 1, b: 21, b: 22, b: 23, c: 3]>
iex> AVLTree.get_lower(tree, {:b, nil})
{:b, 21}``````

# get_upper(avl_tree, value, default \\ nil)

## Specs

`get_upper(t(), value(), term()) :: value() | term()`

Retrieves an element equal to `value`.

If the tree contains more than one element equal to `value`, retrieves the last of them

Returns `default` if nothing is found.

``````iex> tree = [b: 21, a: 1, b: 22, c: 3, b: 23] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 1, b: 21, b: 22, b: 23, c: 3]>
iex> AVLTree.get_upper(tree, {:b, nil})
{:b, 23}``````

# height(avl_tree)

## Specs

`height(t()) :: integer()`

Returns height of the tree.

``````iex> tree = [5, 9, 3, 8, 1, 6, 7] |> Enum.into(AVLTree.new())
#AVLTree<[1, 3, 5, 6, 7, 8, 9]>
iex> AVLTree.height(tree)
4``````

# member?(avl_tree, value)

## Specs

`member?(t(), term()) :: boolean()`

Checks if the tree contains an element equal to `value`.

``````iex> tree = [3, 2, 4, 6] |> Enum.into(AVLTree.new())
#AVLTree<[2, 3, 4, 6]>
iex> AVLTree.member?(tree, 4)
true
iex> AVLTree.member?(tree, 1)
false``````

# new()

## Specs

`new() :: t()`

Creates a new tree with default ascending order.

``````iex> [3, 1, 4, 2] |> Enum.into(AVLTree.new())
#AVLTree<[1, 2, 3, 4]>``````

# new(ordering)

## Specs

`new(:asc | :desc | less()) :: t()`

Creates a new tree with the given `ordering` or comparison function.

``````iex> [3, 1, 4, 2] |> Enum.into(AVLTree.new(:asc))
#AVLTree<[1, 2, 3, 4]>
iex> [3, 1, 4, 2] |> Enum.into(AVLTree.new(:desc))
#AVLTree<[4, 3, 2, 1]>
iex> [3, 1, 4, 2] |> Enum.into(AVLTree.new(fn a, b -> a > b end))
#AVLTree<[4, 3, 2, 1]>``````

# put(avl_tree, value)

## Specs

`put(t(), value()) :: t()`

Puts the given `value` in the tree.

If the tree already contains elements equal to `value`, replaces one of them. It is undefined which one.

``````iex> tree = [b: 2, a: 1, c: 3] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 1, b: 2, c: 3]>
iex> AVLTree.put(tree, {:d, 4})
#AVLTree<[a: 1, b: 2, c: 3, d: 4]>
iex> AVLTree.put(tree, {:a, 11})
#AVLTree<[a: 11, b: 2, c: 3]>``````

# put_lower(avl_tree, value)

## Specs

`put_lower(t(), value()) :: t()`

Puts the given `value` in the tree.

If the tree already contains elements equal to `value`, inserts `value` before them.

``````iex> tree = [b: 21, a: 11, d: 41, c: 31] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 11, b: 21, c: 31, d: 41]>
iex> tree = AVLTree.put_lower(tree, {:a, 12})
#AVLTree<[a: 12, a: 11, b: 21, c: 31, d: 41]>
iex> tree = AVLTree.put_lower(tree, {:b, 22})
#AVLTree<[a: 12, a: 11, b: 22, b: 21, c: 31, d: 41]>
iex> AVLTree.put_lower(tree, {:d, 42})
#AVLTree<[a: 12, a: 11, b: 22, b: 21, c: 31, d: 42, d: 41]>``````

# put_upper(avl_tree, value)

## Specs

`put_upper(t(), value()) :: t()`

Puts the given `value` in the tree.

If the tree already contains elements equal to `value`, inserts `value` after them.

``````iex> tree = [b: 21, a: 11, d: 41, c: 31] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end))
#AVLTree<[a: 11, b: 21, c: 31, d: 41]>
iex> tree = AVLTree.put_upper(tree, {:a, 12})
#AVLTree<[a: 11, a: 12, b: 21, c: 31, d: 41]>
iex> tree = AVLTree.put_upper(tree, {:b, 22})
#AVLTree<[a: 11, a: 12, b: 21, b: 22, c: 31, d: 41]>
iex> AVLTree.put_upper(tree, {:d, 42})
#AVLTree<[a: 11, a: 12, b: 21, b: 22, c: 31, d: 41, d: 42]>``````
``````iex> [a: 11, c: 31, a: 12, b: 21, a: 13] |> Enum.into(AVLTree.new(fn {a, _}, {b, _} -> a < b end)) |> Enum.to_list()
[a: 11, a: 12, a: 13, b: 21, c: 31]``````

# size(avl_tree)

## Specs

`size(t()) :: integer()`

Returns the number of elements in the tree

``````iex> tree = [5, 9, 3, 8, 1, 6, 7] |> Enum.into(AVLTree.new())
#AVLTree<[1, 3, 5, 6, 7, 8, 9]>
iex> AVLTree.size(tree)
7``````

# view(avl_tree)

## Specs

`view(t()) :: String.t()`

Displays the tree in human readable form.

``````iex> tree = 1..10 |> Enum.into(AVLTree.new())
#AVLTree<[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]>
iex> IO.puts AVLTree.view(tree)``````
``````   4
┌─┴───┐
2     8
┌┴┐  ┌─┴─┐
1 3  6   9
┌┴┐ ┌┴─┐
5 7   10``````