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

Question

У меня есть следующая реализация 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] 

Update

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

Answer 1

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

Классический OOP:

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 не требуется, если вы определили INED 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) 
} 

Answer 2

Полное раскрытие, все еще учусь 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) 

Answer 3

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

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