Last active
March 7, 2019 16:29
-
-
Save leighhalliday/2f0db4ce44ba7693744d to your computer and use it in GitHub Desktop.
Playing with Binary Trees in Elixir
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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) |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# 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