44 lines
1.8 KiB
Plaintext
44 lines
1.8 KiB
Plaintext
defmodule RBtree do
|
|
def find(nil, _), do: :not_found
|
|
def find({ key, value, _, _, _ }, key), do: { :found, { key, value } }
|
|
def find({ key1, _, _, left, _ }, key) when key < key1, do: find(left, key)
|
|
def find({ key1, _, _, _, right }, key) when key > key1, do: find(right, key)
|
|
|
|
def new(key, value), do: ins(nil, key, value) |> make_black
|
|
|
|
def insert(tree, key, value), do: ins(tree, key, value) |> make_black
|
|
|
|
defp ins(nil, key, value),
|
|
do: { key, value, :r, nil, nil }
|
|
defp ins({ key, _, color, left, right }, key, value),
|
|
do: { key, value, color, left, right }
|
|
defp ins({ ky, vy, cy, ly, ry }, key, value) when key < ky,
|
|
do: balance({ ky, vy, cy, ins(ly, key, value), ry })
|
|
defp ins({ ky, vy, cy, ly, ry }, key, value) when key > ky,
|
|
do: balance({ ky, vy, cy, ly, ins(ry, key, value) })
|
|
|
|
defp make_black({ key, value, _, left, right }),
|
|
do: { key, value, :b, left, right }
|
|
|
|
defp balance({ kx, vx, :b, lx, { ky, vy, :r, ly, { kz, vz, :r, lz, rz } } }),
|
|
do: { ky, vy, :r, { kx, vx, :b, lx, ly }, { kz, vz, :b, lz, rz } }
|
|
defp balance({ kx, vx, :b, lx, { ky, vy, :r, { kz, vz, :r, lz, rz }, ry } }),
|
|
do: { kz, vz, :r, { kx, vx, :b, lx, lz }, { ky, vy, :b, rz, ry } }
|
|
defp balance({ kx, vx, :b, { ky, vy, :r, { kz, vz, :r, lz, rz }, ry }, rx }),
|
|
do: { ky, vy, :r, { kz, vz, :b, lz, rz }, { kx, vx, :b, ry, rx } }
|
|
defp balance({ kx, vx, :b, { ky, vy, :r, ly, { kz, vz, :r, lz, rz } }, rx }),
|
|
do: { kz, vz, :r, { ky, vy, :b, ly, lz }, { kx, vx, :b, rz, rx } }
|
|
defp balance(t),
|
|
do: t
|
|
end
|
|
|
|
RBtree.new(0,3) |> IO.inspect
|
|
|> RBtree.insert(1,5) |> IO.inspect
|
|
|> RBtree.insert(2,-1) |> IO.inspect
|
|
|> RBtree.insert(3,7) |> IO.inspect
|
|
|> RBtree.insert(4,-3) |> IO.inspect
|
|
|> RBtree.insert(5,0) |> IO.inspect
|
|
|> RBtree.insert(6,-1) |> IO.inspect
|
|
|> RBtree.insert(7,0) |> IO.inspect
|
|
|> RBtree.find(4) |> IO.inspect
|