Create a gist now

Instantly share code, notes, and snippets.

@zwilias /Balance.elm
Last active Mar 21, 2017

What would you like to do?
type Dict k v
= Empty
| Node Int k v (Dict k v) (Dict k v)
balance : Dict k v -> Dict k v
balance dict =
case dict of
Empty ->
dict
Node _ key value left right ->
if heightDiff dict == -2 && heightDiff left == 1 then
-- left leaning tree with right-leaning left subtree. Rotate left, then right.
build key value (rotateLeft left) right |> rotateRight
else if heightDiff dict < -1 then
-- left leaning tree, generally. Rotate right.
rotateRight dict
else if heightDiff dict == 2 && heightDiff right == -1 then
-- right leaning tree with left-leaning right subtree. Rotate right, then left.
build key value left (rotateRight right) |> rotateLeft
else if heightDiff dict > 1 then
-- right leaning tree, generally. Rotate left.
rotateLeft dict
else
-- diff is -1, 0, or 1. Already balanced, no operation required.
dict
-- Type signatures of functions used
-- Build a tree-node, by first calculating the correct height and calling the constructor
build : k -> v -> Dict k v -> Dict k v -> Dict k v
build key value left right = ...
-- Rotate a tree to the left
rotateLeft : Dict k v -> Dict k v
-- Rotate a tree to the right
rotateRight : Dict k v -> Dict k v
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment