insert :: (Ord a) => a -> RedBlackTree a -> RedBlackTree a
insert x tree = fromZipper $ insert' x (tree, [])
  where insert' :: (Ord a) => a -> RedBlackZipper a -> RedBlackZipper a
        insert' x (Empty, []) = (singleton x, [])
        insert' x (Empty, path) = balance (Node x Red Empty Empty, path)
        insert' x (n@(Node v c l r), path)
          | x < v  = insert' x (l, (Path L v c r):path)
          | x == v = (n, path)
          | x > v  = insert' x (r, (Path R v c l):path)

-- balance a tree using algorithm adapted from:
-- http://en.wikipedia.org/wiki/Red_black_tree
insert :: (Ord a) => a -> RedBlackTree a -> RedBlackTree a
insert x tree = fromZipper $ insert' x (tree, [])
  where insert' :: (Ord a) => a -> RedBlackZipper a -> RedBlackZipper a
        insert' x (Empty, []) = (singleton x, [])
        insert' x (Empty, path) = balance (Node x Red Empty Empty, path)
        insert' x (n@(Node v c l r), path)
          | x < v  = insert' x (l, (Path L v c r):path)
          | x == v = (n, path)
          | x > v  = insert' x (r, (Path R v c l):path)

-- balance a tree using algorithm adapted from:
-- http://en.wikipedia.org/wiki/Red_black_tree
insert x tree = fromZipper $ insert' x (tree, [])
  where insert' :: (Ord a) => a -> RedBlackZipper a -> RedBlackZipper a
        insert' x (Empty, []) = (singleton x, [])
        insert' x (Empty, path) = balance (Node x Red Empty Empty, path)
        insert' x (n@(Node v c l r), path)
          | x < v  = insert' x (l, (Path L v c r):path)
          | x == v = (n, path)
          | x > v  = insert' x (r, (Path R v c l):path)

-- balance a tree using algorithm adapted from:
-- http://en.wikipedia.org/wiki/Red_black_tree