       return (
         Tree.Node(.B, ll, lx, Tree.Node(.B, .Node(.R, lrl, lrx, lrr), x, r).balL()), false
       )
+    }
+  }
+}
+
+/// :nodoc:
+
+internal enum TreeBalance {
+  case Balanced(blackHeight: Int)
+  case UnBalanced
+}
+
+// MARK: Contains
+
+extension Tree {
+  private func cont(x: Element, _ p: Element) -> Bool {
+    guard case let .Node(_, l, y, r) = self else { return x == p }
+    return x < y ? l.cont(x, p) : r.cont(x, y)
+  }
+  
+  /**
+  Returns `true` iff `self` contains `x`
+  
+  - Complexity: O(*log n*)
+  */
+  
+  public func contains(x: Element) -> Bool {
+    guard case let .Node(_, l, y, r) = self else { return false }
+    return x < y ? l.contains(x) : r.cont(x, y)
+  }
+}
+
+// MARK: Insert
+
+extension Tree {
+  private func ins(x: Element) -> Tree {
+    guard case let .Node(c, l, y, r) = self else { return Tree(x, color: .R) }
+    if x < y { return Tree(y, color: c, left: l.ins(x), right: r).balL() }
+    if y < x { return Tree(y, color: c, left: l, right: r.ins(x)).balR() }
+    return self
+  }
+  
+  /**
+  Inserts `x` into `self`
+  
+  - Complexity: O(*log n*)
+  */
+  
+  public mutating func insert(x: Element) {
+    guard case let .Node(_, l, y, r) = ins(x) else {
+      preconditionFailure("ins should not return an empty tree")
+    }
+    self = .Node(.B, l, y, r)
+  }
+}
+
+// MARK: SequenceType
+
+extension Tree : SequenceType {
+  /**
+  Runs a `TreeGenerator` over the elements of `self`. (The elements are presented in
+  order, from smallest to largest)
+  */
+  
+  public func generate() -> TreeGenerator<Element> {
+    return TreeGenerator(stack: [], curr: self)
+  }
+}
+
+/**
+A `Generator` for a Tree
+*/
+
+public struct TreeGenerator<Element : Comparable> : GeneratorType {
+  private var (stack, curr): ([Tree<Element>], Tree<Element>)
+  /**
+  Advance to the next element and return it, or return `nil` if no next element exists.
+  */
+  public mutating func next() -> Element? {
+    while case let .Node(_, l, x, r) = curr {
+      if case .Empty = l {
+        curr = r
+        return x
+      } else {
+        stack.append(curr)
+        curr = l
+      }
+    }
+    guard case let .Node(_, _, x, r)? = stack.popLast()
+      else { return nil }
+    curr = r
+    return x
+  }
+}
+
+// MARK: Max, min
+
+extension Tree {
+  /**
+  Returns the smallest element in `self` if it's present, or `nil` if `self` is empty
+  
+  - Complexity: O(*log n*)
+  */
+  
+  public func minElement() ->  Element? {
+    switch self {
+    case .Empty: return nil
+    case .Node(_, .Empty, let e, _): return e
+    case .Node(_, let l, _, _): return l.minElement()
+    }
+  }
+  
+  /**
+  Returns the largest element in `self` if it's present, or `nil` if `self` is empty
+  
+  - Complexity: O(*log n*)
+  */
+  
+  public func maxElement() -> Element? {
+    switch self {
+    case .Empty: return nil
+    case .Node(_, _, let e, .Empty) : return e
+    case .Node(_, _, _, let r): return r.maxElement()
     }
   }
   

    }
    return x
  }
  
  /**
  Returns a sequence of the elements of `self` from largest to smallest
  */

    return .Balanced(blackHeight: x)
  }
  
  private func balL() -> Tree {
    switch self {
    case let .Node(.B, .Node(.R, .Node(.R, a, x, b), y, c), z, d):
