Learning Functional Data Structures and Algorithms

List of tree roots

Time to change gears; we know that binary trees' lookup and update operations are fast. Fast lookup is the result of storing actual data elements in binary trees, that is, all the roots linked up in a list.

Here are our tree definitions:

scala> sealed abstract class Tree { 
     |   def size: Int 
     | } 

Note the use of the sealed keyword. It is sealed, which means the definition could be used in this file only. We have an abstract method to know how many data elements (leaves) exist in this tree:

scala> case class Leaf(n: Int) extends Tree { 
     |   override def size = 1 
     | } 

The Leaf class actually holds the data items. As the name indicates, it ...