Skip to content

Instantly share code, notes, and snippets.

@leighhalliday
Last active March 7, 2019 16:29
Show Gist options
  • Save leighhalliday/2f0db4ce44ba7693744d to your computer and use it in GitHub Desktop.
Save leighhalliday/2f0db4ce44ba7693744d to your computer and use it in GitHub Desktop.
Playing with Binary Trees in Elixir
defmodule MyList do
# Takes 2 lists like [1,2] and [3,4]
# and produces a single list like [1,3,2,4]
def zip_merge([heada | taila], [headb | tailb]) do
[heada] ++ [headb] ++ zip_merge(taila, tailb)
end
def zip_merge([heada | taila], []) do
[heada] ++ zip_merge(taila, [])
end
def zip_merge([], [headb | tailb]) do
[headb] ++ zip_merge([], tailb)
end
def zip_merge([], []) do
[]
end
end
defmodule BinTree do
def create(new_value) do
%{value: new_value, left: nil, right: nil}
end
def add_node(nil, new_value) do
create(new_value)
end
def add_node(%{value: value, left: left, right: right}, new_value) do
if new_value < value do
%{value: value, left: add_node(left, new_value), right: right}
else
%{value: value, left: left, right: add_node(right, new_value)}
end
end
def count(nil) do
0
end
def count(%{left: left, right: right}) do
1 + count(left) + count(right)
end
def reduce(nil, _f, acc) do
acc
end
def reduce(%{value: value, left: left, right: right}, f, acc) do
acc = reduce(left, f, f.(value, acc))
reduce(right, f, acc)
end
def exists?(nil, _sval) do
false
end
def exists?(%{value: value, left: left, right: right}, sval) do
cond do
sval == value -> true
sval < value -> exists?(left, sval)
sval > value -> exists?(right, sval)
end
end
def to_list(t) do
reduce(t, (fn (v, acc) -> [v | acc] end), [])
end
def balance(t) do
to_balance_list(t) |> Enum.reduce(nil, (fn (x, acc) ->
add_node acc, x
end))
end
# [1,2,3,4] becomes [3,2,4,1]
# this new list can then create a new
# binary tree which is balanced
defp to_balance_list(t) do
l = Enum.sort(to_list(t))
count = Enum.count(l)
half = round(Float.ceil(count / 2))
la = Enum.reverse(Enum.slice(l, 0, half))
lb = Enum.slice(l, half, count - 1)
MyList.zip_merge(lb, la)
end
end
t = Enum.reduce(1..10, nil, (fn (x, acc) ->
BinTree.add_node acc, x
end))
IO.inspect t
IO.inspect BinTree.count(t)
IO.inspect BinTree.reduce(t, (fn (v, acc) -> v + acc end), 0)
IO.inspect BinTree.exists?(t, 15)
IO.inspect BinTree.exists?(t, 5)
IO.inspect BinTree.balance(t)
# Initial tree inspect
%{left: nil,
right: %{left: nil,
right: %{left: nil,
right: %{left: nil,
right: %{left: nil,
right: %{left: nil,
right: %{left: nil,
right: %{left: nil,
right: %{left: nil, right: %{left: nil, right: nil, value: 10},
value: 9}, value: 8}, value: 7}, value: 6}, value: 5},
value: 4}, value: 3}, value: 2}, value: 1}
# Count
10
# Reduce (performing sum)
55
# Exists 15?
false
# Exists 5?
true
# Tree inspection after balance
%{left: %{left: %{left: %{left: %{left: %{left: nil, right: nil, value: 1},
right: nil, value: 2}, right: nil, value: 3}, right: nil, value: 4},
right: nil, value: 5},
right: %{left: nil,
right: %{left: nil,
right: %{left: nil, right: %{left: nil, right: nil, value: 10}, value: 9},
value: 8}, value: 7}, value: 6}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment