Scala 2.8 Collections API -- Red-Black Trees

Red-Black Trees

Red-Black Trees

Red-black trees are a form of balanced binary trees where some nodes are designated "red" and others designated "black." Like any balanced binary tree, operations on them reliably complete in time logarithmic to the size of the tree.

Scala provides implementations of immutable sets and maps that use a red-black tree internally. Access them under the names TreeSet and TreeMap.

scala> scala.collection.immutable.TreeSet.empty[Int]

res11: scala.collection.immutable.TreeSet[Int] = TreeSet()

scala> res11 + 1 + 3 + 3

res12: scala.collection.immutable.TreeSet[Int] = TreeSet(1, 3)

Red black trees are the standard implementation of SortedSet in Scala, because they provide an efficient iterator that returns all elements in sorted order.

Next: Immutable BitSets

Red-Black Trees

Contents