Learning Functional Data Structures and Algorithms

Inserting a node

When we insert a node, we color it red. This means that the newly inserted node will never change the black height of any ancestor!

However, it could violate another invariant, namely a red node can never have a red parent. Once we fix this invariant violation, we are done! Here's the code to do this:

sealed trait Color 
case object Red extends Color 
case object Black extends Color 

We know the advantages of sealing a trait. The Color trait can now be used only in this source file. This helps the compiler check for exhaustive matching. As seen earlier, the List and BinTree traits were also sealed.

The case object idiom creates singleton objects, just like List.Nil and Bintree.Leaf.

Next, we define our Tree class:

sealed abstract class ...