Scala中TweetSet的contains方法何时/为何在空叶子节点返回false？

给定如下Scala代码，TweetSet以二叉搜索树形式存储Tweet对象，NonEmpty类的contains方法通过递归实现元素查找。请问该contains方法在遍历至空叶子节点时，何时以及为何会返回false？

/**
 * A class to represent tweets.
 */
class Tweet(val user: String, val text: String, val retweets: Int):
  override def toString: String =
    "User: " + user + "\n" +
    "Text: " + text + " [" + retweets + "]"

/** This represents a set of objects of type `Tweet` in the form of a binary search
 * tree. Every branch in the tree has two children (two `TweetSet`s). There is an
 * invariant which always holds: for every branch `b`, all elements in the left
 * subtree are smaller than the tweet at `b`. The elements in the right subtree are
 * larger. 
*/

abstract class TweetSet extends TweetSetInterface:
  /**
   * Tests if `tweet` exists in this `TweetSet`.
   */
  def contains(tweet: Tweet): Boolean


class NonEmpty(elem: Tweet, left: TweetSet, right: TweetSet) extends TweetSet:

  def filterAcc(p: Tweet => Boolean, acc: TweetSet): TweetSet = ???


  /**
   * The following methods are already implemented
   */

  def contains(x: Tweet): Boolean =
    if x.text < elem.text then
      left.contains(x)
    else if elem.text < x.text then
      right.contains(x)
    else true

问题解答 #

首先要明确：这段代码里没有写出二叉搜索树的空节点实现，但根据TweetSet的抽象设计，必然存在一个Empty类（继承自TweetSet），它的contains方法会直接返回false——这是遍历到空叶子节点时返回false的核心基础。

何时会触发返回false的场景？ #

当你要查找的Tweet对象，其text字段在二叉搜索树的递归遍历路径中始终找不到匹配项，最终走到了树的末端（空叶子节点）：

• 如果目标Tweet的text小于当前NonEmpty节点的elem.text，程序会递归查询左子树；若左子树是Empty节点，就会调用Empty的contains方法返回false
• 如果目标Tweet的text大于当前NonEmpty节点的elem.text，程序会递归查询右子树；若右子树是Empty节点，同样返回false

为什么空叶子节点要返回false？ #

Empty节点代表二叉搜索树的这个分支没有任何Tweet元素，既然该位置不存在任何内容，自然不可能包含我们要查找的目标Tweet，返回false完全符合集合“元素不存在”的语义。

内容的提问来源于stack exchange，提问作者user17118231