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
BinTree traits were also sealed.
The case object idiom creates singleton objects, just like
Next, we define our
sealed abstract class ...