Restore old RedBlack class to maintain backwards compatibility.

The class is marked as deprecated and no longer used by the TreeMap/TreeSet
implementation but is restored in case it was used by anyone else (since
it was not marked as private to the Scala collection library).

Renamed RedBlack.{Tree,RedTree,BlackTree} to Node, RedNode, and BlackNode
to work around name clash with RedBlack class.

4 files changed, 452 insertions, 171 deletions

diff --git a/src/library/scala/collection/immutable/RedBlack.scala b/src/library/scala/collection/immutable/RedBlack.scala
index 30d3ff37a3..37ff7a7f54 100644
--- a/src/library/scala/collection/immutable/RedBlack.scala
+++ b/src/library/scala/collection/immutable/RedBlack.scala
@@ -26,167 +26,167 @@ import annotation.meta.getter
 private[immutable]
 object RedBlack {
 
-  private def blacken[A, B](t: Tree[A, B]): Tree[A, B] = if (t eq null) null else t.black
+  def isBlack(tree: Node[_, _]) = (tree eq null) || isBlackNode(tree)
+  def isRedNode(tree: Node[_, _]) = tree.isInstanceOf[RedNode[_, _]]
+  def isBlackNode(tree: Node[_, _]) = tree.isInstanceOf[BlackNode[_, _]]
 
-  private def mkTree[A, B](isBlack: Boolean, k: A, v: B, l: Tree[A, B], r: Tree[A, B]) =
-    if (isBlack) BlackTree(k, v, l, r) else RedTree(k, v, l, r)
-
-  def isBlack(tree: Tree[_, _]) = (tree eq null) || isBlackTree(tree)
-  def isRedTree(tree: Tree[_, _]) = tree.isInstanceOf[RedTree[_, _]]
-  def isBlackTree(tree: Tree[_, _]) = tree.isInstanceOf[BlackTree[_, _]]
+  def isEmpty(tree: Node[_, _]): Boolean = tree eq null
 
-  def isEmpty(tree: Tree[_, _]): Boolean = tree eq null
-
-  def contains[A](tree: Tree[A, _], x: A)(implicit ordering: Ordering[A]): Boolean = lookup(tree, x) ne null
-  def get[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Option[B] = lookup(tree, x) match {
+  def contains[A](tree: Node[A, _], x: A)(implicit ordering: Ordering[A]): Boolean = lookup(tree, x) ne null
+  def get[A, B](tree: Node[A, B], x: A)(implicit ordering: Ordering[A]): Option[B] = lookup(tree, x) match {
     case null => None
     case tree => Some(tree.value)
   }
 
   @tailrec
-  def lookup[A, B](tree: Tree[A, B], x: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else {
+  def lookup[A, B](tree: Node[A, B], x: A)(implicit ordering: Ordering[A]): Node[A, B] = if (tree eq null) null else {
     val cmp = ordering.compare(x, tree.key)
     if (cmp < 0) lookup(tree.left, x)
     else if (cmp > 0) lookup(tree.right, x)
     else tree
   }
 
-  def count(tree: Tree[_, _]) = if (tree eq null) 0 else tree.count
-  def update[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = blacken(upd(tree, k, v))
-  def delete[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = blacken(del(tree, k))
-  def range[A, B](tree: Tree[A, B], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = blacken(rng(tree, from, until))
+  def count(tree: Node[_, _]) = if (tree eq null) 0 else tree.count
+  def update[A, B, B1 >: B](tree: Node[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Node[A, B1] = blacken(upd(tree, k, v))
+  def delete[A, B](tree: Node[A, B], k: A)(implicit ordering: Ordering[A]): Node[A, B] = blacken(del(tree, k))
+  def range[A, B](tree: Node[A, B], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Node[A, B] = blacken(rng(tree, from, until))
 
-  def smallest[A, B](tree: Tree[A, B]): Tree[A, B] = {
+  def smallest[A, B](tree: Node[A, B]): Node[A, B] = {
     if (tree eq null) throw new NoSuchElementException("empty map")
     var result = tree
     while (result.left ne null) result = result.left
     result
   }
-  def greatest[A, B](tree: Tree[A, B]): Tree[A, B] = {
+  def greatest[A, B](tree: Node[A, B]): Node[A, B] = {
     if (tree eq null) throw new NoSuchElementException("empty map")
     var result = tree
     while (result.right ne null) result = result.right
     result
   }
 
-  def foreach[A, B, U](tree: Tree[A, B], f: ((A, B)) => U): Unit = if (tree ne null) {
+  def foreach[A, B, U](tree: Node[A, B], f: ((A, B)) => U): Unit = if (tree ne null) {
     if (tree.left ne null) foreach(tree.left, f)
     f((tree.key, tree.value))
     if (tree.right ne null) foreach(tree.right, f)
   }
-  def foreachKey[A, U](tree: Tree[A, _], f: A => U): Unit = if (tree ne null) {
+  def foreachKey[A, U](tree: Node[A, _], f: A => U): Unit = if (tree ne null) {
     if (tree.left ne null) foreachKey(tree.left, f)
     f(tree.key)
     if (tree.right ne null) foreachKey(tree.right, f)
   }
 
-  def iterator[A, B](tree: Tree[A, B]): Iterator[(A, B)] = new EntriesIterator(tree)
-  def keysIterator[A, _](tree: Tree[A, _]): Iterator[A] = new KeysIterator(tree)
-  def valuesIterator[_, B](tree: Tree[_, B]): Iterator[B] = new ValuesIterator(tree)
+  def iterator[A, B](tree: Node[A, B]): Iterator[(A, B)] = new EntriesIterator(tree)
+  def keysIterator[A, _](tree: Node[A, _]): Iterator[A] = new KeysIterator(tree)
+  def valuesIterator[_, B](tree: Node[_, B]): Iterator[B] = new ValuesIterator(tree)
 
   @tailrec
-  def nth[A, B](tree: Tree[A, B], n: Int): Tree[A, B] = {
+  def nth[A, B](tree: Node[A, B], n: Int): Node[A, B] = {
     val count = RedBlack.count(tree.left)
     if (n < count) nth(tree.left, n)
     else if (n > count) nth(tree.right, n - count - 1)
     else tree
   }
 
-  private[this] def balanceLeft[A, B, B1 >: B](isBlack: Boolean, z: A, zv: B, l: Tree[A, B1], d: Tree[A, B1]): Tree[A, B1] = {
-    if (isRedTree(l) && isRedTree(l.left))
-      RedTree(l.key, l.value, BlackTree(l.left.key, l.left.value, l.left.left, l.left.right), BlackTree(z, zv, l.right, d))
-    else if (isRedTree(l) && isRedTree(l.right))
-      RedTree(l.right.key, l.right.value, BlackTree(l.key, l.value, l.left, l.right.left), BlackTree(z, zv, l.right.right, d))
+  private def blacken[A, B](t: Node[A, B]): Node[A, B] = if (t eq null) null else t.black
+
+  private def mkNode[A, B](isBlack: Boolean, k: A, v: B, l: Node[A, B], r: Node[A, B]) =
+    if (isBlack) BlackNode(k, v, l, r) else RedNode(k, v, l, r)
+
+  private[this] def balanceLeft[A, B, B1 >: B](isBlack: Boolean, z: A, zv: B, l: Node[A, B1], d: Node[A, B1]): Node[A, B1] = {
+    if (isRedNode(l) && isRedNode(l.left))
+      RedNode(l.key, l.value, BlackNode(l.left.key, l.left.value, l.left.left, l.left.right), BlackNode(z, zv, l.right, d))
+    else if (isRedNode(l) && isRedNode(l.right))
+      RedNode(l.right.key, l.right.value, BlackNode(l.key, l.value, l.left, l.right.left), BlackNode(z, zv, l.right.right, d))
     else
-      mkTree(isBlack, z, zv, l, d)
+      mkNode(isBlack, z, zv, l, d)
   }
-  private[this] def balanceRight[A, B, B1 >: B](isBlack: Boolean, x: A, xv: B, a: Tree[A, B1], r: Tree[A, B1]): Tree[A, B1] = {
-    if (isRedTree(r) && isRedTree(r.left))
-      RedTree(r.left.key, r.left.value, BlackTree(x, xv, a, r.left.left), BlackTree(r.key, r.value, r.left.right, r.right))
-    else if (isRedTree(r) && isRedTree(r.right))
-      RedTree(r.key, r.value, BlackTree(x, xv, a, r.left), BlackTree(r.right.key, r.right.value, r.right.left, r.right.right))
+  private[this] def balanceRight[A, B, B1 >: B](isBlack: Boolean, x: A, xv: B, a: Node[A, B1], r: Node[A, B1]): Node[A, B1] = {
+    if (isRedNode(r) && isRedNode(r.left))
+      RedNode(r.left.key, r.left.value, BlackNode(x, xv, a, r.left.left), BlackNode(r.key, r.value, r.left.right, r.right))
+    else if (isRedNode(r) && isRedNode(r.right))
+      RedNode(r.key, r.value, BlackNode(x, xv, a, r.left), BlackNode(r.right.key, r.right.value, r.right.left, r.right.right))
     else
-      mkTree(isBlack, x, xv, a, r)
+      mkNode(isBlack, x, xv, a, r)
   }
-  private[this] def upd[A, B, B1 >: B](tree: Tree[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Tree[A, B1] = if (tree eq null) {
-    RedTree(k, v, null, null)
+  private[this] def upd[A, B, B1 >: B](tree: Node[A, B], k: A, v: B1)(implicit ordering: Ordering[A]): Node[A, B1] = if (tree eq null) {
+    RedNode(k, v, null, null)
   } else {
     val cmp = ordering.compare(k, tree.key)
     if (cmp < 0) balanceLeft(tree.isBlack, tree.key, tree.value, upd(tree.left, k, v), tree.right)
     else if (cmp > 0) balanceRight(tree.isBlack, tree.key, tree.value, tree.left, upd(tree.right, k, v))
-    else mkTree(tree.isBlack, k, v, tree.left, tree.right)
+    else mkNode(tree.isBlack, k, v, tree.left, tree.right)
   }
 
     // Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
-    // http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html
-  private[this] def del[A, B](tree: Tree[A, B], k: A)(implicit ordering: Ordering[A]): Tree[A, B] = if (tree eq null) null else {
-    def balance(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
-      if (isRedTree(tr)) {
-        RedTree(x, xv, tl.black, tr.black)
-      } else if (isRedTree(tl.left)) {
-        RedTree(tl.key, tl.value, tl.left.black, BlackTree(x, xv, tl.right, tr))
-      } else if (isRedTree(tl.right)) {
-        RedTree(tl.right.key, tl.right.value, BlackTree(tl.key, tl.value, tl.left, tl.right.left), BlackTree(x, xv, tl.right.right, tr))
+    // http://www.cse.unsw.edu.au/~dons/data/RedBlackNode.html
+  private[this] def del[A, B](tree: Node[A, B], k: A)(implicit ordering: Ordering[A]): Node[A, B] = if (tree eq null) null else {
+    def balance(x: A, xv: B, tl: Node[A, B], tr: Node[A, B]) = if (isRedNode(tl)) {
+      if (isRedNode(tr)) {
+        RedNode(x, xv, tl.black, tr.black)
+      } else if (isRedNode(tl.left)) {
+        RedNode(tl.key, tl.value, tl.left.black, BlackNode(x, xv, tl.right, tr))
+      } else if (isRedNode(tl.right)) {
+        RedNode(tl.right.key, tl.right.value, BlackNode(tl.key, tl.value, tl.left, tl.right.left), BlackNode(x, xv, tl.right.right, tr))
       } else {
-        BlackTree(x, xv, tl, tr)
+        BlackNode(x, xv, tl, tr)
       }
-    } else if (isRedTree(tr)) {
-      if (isRedTree(tr.right)) {
-        RedTree(tr.key, tr.value, BlackTree(x, xv, tl, tr.left), tr.right.black)
-      } else if (isRedTree(tr.left)) {
-        RedTree(tr.left.key, tr.left.value, BlackTree(x, xv, tl, tr.left.left), BlackTree(tr.key, tr.value, tr.left.right, tr.right))
+    } else if (isRedNode(tr)) {
+      if (isRedNode(tr.right)) {
+        RedNode(tr.key, tr.value, BlackNode(x, xv, tl, tr.left), tr.right.black)
+      } else if (isRedNode(tr.left)) {
+        RedNode(tr.left.key, tr.left.value, BlackNode(x, xv, tl, tr.left.left), BlackNode(tr.key, tr.value, tr.left.right, tr.right))
       } else {
-        BlackTree(x, xv, tl, tr)
+        BlackNode(x, xv, tl, tr)
       }
     } else {
-      BlackTree(x, xv, tl, tr)
+      BlackNode(x, xv, tl, tr)
     }
-    def subl(t: Tree[A, B]) =
-      if (t.isInstanceOf[BlackTree[_, _]]) t.red
+    def subl(t: Node[A, B]) =
+      if (t.isInstanceOf[BlackNode[_, _]]) t.red
       else sys.error("Defect: invariance violation; expected black, got "+t)
 
-    def balLeft(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tl)) {
-      RedTree(x, xv, tl.black, tr)
-    } else if (isBlackTree(tr)) {
+    def balLeft(x: A, xv: B, tl: Node[A, B], tr: Node[A, B]) = if (isRedNode(tl)) {
+      RedNode(x, xv, tl.black, tr)
+    } else if (isBlackNode(tr)) {
       balance(x, xv, tl, tr.red)
-    } else if (isRedTree(tr) && isBlackTree(tr.left)) {
-      RedTree(tr.left.key, tr.left.value, BlackTree(x, xv, tl, tr.left.left), balance(tr.key, tr.value, tr.left.right, subl(tr.right)))
+    } else if (isRedNode(tr) && isBlackNode(tr.left)) {
+      RedNode(tr.left.key, tr.left.value, BlackNode(x, xv, tl, tr.left.left), balance(tr.key, tr.value, tr.left.right, subl(tr.right)))
     } else {
-      sys.error("Defect: invariance violation at ") // TODO
+      sys.error("Defect: invariance violation")
     }
-    def balRight(x: A, xv: B, tl: Tree[A, B], tr: Tree[A, B]) = if (isRedTree(tr)) {
-      RedTree(x, xv, tl, tr.black)
-    } else if (isBlackTree(tl)) {
+    def balRight(x: A, xv: B, tl: Node[A, B], tr: Node[A, B]) = if (isRedNode(tr)) {
+      RedNode(x, xv, tl, tr.black)
+    } else if (isBlackNode(tl)) {
       balance(x, xv, tl.red, tr)
-    } else if (isRedTree(tl) && isBlackTree(tl.right)) {
-      RedTree(tl.right.key, tl.right.value, balance(tl.key, tl.value, subl(tl.left), tl.right.left), BlackTree(x, xv, tl.right.right, tr))
+    } else if (isRedNode(tl) && isBlackNode(tl.right)) {
+      RedNode(tl.right.key, tl.right.value, balance(tl.key, tl.value, subl(tl.left), tl.right.left), BlackNode(x, xv, tl.right.right, tr))
     } else {
-      sys.error("Defect: invariance violation at ") // TODO
+      sys.error("Defect: invariance violation")
     }
-    def delLeft = if (isBlackTree(tree.left)) balLeft(tree.key, tree.value, del(tree.left, k), tree.right) else RedTree(tree.key, tree.value, del(tree.left, k), tree.right)
-    def delRight = if (isBlackTree(tree.right)) balRight(tree.key, tree.value, tree.left, del(tree.right, k)) else RedTree(tree.key, tree.value, tree.left, del(tree.right, k))
-    def append(tl: Tree[A, B], tr: Tree[A, B]): Tree[A, B] = if (tl eq null) {
+    def delLeft = if (isBlackNode(tree.left)) balLeft(tree.key, tree.value, del(tree.left, k), tree.right) else RedNode(tree.key, tree.value, del(tree.left, k), tree.right)
+    def delRight = if (isBlackNode(tree.right)) balRight(tree.key, tree.value, tree.left, del(tree.right, k)) else RedNode(tree.key, tree.value, tree.left, del(tree.right, k))
+    def append(tl: Node[A, B], tr: Node[A, B]): Node[A, B] = if (tl eq null) {
       tr
     } else if (tr eq null) {
       tl
-    } else if (isRedTree(tl) && isRedTree(tr)) {
+    } else if (isRedNode(tl) && isRedNode(tr)) {
       val bc = append(tl.right, tr.left)
-      if (isRedTree(bc)) {
-        RedTree(bc.key, bc.value, RedTree(tl.key, tl.value, tl.left, bc.left), RedTree(tr.key, tr.value, bc.right, tr.right))
+      if (isRedNode(bc)) {
+        RedNode(bc.key, bc.value, RedNode(tl.key, tl.value, tl.left, bc.left), RedNode(tr.key, tr.value, bc.right, tr.right))
       } else {
-        RedTree(tl.key, tl.value, tl.left, RedTree(tr.key, tr.value, bc, tr.right))
+        RedNode(tl.key, tl.value, tl.left, RedNode(tr.key, tr.value, bc, tr.right))
       }
-    } else if (isBlackTree(tl) && isBlackTree(tr)) {
+    } else if (isBlackNode(tl) && isBlackNode(tr)) {
       val bc = append(tl.right, tr.left)
-      if (isRedTree(bc)) {
-        RedTree(bc.key, bc.value, BlackTree(tl.key, tl.value, tl.left, bc.left), BlackTree(tr.key, tr.value, bc.right, tr.right))
+      if (isRedNode(bc)) {
+        RedNode(bc.key, bc.value, BlackNode(tl.key, tl.value, tl.left, bc.left), BlackNode(tr.key, tr.value, bc.right, tr.right))
       } else {
-        balLeft(tl.key, tl.value, tl.left, BlackTree(tr.key, tr.value, bc, tr.right))
+        balLeft(tl.key, tl.value, tl.left, BlackNode(tr.key, tr.value, bc, tr.right))
       }
-    } else if (isRedTree(tr)) {
-      RedTree(tr.key, tr.value, append(tl, tr.left), tr.right)
-    } else if (isRedTree(tl)) {
-      RedTree(tl.key, tl.value, tl.left, append(tl.right, tr))
+    } else if (isRedNode(tr)) {
+      RedNode(tr.key, tr.value, append(tl, tr.left), tr.right)
+    } else if (isRedNode(tl)) {
+      RedNode(tl.key, tl.value, tl.left, append(tl.right, tr))
     } else {
       sys.error("unmatched tree on append: " + tl + ", " + tr)
     }
@@ -197,7 +197,7 @@ object RedBlack {
     else append(tree.left, tree.right)
   }
 
-  private[this] def rng[A, B](tree: Tree[A, B], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Tree[A, B] = {
+  private[this] def rng[A, B](tree: Node[A, B], from: Option[A], until: Option[A])(implicit ordering: Ordering[A]): Node[A, B] = {
     if (tree eq null) return null
     if (from == None && until == None) return tree
     if (from != None && ordering.lt(tree.key, from.get)) return rng(tree.right, from, until);
@@ -219,9 +219,9 @@ object RedBlack {
   // whether the zipper was traversed left-most or right-most.
 
   // If the trees were balanced, returns an empty zipper
-  private[this] def compareDepth[A, B](left: Tree[A, B], right: Tree[A, B]): (List[Tree[A, B]], Boolean, Boolean, Int) = {
+  private[this] def compareDepth[A, B](left: Node[A, B], right: Node[A, B]): (List[Node[A, B]], Boolean, Boolean, Int) = {
     // Once a side is found to be deeper, unzip it to the bottom
-    def unzip(zipper: List[Tree[A, B]], leftMost: Boolean): List[Tree[A, B]] = {
+    def unzip(zipper: List[Node[A, B]], leftMost: Boolean): List[Node[A, B]] = {
       val next = if (leftMost) zipper.head.left else zipper.head.right
       next match {
         case null => zipper
@@ -231,25 +231,25 @@ object RedBlack {
 
     // Unzip left tree on the rightmost side and right tree on the leftmost side until one is
     // found to be deeper, or the bottom is reached
-    def unzipBoth(left: Tree[A, B],
-                  right: Tree[A, B],
-                  leftZipper: List[Tree[A, B]],
-                  rightZipper: List[Tree[A, B]],
-                  smallerDepth: Int): (List[Tree[A, B]], Boolean, Boolean, Int) = {
-      if (isBlackTree(left) && isBlackTree(right)) {
+    def unzipBoth(left: Node[A, B],
+                  right: Node[A, B],
+                  leftZipper: List[Node[A, B]],
+                  rightZipper: List[Node[A, B]],
+                  smallerDepth: Int): (List[Node[A, B]], Boolean, Boolean, Int) = {
+      if (isBlackNode(left) && isBlackNode(right)) {
         unzipBoth(left.right, right.left, left :: leftZipper, right :: rightZipper, smallerDepth + 1)
-      } else if (isRedTree(left) && isRedTree(right)) {
+      } else if (isRedNode(left) && isRedNode(right)) {
         unzipBoth(left.right, right.left, left :: leftZipper, right :: rightZipper, smallerDepth)
-      } else if (isRedTree(right)) {
+      } else if (isRedNode(right)) {
         unzipBoth(left, right.left, leftZipper, right :: rightZipper, smallerDepth)
-      } else if (isRedTree(left)) {
+      } else if (isRedNode(left)) {
         unzipBoth(left.right, right, left :: leftZipper, rightZipper, smallerDepth)
       } else if ((left eq null) && (right eq null)) {
         (Nil, true, false, smallerDepth)
-      } else if ((left eq null) && isBlackTree(right)) {
+      } else if ((left eq null) && isBlackNode(right)) {
         val leftMost = true
         (unzip(right :: rightZipper, leftMost), false, leftMost, smallerDepth)
-      } else if (isBlackTree(left) && (right eq null)) {
+      } else if (isBlackNode(left) && (right eq null)) {
         val leftMost = false
         (unzip(left :: leftZipper, leftMost), false, leftMost, smallerDepth)
       } else {
@@ -258,10 +258,10 @@ object RedBlack {
     }
     unzipBoth(left, right, Nil, Nil, 0)
   }
-   private[this] def rebalance[A, B](tree: Tree[A, B], newLeft: Tree[A, B], newRight: Tree[A, B]) = {
+  private[this] def rebalance[A, B](tree: Node[A, B], newLeft: Node[A, B], newRight: Node[A, B]) = {
     // This is like drop(n-1), but only counting black nodes
-    def  findDepth(zipper: List[Tree[A, B]], depth: Int): List[Tree[A, B]] = zipper match {
-      case head :: tail if isBlackTree(head) =>
+    def  findDepth(zipper: List[Node[A, B]], depth: Int): List[Node[A, B]] = zipper match {
+      case head :: tail if isBlackNode(head) =>
         if (depth == 1) zipper else findDepth(tail, depth - 1)
       case _ :: tail => findDepth(tail, depth)
       case Nil => sys.error("Defect: unexpected empty zipper while computing range")
@@ -274,15 +274,15 @@ object RedBlack {
     val (zipper, levelled, leftMost, smallerDepth) = compareDepth(blkNewLeft, blkNewRight)
 
     if (levelled) {
-      BlackTree(tree.key, tree.value, blkNewLeft, blkNewRight)
+      BlackNode(tree.key, tree.value, blkNewLeft, blkNewRight)
     } else {
       val zipFrom = findDepth(zipper, smallerDepth)
       val union = if (leftMost) {
-        RedTree(tree.key, tree.value, blkNewLeft, zipFrom.head)
+        RedNode(tree.key, tree.value, blkNewLeft, zipFrom.head)
       } else {
-        RedTree(tree.key, tree.value, zipFrom.head, blkNewRight)
+        RedNode(tree.key, tree.value, zipFrom.head, blkNewRight)
       }
-      val zippedTree = zipFrom.tail.foldLeft(union: Tree[A, B]) { (tree, node) =>
+      val zippedTree = zipFrom.tail.foldLeft(union: Node[A, B]) { (tree, node) =>
         if (leftMost)
           balanceLeft(node.isBlack, node.key, node.value, tree, node.right)
         else
@@ -301,47 +301,47 @@ object RedBlack {
    *
    * An alternative is to implement the these classes using plain old Java code...
    */
-  sealed abstract class Tree[A, +B](
+  sealed abstract class Node[A, +B](
     @(inline @getter) final val key: A,
     @(inline @getter) final val value: B,
-    @(inline @getter) final val left: Tree[A, B],
-    @(inline @getter) final val right: Tree[A, B])
+    @(inline @getter) final val left: Node[A, B],
+    @(inline @getter) final val right: Node[A, B])
   extends Serializable {
     final val count: Int = 1 + RedBlack.count(left) + RedBlack.count(right)
     def isBlack: Boolean
-    def black: Tree[A, B]
-    def red: Tree[A, B]
+    def black: Node[A, B]
+    def red: Node[A, B]
   }
-  final class RedTree[A, +B](key: A,
+  final class RedNode[A, +B](key: A,
                              value: B,
-                             left: Tree[A, B],
-                             right: Tree[A, B]) extends Tree[A, B](key, value, left, right) {
+                             left: Node[A, B],
+                             right: Node[A, B]) extends Node[A, B](key, value, left, right) {
     override def isBlack = false
-    override def black = BlackTree(key, value, left, right)
+    override def black = BlackNode(key, value, left, right)
     override def red = this
-    override def toString = "RedTree(" + key + ", " + value + ", " + left + ", " + right + ")"
+    override def toString = "RedNode(" + key + ", " + value + ", " + left + ", " + right + ")"
   }
-  final class BlackTree[A, +B](key: A,
+  final class BlackNode[A, +B](key: A,
                                value: B,
-                               left: Tree[A, B],
-                               right: Tree[A, B]) extends Tree[A, B](key, value, left, right) {
+                               left: Node[A, B],
+                               right: Node[A, B]) extends Node[A, B](key, value, left, right) {
     override def isBlack = true
     override def black = this
-    override def red = RedTree(key, value, left, right)
-    override def toString = "BlackTree(" + key + ", " + value + ", " + left + ", " + right + ")"
+    override def red = RedNode(key, value, left, right)
+    override def toString = "BlackNode(" + key + ", " + value + ", " + left + ", " + right + ")"
   }
 
-  object RedTree {
-    @inline def apply[A, B](key: A, value: B, left: Tree[A, B], right: Tree[A, B]) = new RedTree(key, value, left, right)
-    def unapply[A, B](t: RedTree[A, B]) = Some((t.key, t.value, t.left, t.right))
+  object RedNode {
+    @inline def apply[A, B](key: A, value: B, left: Node[A, B], right: Node[A, B]) = new RedNode(key, value, left, right)
+    def unapply[A, B](t: RedNode[A, B]) = Some((t.key, t.value, t.left, t.right))
   }
-  object BlackTree {
-    @inline def apply[A, B](key: A, value: B, left: Tree[A, B], right: Tree[A, B]) = new BlackTree(key, value, left, right)
-    def unapply[A, B](t: BlackTree[A, B]) = Some((t.key, t.value, t.left, t.right))
+  object BlackNode {
+    @inline def apply[A, B](key: A, value: B, left: Node[A, B], right: Node[A, B]) = new BlackNode(key, value, left, right)
+    def unapply[A, B](t: BlackNode[A, B]) = Some((t.key, t.value, t.left, t.right))
   }
 
-  private[this] abstract class TreeIterator[A, B, R](tree: Tree[A, B]) extends Iterator[R] {
-    protected[this] def nextResult(tree: Tree[A, B]): R
+  private[this] abstract class TreeIterator[A, B, R](tree: Node[A, B]) extends Iterator[R] {
+    protected[this] def nextResult(tree: Node[A, B]): R
 
     override def hasNext: Boolean = next ne null
 
@@ -354,7 +354,7 @@ object RedBlack {
     }
 
     @tailrec
-    private[this] def findNext(tree: Tree[A, B]): Tree[A, B] = {
+    private[this] def findNext(tree: Node[A, B]): Node[A, B] = {
       if (tree eq null) popPath()
       else if (tree.left eq null) tree
       else {
@@ -363,7 +363,7 @@ object RedBlack {
       }
     }
 
-    private[this] def pushPath(tree: Tree[A, B]) {
+    private[this] def pushPath(tree: Node[A, B]) {
       try {
         path(index) = tree
         index += 1
@@ -382,7 +382,7 @@ object RedBlack {
           pushPath(tree)
       }
     }
-    private[this] def popPath(): Tree[A, B] = if (index == 0) null else {
+    private[this] def popPath(): Node[A, B] = if (index == 0) null else {
       index -= 1
       path(index)
     }
@@ -397,21 +397,302 @@ object RedBlack {
        * We also don't store the deepest nodes in the path so the maximum path length is further reduced by one.
        */
       val maximumHeight = 2 * (32 - Integer.numberOfLeadingZeros(tree.count + 2 - 1)) - 2 - 1
-      new Array[Tree[A, B]](maximumHeight)
+      new Array[Node[A, B]](maximumHeight)
     }
     private[this] var index = 0
-    private[this] var next: Tree[A, B] = findNext(tree)
+    private[this] var next: Node[A, B] = findNext(tree)
+  }
+
+  private[this] class EntriesIterator[A, B](tree: Node[A, B]) extends TreeIterator[A, B, (A, B)](tree) {
+    override def nextResult(tree: Node[A, B]) = (tree.key, tree.value)
   }
 
-  private[this] class EntriesIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, (A, B)](tree) {
-    override def nextResult(tree: Tree[A, B]) = (tree.key, tree.value)
+  private[this] class KeysIterator[A, B](tree: Node[A, B]) extends TreeIterator[A, B, A](tree) {
+    override def nextResult(tree: Node[A, B]) = tree.key
   }
 
-  private[this] class KeysIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, A](tree) {
-    override def nextResult(tree: Tree[A, B]) = tree.key
+  private[this] class ValuesIterator[A, B](tree: Node[A, B]) extends TreeIterator[A, B, B](tree) {
+    override def nextResult(tree: Node[A, B]) = tree.value
   }
+}
+
+
+/** Old base class that was used by previous implementations of `TreeMaps` and `TreeSets`.
+ *
+ *  Deprecated due to various performance bugs (see [[https://issues.scala-lang.org/browse/SI-5331 SI-5331]] for more information).
+ *
+ *  @since 2.3
+ */
+@deprecated("use `TreeMap` or `TreeSet` instead", "2.10")
+@SerialVersionUID(8691885935445612921L)
+abstract class RedBlack[A] extends Serializable {
 
-  private[this] class ValuesIterator[A, B](tree: Tree[A, B]) extends TreeIterator[A, B, B](tree) {
-    override def nextResult(tree: Tree[A, B]) = tree.value
+  def isSmaller(x: A, y: A): Boolean
+
+  private def blacken[B](t: Tree[B]): Tree[B] = t match {
+    case RedTree(k, v, l, r) => BlackTree(k, v, l, r)
+    case t => t
+  }
+  private def mkTree[B](isBlack: Boolean, k: A, v: B, l: Tree[B], r: Tree[B]) =
+    if (isBlack) BlackTree(k, v, l, r) else RedTree(k, v, l, r)
+
+  abstract class Tree[+B] extends Serializable {
+    def isEmpty: Boolean
+    def isBlack: Boolean
+    def lookup(x: A): Tree[B]
+    def update[B1 >: B](k: A, v: B1): Tree[B1] = blacken(upd(k, v))
+    def delete(k: A): Tree[B] = blacken(del(k))
+    def range(from: Option[A], until: Option[A]): Tree[B] = blacken(rng(from, until))
+    def foreach[U](f: (A, B) =>  U)
+    def toStream: Stream[(A,B)]
+    def iterator: Iterator[(A, B)]
+    def upd[B1 >: B](k: A, v: B1): Tree[B1]
+    def del(k: A): Tree[B]
+    def smallest: NonEmpty[B]
+    def rng(from: Option[A], until: Option[A]): Tree[B]
+    def first : A
+    def last : A
+    def count : Int
+  }
+  abstract class NonEmpty[+B] extends Tree[B] with Serializable {
+    def isEmpty = false
+    def key: A
+    def value: B
+    def left: Tree[B]
+    def right: Tree[B]
+    def lookup(k: A): Tree[B] =
+      if (isSmaller(k, key)) left.lookup(k)
+      else if (isSmaller(key, k)) right.lookup(k)
+      else this
+    private[this] def balanceLeft[B1 >: B](isBlack: Boolean, z: A, zv: B, l: Tree[B1], d: Tree[B1])/*: NonEmpty[B1]*/ = l match {
+      case RedTree(y, yv, RedTree(x, xv, a, b), c) =>
+        RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+      case RedTree(x, xv, a, RedTree(y, yv, b, c)) =>
+        RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+      case _ =>
+        mkTree(isBlack, z, zv, l, d)
+    }
+    private[this] def balanceRight[B1 >: B](isBlack: Boolean, x: A, xv: B, a: Tree[B1], r: Tree[B1])/*: NonEmpty[B1]*/ = r match {
+      case RedTree(z, zv, RedTree(y, yv, b, c), d) =>
+        RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+      case RedTree(y, yv, b, RedTree(z, zv, c, d)) =>
+        RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+      case _ =>
+        mkTree(isBlack, x, xv, a, r)
+    }
+    def upd[B1 >: B](k: A, v: B1): Tree[B1] = {
+      if (isSmaller(k, key)) balanceLeft(isBlack, key, value, left.upd(k, v), right)
+      else if (isSmaller(key, k)) balanceRight(isBlack, key, value, left, right.upd(k, v))
+      else mkTree(isBlack, k, v, left, right)
+    }
+    // Based on Stefan Kahrs' Haskell version of Okasaki's Red&Black Trees
+    // http://www.cse.unsw.edu.au/~dons/data/RedBlackTree.html
+    def del(k: A): Tree[B] = {
+      def balance(x: A, xv: B, tl: Tree[B], tr: Tree[B]) = (tl, tr) match {
+        case (RedTree(y, yv, a, b), RedTree(z, zv, c, d)) =>
+          RedTree(x, xv, BlackTree(y, yv, a, b), BlackTree(z, zv, c, d))
+        case (RedTree(y, yv, RedTree(z, zv, a, b), c), d) =>
+          RedTree(y, yv, BlackTree(z, zv, a, b), BlackTree(x, xv, c, d))
+        case (RedTree(y, yv, a, RedTree(z, zv, b, c)), d) =>
+          RedTree(z, zv, BlackTree(y, yv, a, b), BlackTree(x, xv, c, d))
+        case (a, RedTree(y, yv, b, RedTree(z, zv, c, d))) =>
+          RedTree(y, yv, BlackTree(x, xv, a, b), BlackTree(z, zv, c, d))
+        case (a, RedTree(y, yv, RedTree(z, zv, b, c), d)) =>
+          RedTree(z, zv, BlackTree(x, xv, a, b), BlackTree(y, yv, c, d))
+        case (a, b) =>
+          BlackTree(x, xv, a, b)
+      }
+      def subl(t: Tree[B]) = t match {
+        case BlackTree(x, xv, a, b) => RedTree(x, xv, a, b)
+        case _ => sys.error("Defect: invariance violation; expected black, got "+t)
+      }
+      def balLeft(x: A, xv: B, tl: Tree[B], tr: Tree[B]) = (tl, tr) match {
+        case (RedTree(y, yv, a, b), c) =>
+          RedTree(x, xv, BlackTree(y, yv, a, b), c)
+        case (bl, BlackTree(y, yv, a, b)) =>
+          balance(x, xv, bl, RedTree(y, yv, a, b))
+        case (bl, RedTree(y, yv, BlackTree(z, zv, a, b), c)) =>
+          RedTree(z, zv, BlackTree(x, xv, bl, a), balance(y, yv, b, subl(c)))
+        case _ => sys.error("Defect: invariance violation at "+right)
+      }
+      def balRight(x: A, xv: B, tl: Tree[B], tr: Tree[B]) = (tl, tr) match {
+        case (a, RedTree(y, yv, b, c)) =>
+          RedTree(x, xv, a, BlackTree(y, yv, b, c))
+        case (BlackTree(y, yv, a, b), bl) =>
+          balance(x, xv, RedTree(y, yv, a, b), bl)
+        case (RedTree(y, yv, a, BlackTree(z, zv, b, c)), bl) =>
+          RedTree(z, zv, balance(y, yv, subl(a), b), BlackTree(x, xv, c, bl))
+        case _ => sys.error("Defect: invariance violation at "+left)
+      }
+      def delLeft = left match {
+        case _: BlackTree[_] => balLeft(key, value, left.del(k), right)
+        case _ => RedTree(key, value, left.del(k), right)
+      }
+      def delRight = right match {
+        case _: BlackTree[_] => balRight(key, value, left, right.del(k))
+        case _ => RedTree(key, value, left, right.del(k))
+      }
+      def append(tl: Tree[B], tr: Tree[B]): Tree[B] = (tl, tr) match {
+        case (Empty, t) => t
+        case (t, Empty) => t
+        case (RedTree(x, xv, a, b), RedTree(y, yv, c, d)) =>
+          append(b, c) match {
+            case RedTree(z, zv, bb, cc) => RedTree(z, zv, RedTree(x, xv, a, bb), RedTree(y, yv, cc, d))
+            case bc => RedTree(x, xv, a, RedTree(y, yv, bc, d))
+          }
+        case (BlackTree(x, xv, a, b), BlackTree(y, yv, c, d)) =>
+          append(b, c) match {
+            case RedTree(z, zv, bb, cc) => RedTree(z, zv, BlackTree(x, xv, a, bb), BlackTree(y, yv, cc, d))
+            case bc => balLeft(x, xv, a, BlackTree(y, yv, bc, d))
+          }
+        case (a, RedTree(x, xv, b, c)) => RedTree(x, xv, append(a, b), c)
+        case (RedTree(x, xv, a, b), c) => RedTree(x, xv, a, append(b, c))
+      }
+      // RedBlack is neither A : Ordering[A], nor A <% Ordered[A]
+      k match {
+        case _ if isSmaller(k, key) => delLeft
+        case _ if isSmaller(key, k) => delRight
+        case _ => append(left, right)
+      }
+    }
+
+    def smallest: NonEmpty[B] = if (left.isEmpty) this else left.smallest
+
+    def toStream: Stream[(A,B)] =
+      left.toStream ++ Stream((key,value)) ++ right.toStream
+
+    def iterator: Iterator[(A, B)] =
+      left.iterator ++ Iterator.single(Pair(key, value)) ++ right.iterator
+
+    def foreach[U](f: (A, B) => U) {
+      left foreach f
+      f(key, value)
+      right foreach f
+    }
+
+    override def rng(from: Option[A], until: Option[A]): Tree[B] = {
+      if (from == None && until == None) return this
+      if (from != None && isSmaller(key, from.get)) return right.rng(from, until);
+      if (until != None && (isSmaller(until.get,key) || !isSmaller(key,until.get)))
+        return left.rng(from, until);
+      val newLeft = left.rng(from, None)
+      val newRight = right.rng(None, until)
+      if ((newLeft eq left) && (newRight eq right)) this
+      else if (newLeft eq Empty) newRight.upd(key, value);
+      else if (newRight eq Empty) newLeft.upd(key, value);
+      else rebalance(newLeft, newRight)
+    }
+
+    // The zipper returned might have been traversed left-most (always the left child)
+    // or right-most (always the right child). Left trees are traversed right-most,
+    // and right trees are traversed leftmost.
+
+    // Returns the zipper for the side with deepest black nodes depth, a flag
+    // indicating whether the trees were unbalanced at all, and a flag indicating
+    // whether the zipper was traversed left-most or right-most.
+
+    // If the trees were balanced, returns an empty zipper
+    private[this] def compareDepth(left: Tree[B], right: Tree[B]): (List[NonEmpty[B]], Boolean, Boolean, Int) = {
+      // Once a side is found to be deeper, unzip it to the bottom
+      def unzip(zipper: List[NonEmpty[B]], leftMost: Boolean): List[NonEmpty[B]] = {
+        val next = if (leftMost) zipper.head.left else zipper.head.right
+        next match {
+          case node: NonEmpty[_] => unzip(node :: zipper, leftMost)
+          case Empty             => zipper
+        }
+      }
+
+      // Unzip left tree on the rightmost side and right tree on the leftmost side until one is
+      // found to be deeper, or the bottom is reached
+      def unzipBoth(left: Tree[B],
+                    right: Tree[B],
+                    leftZipper: List[NonEmpty[B]],
+                    rightZipper: List[NonEmpty[B]],
+                    smallerDepth: Int): (List[NonEmpty[B]], Boolean, Boolean, Int) = (left, right) match {
+        case (l @ BlackTree(_, _, _, _), r @ BlackTree(_, _, _, _)) =>
+          unzipBoth(l.right, r.left, l :: leftZipper, r :: rightZipper, smallerDepth + 1)
+        case (l @ RedTree(_, _, _, _), r @ RedTree(_, _, _, _)) =>
+          unzipBoth(l.right, r.left, l :: leftZipper, r :: rightZipper, smallerDepth)
+        case (_, r @ RedTree(_, _, _, _)) =>
+          unzipBoth(left, r.left, leftZipper, r :: rightZipper, smallerDepth)
+        case (l @ RedTree(_, _, _, _), _) =>
+          unzipBoth(l.right, right, l :: leftZipper, rightZipper, smallerDepth)
+        case (Empty, Empty) =>
+          (Nil, true, false, smallerDepth)
+        case (Empty, r @ BlackTree(_, _, _, _)) =>
+          val leftMost = true
+          (unzip(r :: rightZipper, leftMost), false, leftMost, smallerDepth)
+        case (l @ BlackTree(_, _, _, _), Empty) =>
+          val leftMost = false
+          (unzip(l :: leftZipper, leftMost), false, leftMost, smallerDepth)
+      }
+      unzipBoth(left, right, Nil, Nil, 0)
+    }
+
+    private[this] def rebalance(newLeft: Tree[B], newRight: Tree[B]) = {
+      // This is like drop(n-1), but only counting black nodes
+      def  findDepth(zipper: List[NonEmpty[B]], depth: Int): List[NonEmpty[B]] = zipper match {
+        case BlackTree(_, _, _, _) :: tail =>
+          if (depth == 1) zipper else findDepth(tail, depth - 1)
+        case _ :: tail => findDepth(tail, depth)
+        case Nil => sys.error("Defect: unexpected empty zipper while computing range")
+      }
+
+      // Blackening the smaller tree avoids balancing problems on union;
+      // this can't be done later, though, or it would change the result of compareDepth
+      val blkNewLeft = blacken(newLeft)
+      val blkNewRight = blacken(newRight)
+      val (zipper, levelled, leftMost, smallerDepth) = compareDepth(blkNewLeft, blkNewRight)
+
+      if (levelled) {
+        BlackTree(key, value, blkNewLeft, blkNewRight)
+      } else {
+        val zipFrom = findDepth(zipper, smallerDepth)
+        val union = if (leftMost) {
+          RedTree(key, value, blkNewLeft, zipFrom.head)
+        } else {
+          RedTree(key, value, zipFrom.head, blkNewRight)
+        }
+        val zippedTree = zipFrom.tail.foldLeft(union: Tree[B]) { (tree, node) =>
+            if (leftMost)
+              balanceLeft(node.isBlack, node.key, node.value, tree, node.right)
+            else
+              balanceRight(node.isBlack, node.key, node.value, node.left, tree)
+        }
+        zippedTree
+      }
+    }
+    def first = if (left .isEmpty) key else left.first
+    def last  = if (right.isEmpty) key else right.last
+    def count = 1 + left.count + right.count
+  }
+  case object Empty extends Tree[Nothing] {
+    def isEmpty = true
+    def isBlack = true
+    def lookup(k: A): Tree[Nothing] = this
+    def upd[B](k: A, v: B): Tree[B] = RedTree(k, v, Empty, Empty)
+    def del(k: A): Tree[Nothing] = this
+    def smallest: NonEmpty[Nothing] = throw new NoSuchElementException("empty map")
+    def iterator: Iterator[(A, Nothing)] = Iterator.empty
+    def toStream: Stream[(A,Nothing)] = Stream.empty
+
+    def foreach[U](f: (A, Nothing) => U) {}
+
+    def rng(from: Option[A], until: Option[A]) = this
+    def first = throw new NoSuchElementException("empty map")
+    def last = throw new NoSuchElementException("empty map")
+    def count = 0
+  }
+  case class RedTree[+B](override val key: A,
+                         override val value: B,
+                         override val left: Tree[B],
+                         override val right: Tree[B]) extends NonEmpty[B] {
+    def isBlack = false
+  }
+  case class BlackTree[+B](override val key: A,
+                           override val value: B,
+                           override val left: Tree[B],
+                           override val right: Tree[B]) extends NonEmpty[B] {
+    def isBlack = true
   }
 }
diff --git a/src/library/scala/collection/immutable/TreeMap.scala b/src/library/scala/collection/immutable/TreeMap.scala
index 65e42ad061..50244ef21d 100644
--- a/src/library/scala/collection/immutable/TreeMap.scala
+++ b/src/library/scala/collection/immutable/TreeMap.scala
@@ -45,7 +45,7 @@ object TreeMap extends ImmutableSortedMapFactory[TreeMap] {
  *  @define mayNotTerminateInf
  *  @define willNotTerminateInf
  */
-class TreeMap[A, +B] private (tree: RedBlack.Tree[A, B])(implicit val ordering: Ordering[A])
+class TreeMap[A, +B] private (tree: RedBlack.Node[A, B])(implicit val ordering: Ordering[A])
   extends SortedMap[A, B]
      with SortedMapLike[A, B, TreeMap[A, B]]
      with MapLike[A, B, TreeMap[A, B]]
diff --git a/src/library/scala/collection/immutable/TreeSet.scala b/src/library/scala/collection/immutable/TreeSet.scala
index f7ceafdf8f..899ef0e5eb 100644
--- a/src/library/scala/collection/immutable/TreeSet.scala
+++ b/src/library/scala/collection/immutable/TreeSet.scala
@@ -47,7 +47,7 @@ object TreeSet extends ImmutableSortedSetFactory[TreeSet] {
  *  @define willNotTerminateInf
  */
 @SerialVersionUID(-5685982407650748405L)
-class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: Ordering[A])
+class TreeSet[A] private (tree: RedBlack.Node[A, Unit])(implicit val ordering: Ordering[A])
   extends SortedSet[A] with SortedSetLike[A, TreeSet[A]] with Serializable {
 
   import immutable.{RedBlack => RB}
@@ -105,7 +105,7 @@ class TreeSet[A] private (tree: RedBlack.Tree[A, Unit])(implicit val ordering: O
 
   def this()(implicit ordering: Ordering[A]) = this(null)(ordering)
 
-  private def newSet(t: RedBlack.Tree[A, Unit]) = new TreeSet[A](t)
+  private def newSet(t: RedBlack.Node[A, Unit]) = new TreeSet[A](t)
 
   /** A factory to create empty sets of the same type of keys.
    */
diff --git a/test/files/scalacheck/redblack.scala b/test/files/scalacheck/redblack.scala
index 5c52a27e38..83d3ca0c1f 100644
--- a/test/files/scalacheck/redblack.scala
+++ b/test/files/scalacheck/redblack.scala
@@ -22,14 +22,14 @@ abstract class RedBlackTest extends Properties("RedBlack") {
 
   import RedBlack._
 
-  def nodeAt[A](tree: Tree[String, A], n: Int): Option[(String, A)] = if (n < iterator(tree).size && n >= 0)
+  def nodeAt[A](tree: Node[String, A], n: Int): Option[(String, A)] = if (n < iterator(tree).size && n >= 0)
     Some(iterator(tree).drop(n).next)
   else
     None
 
-  def treeContains[A](tree: Tree[String, A], key: String) = iterator(tree).map(_._1) contains key
+  def treeContains[A](tree: Node[String, A], key: String) = iterator(tree).map(_._1) contains key
 
-  def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Tree[String, Int]] =
+  def mkTree(level: Int, parentIsBlack: Boolean = false, label: String = ""): Gen[Node[String, Int]] =
     if (level == 0) {
       value(null)
     } else {
@@ -42,9 +42,9 @@ abstract class RedBlackTest extends Properties("RedBlack") {
         right <- mkTree(nextLevel, !isRed, label + "R")
       } yield {
         if (isRed)
-          RedTree(label + "N", 0, left, right)
+          RedNode(label + "N", 0, left, right)
         else
-          BlackTree(label + "N", 0, left, right)
+          BlackNode(label + "N", 0, left, right)
       }
     }
 
@@ -54,10 +54,10 @@ abstract class RedBlackTest extends Properties("RedBlack") {
   } yield tree
 
   type ModifyParm
-  def genParm(tree: Tree[String, Int]): Gen[ModifyParm]
-  def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int]
+  def genParm(tree: Node[String, Int]): Gen[ModifyParm]
+  def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int]
 
-  def genInput: Gen[(Tree[String, Int], ModifyParm, Tree[String, Int])] = for {
+  def genInput: Gen[(Node[String, Int], ModifyParm, Node[String, Int])] = for {
     tree <- genTree
     parm <- genParm(tree)
   } yield (tree, parm, modify(tree, parm))
@@ -68,26 +68,26 @@ trait RedBlackInvariants {
 
   import RedBlack._
 
-  def rootIsBlack[A](t: Tree[String, A]) = isBlack(t)
+  def rootIsBlack[A](t: Node[String, A]) = isBlack(t)
 
-  def areAllLeavesBlack[A](t: Tree[String, A]): Boolean = t match {
+  def areAllLeavesBlack[A](t: Node[String, A]): Boolean = t match {
     case null => isBlack(t)
     case ne => List(ne.left, ne.right) forall areAllLeavesBlack
   }
 
-  def areRedNodeChildrenBlack[A](t: Tree[String, A]): Boolean = t match {
-    case RedTree(_, _, left, right) => List(left, right) forall (t => isBlack(t) && areRedNodeChildrenBlack(t))
-    case BlackTree(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack
+  def areRedNodeChildrenBlack[A](t: Node[String, A]): Boolean = t match {
+    case RedNode(_, _, left, right) => List(left, right) forall (t => isBlack(t) && areRedNodeChildrenBlack(t))
+    case BlackNode(_, _, left, right) => List(left, right) forall areRedNodeChildrenBlack
     case null => true
   }
 
-  def blackNodesToLeaves[A](t: Tree[String, A]): List[Int] = t match {
+  def blackNodesToLeaves[A](t: Node[String, A]): List[Int] = t match {
     case null => List(1)
-    case BlackTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1)
-    case RedTree(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves
+    case BlackNode(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves map (_ + 1)
+    case RedNode(_, _, left, right) => List(left, right) flatMap blackNodesToLeaves
   }
 
-  def areBlackNodesToLeavesEqual[A](t: Tree[String, A]): Boolean = t match {
+  def areBlackNodesToLeavesEqual[A](t: Node[String, A]): Boolean = t match {
     case null => true
     case ne =>
       (
@@ -97,10 +97,10 @@ trait RedBlackInvariants {
       )
   }
 
-  def orderIsPreserved[A](t: Tree[String, A]): Boolean =
+  def orderIsPreserved[A](t: Node[String, A]): Boolean =
     iterator(t) zip iterator(t).drop(1) forall { case (x, y) => x._1 < y._1 }
 
-  def setup(invariant: Tree[String, Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) =>
+  def setup(invariant: Node[String, Int] => Boolean) = forAll(genInput) { case (tree, parm, newTree) =>
     invariant(newTree)
   }
 
@@ -115,10 +115,10 @@ object TestInsert extends RedBlackTest with RedBlackInvariants {
   import RedBlack._
 
   override type ModifyParm = Int
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size + 1)
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = update(tree, generateKey(tree, parm), 0)
+  override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size + 1)
+  override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = update(tree, generateKey(tree, parm), 0)
 
-  def generateKey(tree: Tree[String, Int], parm: ModifyParm): String = nodeAt(tree, parm) match {
+  def generateKey(tree: Node[String, Int], parm: ModifyParm): String = nodeAt(tree, parm) match {
     case Some((key, _)) => key.init.mkString + "MN"
     case None => nodeAt(tree, parm - 1) match {
       case Some((key, _)) => key.init.mkString + "RN"
@@ -137,8 +137,8 @@ object TestModify extends RedBlackTest {
   def newValue = 1
   override def minimumSize = 1
   override type ModifyParm = Int
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size)
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map {
+  override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size)
+  override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = nodeAt(tree, parm) map {
     case (key, _) => update(tree, key, newValue)
   } getOrElse tree
 
@@ -154,8 +154,8 @@ object TestDelete extends RedBlackTest with RedBlackInvariants  {
 
   override def minimumSize = 1
   override type ModifyParm = Int
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size)
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = nodeAt(tree, parm) map {
+  override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = choose(0, iterator(tree).size)
+  override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = nodeAt(tree, parm) map {
     case (key, _) => delete(tree, key)
   } getOrElse tree
 
@@ -170,14 +170,14 @@ object TestRange extends RedBlackTest with RedBlackInvariants  {
   import RedBlack._
 
   override type ModifyParm = (Option[Int], Option[Int])
-  override def genParm(tree: Tree[String, Int]): Gen[ModifyParm] = for {
+  override def genParm(tree: Node[String, Int]): Gen[ModifyParm] = for {
     from <- choose(0, iterator(tree).size)
     to <- choose(0, iterator(tree).size) suchThat (from <=)
     optionalFrom <- oneOf(Some(from), None, Some(from)) // Double Some(n) to get around a bug
     optionalTo <- oneOf(Some(to), None, Some(to)) // Double Some(n) to get around a bug
   } yield (optionalFrom, optionalTo)
 
-  override def modify(tree: Tree[String, Int], parm: ModifyParm): Tree[String, Int] = {
+  override def modify(tree: Node[String, Int], parm: ModifyParm): Node[String, Int] = {
     val from = parm._1 flatMap (nodeAt(tree, _) map (_._1))
     val to = parm._2 flatMap (nodeAt(tree, _) map (_._1))
     range(tree, from, to)