如何为这个 Btree 实现实现 'find' 方法

Question

所以我正在学习 Scala。这是所有节点和 BTree

的基础 class

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

这里是基本案例类

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
}

他们继续 ThreeNode 和 FourNode

的模式

现在在BTreeclass，我要实现一个查找功能

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

而且我无法全神贯注于我需要做的事情。在 Java 中，我只是做一个循环遍历每个节点或其他任何东西，但 Scala 我不知道。甚至 Some 的事情。 return 只是 Some(v) 吗？不管怎样，这是我能想到的

//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)

我不知道在这些情况下该怎么做：

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

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

条目可能位于树的更下方。

我有类似的情况 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)

但是再一次，如果 v 在树的下方更远，我不知道该怎么办。

   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) =>

我也不确定 Some(v) 在被发现时是否正确。

感谢任何帮助。谢谢

Answer 1

你需要使用递归的find方法，像这样：

  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
    }

此版本 returns Boolean 因为值要么存在，要么不存在。如果想要 return 值所在的节点，那么您需要 return Option[BTree[T]] 并且逻辑变得更加复杂：

  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
    }

对于 4 个节点，这将变得笨拙，因此我建议您使用 List[BTree[T]] 而不是枚举子节点。这将使代码更加清晰。

另请注意，您需要向 OneNode 添加一个 u1 成员，它应该继承自 BTree[T] 而不是 Node[T] 否则您将无法将其添加到其他节点。

如何为这个 Btree 实现实现 'find' 方法

How to implement 'find' method for this Btree implementation

b-tree

scala