O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required