Scala: реверсирование хвоста вставки дерева со сложной структурой

Я создаю дерево пользовательских объектов в scala, и мой метод insert вызывает переполнение стека, потому что он не является хвостом рекурсивным. Однако я не могу понять, как сделать хвост рекурсивным. Связанные примеры Я видел использование переменных "аккумулятора", но они либо были такими, как целые, которые можно просто умножать и перезаписывать, или списки, с которыми мне трудно адаптироваться к дереву. Вот что у меня есть:

Основа для моих деревьев:

abstract class GeoTree
case object EmptyTree extends GeoTree
case class Node(elem:GeoNode, left:GeoTree, right:GeoTree) extends GeoTree

Метод insert для рекурсивного создания дерева (метод, вызывающий переполнение стека):

  def insert(t:GeoTree, v: GeoNode): GeoTree = t match {
    case EmptyTree => new Node(v, EmptyTree, EmptyTree)
    case Node(elem:GeoNode, left:GeoTree, right:GeoTree) => {
      if (v < elem) new Node(elem, insert(left, v), right)
      else new Node(elem, left, insert(right, v))
    }
  }

Я не думаю, что код для GeoNode действительно особенно важен, потому что он очень прост. Класс имеет два атрибута Long, а операторы <, > и == переопределяются для использования внутри дерева. Может ли кто-нибудь сделать предложение о том, как использовать аккумулятор для моей функции insert или каким-либо другим способом сделать его хвостом рекурсивным?

Ответы

Ответ 1

Ваша функция не может быть рекурсивной. Причина в том, что ваши рекурсивные вызовы insert не заканчивают вычисление, они используются как подвыражения, в этом случае в new Node(...). Например. если бы вы просто искали нижний элемент, было бы легко сделать его хвостом рекурсивным.

Что происходит:. Когда вы опускаете дерево вниз, вызывая insert на каждом из узлов, но вы должны помнить путь назад к корню, так как вам нужно восстановить дерево после замены нижнего листа новым значением.

Возможное решение: Запомните путь вниз, а не в стеке. Для примера используйте упрощенную структуру данных:

sealed trait Tree;
case object EmptyTree extends Tree;
case class Node(elem: Int, left:Tree, right:Tree) extends Tree;

Теперь определите, что такое путь: это список узлов вместе с информацией, если мы поехали направо или налево. Корень всегда находится в конце списка, лист в начале.

type Path = List[(Node, Boolean)]

Теперь мы можем сделать хвостовую рекурсивную функцию, которая вычисляет путь с заданным значением:

// Find a path down the tree that leads to the leaf where `v` would belong.
private def path(tree: Tree, v: Int): Path = {
  @tailrec
  def loop(t: Tree, p: Path): Path =
    t match {
      case EmptyTree        => p
      case [email protected](w, l, r)  =>
        if (v < w) loop(l, (n, false) :: p)
        else       loop(r, (n, true)  :: p)
    }

  loop(tree, Nil)
}

и функция, которая берет путь и значение и восстанавливает новое дерево со значением как новый node в нижней части пути:

// Given a path reconstruct a new tree with `v` inserted at the bottom
// of the path.
private def rebuild(path: Path, v: Int): Tree = {
  @tailrec
  def loop(p: Path, subtree: Tree): Tree =
    p match {
      case Nil                          => subtree
      case (Node(w, l, r), false) :: q  => loop(q, Node(w, subtree, r))
      case (Node(w, l, r), true)  :: q  => loop(q, Node(w, l, subtree))
    }
  loop(path, Node(v, EmptyTree, EmptyTree))
}

Вставка легко:

def insert(tree: Tree, v: Int): Tree =
  rebuild(path(tree, v), v)

Обратите внимание, что эта версия не особенно эффективна. Вероятно, вы могли бы сделать его более эффективным, используя Seq, или даже больше, используя изменяемый стек для хранения пути. Но при List идея может быть хорошо выражена.

Отказ от ответственности: Я только скомпилировал код, я его вообще не тестировал.

Примечания:

  • Это специальный пример использования молнии для перемещения по функциональному дереву. С застежками-молниями вы можете применять ту же идею на любом дереве и ходить по дереву в разных направлениях.
  • Если вы хотите, чтобы дерево было полезно для больших наборов элементов (что вы, вероятно, делаете, если вы получаете переполнение стека), я настоятельно рекомендую сделать его самоуравновешенной. То есть, обновите структуру дерева так, чтобы она была всегда O (log n). Тогда ваши операции будут быстрыми во всех случаях, вам не придется беспокоиться о переполнении стека, и вы можете использовать свою версию, основанную на стеках, а не на хвостовой рекурсии. Вероятно, самым простым вариантом дерева с балансировкой является дерево .