Red Black Tree with Pattern Matching Elixir

red_black_tree.ex

defmodule RedBlackTree do
  @type color :: :red | :black
  @type tree :: nil | {color, any, tree, tree}

  @spec insert(tree, any) :: tree
  def insert(nil, value), do: {:black, value, nil, nil}
  def insert(tree, value) do
    {_, new_value, new_left, new_right} = do_insert(tree, value)
    {:black, new_value, new_left, new_right}
  end

  @spec do_insert(tree, any) :: tree
  defp do_insert(nil, value), do: {:red, value, nil, nil}
  defp do_insert({node_color, node_value, left, right}, value) do
    cond do
      value < node_value ->
        balance(node_color, node_value, do_insert(left, value), right)
      value > node_value ->
        balance(node_color, node_value, left, do_insert(right, value))
      true ->
        {node_color, node_value, left, right}
    end
  end

  @spec balance(color, any, tree, tree) :: tree
  defp balance(:black, z, {:red, y, {:red, x, a, b}, c}, d) do
    {:red, y, {:black, x, a, b}, {:black, z, c, d}}
  end
  defp balance(:black, z, {:red, x, a, {:red, y, b, c}}, d) do
    {:red, y, {:black, x, a, b}, {:black, z, c, d}}
  end
  defp balance(:black, x, a, {:red, z, {:red, y, b, c}, d}) do
    {:red, y, {:black, x, a, b}, {:black, z, c, d}}
  end
  defp balance(:black, x, a, {:red, y, b, {:red, z, c, d}}) do
    {:red, y, {:black, x, a, b}, {:black, z, c, d}}
  end
  defp balance(color, value, left, right), do: {color, value, left, right}

  @spec delete(tree, any) :: tree
  def delete(nil, _), do: nil
  def delete(tree, value) do
    {_, new_value, new_left, new_right} = do_delete(tree, value)
    {:black, new_value, new_left, new_right}
  end

  @spec do_delete(tree, any) :: tree
  defp do_delete({:black, value, nil, nil}, value), do: {:black, :leaf, nil, nil}
  defp do_delete({color, node_value, left, right}, value) do
    cond do
      value < node_value ->
        handle_delete_left(color, node_value, do_delete(left, value), right)
      value > node_value ->
        handle_delete_right(color, node_value, left, do_delete(right, value))
      true ->
        if right == nil do
          {color, node_value, left, nil}
        else
          {successor, new_right} = delete_min(right)
          balance(color, successor, left, new_right)
        end
    end
  end

  defp handle_delete_left(:black, value, {:black, :leaf, nil, nil}, right) do
    balance(:black, value, {:red, :leaf, nil, nil}, right)
  end
  defp handle_delete_left(color, value, left, right) do
    balance(color, value, left, right)
  end

  defp handle_delete_right(:black, value, left, {:black, :leaf, nil, nil}) do
    balance(:black, value, left, {:red, :leaf, nil, nil})
  end
  defp handle_delete_right(color, value, left, right) do
    balance(color, value, left, right)
  end

  defp delete_min({:black, value, nil, _right}) do
    {value, {:red, :leaf, nil, nil}}
  end
  defp delete_min({:black, value, {:red, left_value, nil, nil}, nil}) do
    {value, {:black, left_value, nil, nil}}
  end
  defp delete_min({color, value, left, right}) do
    {min_value, new_left} = delete_min(left)
    {min_value, balance(color, value, new_left, right)}
  end

  @spec search(tree, any) :: boolean
  def search(nil, _), do: false
  def search({_, value, left, right}, search_value) do
    cond do
      search_value < value -> search(left, search_value)
      search_value > value -> search(right, search_value)
      true -> true
    end
  end

  @spec to_list(tree) :: list
  def to_list(tree), do: do_to_list(tree, [])

  @spec do_to_list(tree, list) :: list
  defp do_to_list(nil, acc), do: acc
  defp do_to_list({_, value, left, right}, acc) do
    do_to_list(left, [value | do_to_list(right, acc)])
  end
end