CODEWITHSUNDEEP
scalab-tree
Alonzo Robbe
Alonzo Robbe

Reputation: 475

How to implement 'find' method for this Btree implementation

So im learning Scala. This is the base class for all Nodes and BTree 

abstract sealed class Node[T](implicit val ord : Ordering[T])

abstract sealed class BTree[T](implicit ord : Ordering[T])
extends Node[T] {
def size : Int
def depth : Int

And heres the base case clases

object BTree {
//empty node
final case class EmptyNode[T]()(implicit ord : Ordering[T])
  extends BTree[T] {
val size : Int = 0
val depth : Int = 0
}
//node with 1 child
final case class OneNode[T](t : BTree[T])(implicit ord : Ordering[T])
  extends Node[T] {
val size : Int = t.size
val depth : Int = t.depth + 1
}
//node with 2 children
final case class TwoNode[T](t1 : BTree[T], u1 : T, t2 : BTree[T])
                      (implicit ord : Ordering[T]) extends BTree[T] {
val size : Int = t1.size + t2.size + 1
val depth : Int = max(t1.depth, t2.depth) + 1
}

And they continue the pattern for ThreeNode and FourNode

Now in the BTree class, I have to implement a find function 

//return `Some` of entry if equivalent is found, None if not. 
def find(v : T) : Option[T] =

and Im having trouble wrapping my head around what I need to do. In Java, I would just do a loop going through each node or what ever, but Scala I have no idea. Even the Some thing. Is the return just Some(v)? Anyway, heres what I could come up with 

//return `Some` of entry if equivalent is found, None if not. 
def find(v : T) : Option[T] = 
this match {

  case EmptyNode() => None

  case TwoNode(EmptyNode(), u1, EmptyNode()) if (v equiv u1) =>
    Some(v)

  case TwoNode(t1, u1, t2) if (v equiv u1) =>
    Some(v)

Im having trouble figuring out what to do in these cases:

  case TwoNode(t1, u1, t2) if (v < u1) => 

  case TwoNode(t1, u1, t2) if (u1 < v) =>

where the entry might be further down the tree.

I have similar cases for ThreeNode 

  case ThreeNode(EmptyNode(), u1, EmptyNode(), u2, EmptyNode()) if (v equiv u1) =>
    Some(v)
  case ThreeNode(EmptyNode(), u1, EmptyNode(), u2, EmptyNode()) if (v equiv u2) =>
    Some(v)

  case ThreeNode(t1, u1, t2, u2, t3) if (v equiv u1) =>
    Some(v)
  case ThreeNode(t1, u1, t2, u2, t3) if (v equiv u2) =>
    Some(v)

But once again, cant figure out what to do if v is further below the tree. 

   case ThreeNode(t1, u1, t2, u2, t3) if (v < u1) =>

   case ThreeNode(t1, u1, t2, u2, t3) if (u1 < v  && v < u2) =>

   case ThreeNode(t1, u1, t2, u2, t3) if (u2 < v) =>

I also not sure if doing Some(v) is the correct thing to do when found.

Any help appreciated. Thank you

Upvotes: 0

Views: 155

Answers (1)

Tim
Tim

Reputation: 27356

You need to use a recursive find method, something like this:

  def find(v: T): Boolean =
    this match {
      case OneNode(t1, u1) =>
        (u1 == v) || t1.find(v)
      case TwoNode(t1, u1, t2) =>
        (u1 == v) || t1.find(v) || t2.find(v)
      case _ => false
    }

This version returns Boolean because the value is either there or it isn't. If wanted to return the node where the value resides then you need to return Option[BTree[T]] and the logic gets more complicated:

  def findNode(v: T): Option[BTree[T]] =
    this match {
      case OneNode(t1, u1) =>
        if (u1 == v) {
          Some(this)
        } else {
          t1.findNode(v)
        }
      case TwoNode(t1, u1, t2) =>
        if (u1 == v) {
          Some(this)
        } else {
          t1.findNode(v) orElse t2.findNode(v)
        }
      case _ => None
    }

With 4 nodes this is going to get unwieldy, so I suggest that you use List[BTree[T]] rather than enumerating the sub-nodes. This will make the code much clearer.

Also note that you need to add a u1 member to OneNode and it should inherit from BTree[T] not Node[T] or else you won't be able to add it to other nodes.

Upvotes: 1

Related Questions