Максимальный элемент в дереве

У меня есть следующая реализация ADT в Scala.

Как найти максимальный элемент в дереве? Могу ли я ввести некоторую вспомогательную функцию, и если да, то как?

abstract class MySet {
  def max: Int

  def contains(tweet: Tweet): Boolean = false
}

class Empty extends MySet {
  def max: throw new NoSuchElementExeption("max called on empty tree")

  def contains(x: Int): Boolean =
    if (x < elem) left.contains(x)
    else if (elem < x) right.contains(x)
    else true
}

class Node(elem: Int, left: MySet, right: MySet) extends Set {
  def max: { ... }

  def contains(x: Int): Boolean =
    if (x < elem) left.contains(x)
    else if (elem < x) right.contains(x)
    else true
}

Я нашел решение в Haskell, которое кажется довольно интуитивным, могу ли я как-то преобразовать его в Scala?

data Tree a = Nil | Node a (Tree a) (Tree a)
maxElement Nil = error "maxElement called on empty tree"
maxElement (Node x Nil Nil) = x
maxElement (Node x Nil r) = max x (maxElement r)
maxElement (Node x l Nil) = max x (maxElement l)
maxElement (Node x l r) = maximum [x, maxElement l, maxElement r]

Обновить

Я не заинтересован в копировании кода на Haskell в Scala, а думаю, что версия на Haskell более интуитивна, но из-за this Ключевое слово и другие вещи в объектно-ориентированном языке. Как я могу написать эквивалентный код в объектно-ориентированном стиле без сопоставления с образцом?

Источник

3 ответа

Решение

Ваше дерево неоднородно, что означает, что каждый узел может быть либо полным узлом со значением, либо пустым листом. Следовательно, вам нужно различать, что есть что, в противном случае вы можете позвонить max на пустом узле. Есть много способов:

Классический ООП:

abstract class MySet {
  def isEmpty: Boolean
  ...
}

class Empty extends MySet {
  def isEmpty = true
  ...
}

class Node(...) extends MySet {
  def isEmpty = false
  ...
}

Итак, вы делаете что-то вроде этого:

var maxElem = elem
if(!left.isEmpty)
  maxElem = maxElem.max(left.max)
end
if(!right.isEmpty)
  maxElem = maxElem.max(right.max)
end

Поскольку JVM имеет информацию о классе во время выполнения, вы можете пропустить определение isEmpty:

var maxElem = elem
if(left.isInstanceOf[Node])
  maxElem = maxElem.max(left.asInstanceOf[Node].max)
end
if(left.isInstanceOf[Node])
  maxElem = maxElem.max(right.asInstanceOf[Node].max)
end

(asInstanceOf не требуется, если вы определили max в MySet, но этот шаблон охватывает тот случай, когда вы этого не сделали)

Ну, у Scala есть синтаксический сахар для последнего, и неудивительно, что это сопоставление с образцом:

var maxElem = elem
left match {
  case node: Node =>
    maxElem = maxElem.max(node.max)
  case _ =>
}
right match {
  case node: Node =>
    maxElem = maxElem.max(node.max)
  case _ =>
}
maxElem

Вы можете пойти дальше и написать что-то вроде этого:

def max = (left, right) match {
  case (_: Empty, _: Empty) => elem
  case (_: Empty, node: Node)  => elem.max(node.max)
  case (node: Node, _: Empty)  => elem.max(node.max)
  case (leftNode: Node, rightNode: Node)  =>
    elem.max(leftNode.max).max(rightNode.max)
}
Источник

Полное раскрытие, я все еще изучаю Scala, но вот две версии, которые я придумал (сопоставление с шаблоном похоже на честный перевод кода на Haskell)

sealed trait Tree {
  def max: Int
  def maxMatch: Int
}
case object EmptyTree extends Tree {
  def max = 0
  def maxMatch = 0
}
case class Node(data:Int,
                left:Tree = EmptyTree,
                right:Tree = EmptyTree) extends Tree {

  def max:Int = {
    data
      .max(left.max)
      .max(right.max)
  }

  def maxMatch: Int = {
    this match {
      case Node(x,EmptyTree,EmptyTree) => x
      case Node(x,l:Node,EmptyTree) => x max l.maxMatch
      case Node(x,EmptyTree,r:Node) => x max r.maxMatch
      case Node(x,l:Node,r:Node) => x max (l.maxMatch max r.maxMatch)
    }
  }
}

Тесты (все прохождение)

val simpleNode = Node(3)
assert(simpleNode.max == 3)
assert(simpleNode.maxMatch == 3)

val leftLeaf = Node(1, Node(5))
assert(leftLeaf.max == 5)
assert(leftLeaf.maxMatch == 5)


val leftLeafMaxRoot = Node(5, 
                        EmptyTree, Node(2))
assert(leftLeafMaxRoot.max == 5)
assert(leftLeafMaxRoot.maxMatch == 5)

val nestedRightTree = Node(1, 
                         EmptyTree, 
                         Node(2, 
                             EmptyTree, Node(3)))
assert(nestedRightTree.max == 3)
assert(nestedRightTree.maxMatch == 3)

val partialFullTree = Node(1, 
                         Node(2, 
                             Node(4)),
                         Node(3, 
                              Node(6, Node(7))))
assert(partialFullTree.max == 7)
assert(partialFullTree.maxMatch == 7)
Источник

Если вы не хотите использовать сопоставление с образцом, вам необходимо реализовать isEmpty операция или ее эквивалент, чтобы избежать вызова max на пустом множестве.

Важно то, как организовано дерево. На основании реализации contains, похоже, у вас есть упорядоченное дерево ("дерево двоичного поиска"), где каждый элемент в левой части меньше или равен каждому элементу в правой части. Если это так, ваша проблема довольно проста. Либо правое поддерево пусто, а текущий элемент является максимумом, либо элемент максимума дерева является максимумом правого поддерева. Это должна быть простая рекурсивная реализация, не требующая ничего особенного.

Источник
Другие вопросы по тегам