Idea:

• update creates a new path (copying only log(n) nodes)
• lookup and update in log(n)

We present a simplified example that stores integers

• a real implementation stores comparable objects
• instead of '<' below, we would use the comparison method

sealed abstract class BST
case class Empty() extends BST
case class Node(left: BST, value: Int, right: BST) extends BST

def contains(key: Int, t : BST): Boolean = t match {
  case Empty() => false
  case Node(left,v,right) => {
    if (key == v) true
    else if (key < v) contains(key, left)
    else contains(key, right)
  }
}

def add(x : Int, t : BST) : Node = t match {
  case Empty() => Node(Empty(),x,Empty())
  case t @ Node(left,v,right) => {
    if (x < v) Node(add(x, left), v, right)
    else if (x==v) t
    else Node(left, v, add(x, right))
  }
}

Idea:

• prevent tree from degenerating into a list with bad sequence of insertions
• rebalance tree after each change

Invariants that imply balancing formulated using nodes of two colors: red and black.

• red node must have black children
• each path in tree from root to children must have the same number of black nodes

sealed abstract class Color
case class Red() extends Color
case class Black() extends Color
 
sealed abstract class Tree
case class Empty() extends Tree
case class Node(color: Color, left: Tree, value: Int, right: Tree) extends Tree

def add(x: Int, t: Tree): Tree = {
  def ins(t: Tree): Tree = t match {
    case Empty() => Node(Red(),Empty(),x,Empty())
    case Node(c,a,y,b) =>
      if      (x < y)  balance(c, ins(a), y, b)
      else if (x == y) Node(c,a,y,b)
      else             balance(c,a,y,ins(b))
  }
  makeBlack(ins(t))
}
 
def balance(c: Color, a: Tree, x: Int, b: Tree): Tree = (c,a,x,b) match {
  case (Black(),Node(Red(),Node(Red(),a,xV,b),yV,c),zV,d) => 
    Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
  case (Black(),Node(Red(),a,xV,Node(Red(),b,yV,c)),zV,d) => 
    Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
  case (Black(),a,xV,Node(Red(),Node(Red(),b,yV,c),zV,d)) => 
    Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
  case (Black(),a,xV,Node(Red(),b,yV,Node(Red(),c,zV,d))) => 
    Node(Red(),Node(Black(),a,xV,b),yV,Node(Black(),c,zV,d))
  case (c,a,xV,b) => Node(c,a,xV,b)  
}
 
def makeBlack(n: Tree): Tree = n match {
  case Node(Red(),l,v,r) => Node(Black(),l,v,r)
  case _ => n
}

• keep old versions (e.g. when exiting scope, the old scope is around)
• easier to prove correct

• Book by Chris Okasaki: Purely Functional Data Structures
• Red-Black Trees in Functional Settings (a pearl)
• Binary Search Trees Proved Correct
• AVL Trees Proved Correct (also balanced, but not red-black)

Emulate functional behavior using an imperative hash table

• internally mutable, observationally immutable

Insertion:

• updates the hashtable
• creates a log entry that specifies how the old version differs from new one

Old version:

• checks if the value has been changed, if so uses log to look it up
• otherwise looks up the log in the table

Benefits:

• constant-time access for last version produced in computation

• Immutable TreeMap in Scala