Balance.elm

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