Как лучше всего построить постоянное двоичное дерево из отсортированного потока

Question

Для побочного проекта я хотел простой способ создания постоянного дерева двоичного поиска из отсортированного потока. После некоторого беглого поиска мне удалось найти только описания техник, которые включали хранение отсортированного массива, где вы можете получить доступ к любому элементу по индексу. Я закончил тем, что написал кое-что, что работает, но я полагал, что это - проторенная территория, и канонический пример, вероятно, где-то зарегистрирован (и, вероятно, имеет имя).

Код make shift, который я сделал, включен только для ясности. (Это тоже коротко)

object TreeFromStream {
  sealed trait ImmutableTree[T] {
    def height: Int
  }
  case class ImmutableTreeNode[T](
    value: T,
    left: ImmutableTree[T],
    right: ImmutableTree[T]
  ) extends ImmutableTree[T] {
    lazy val height = left.height + 1
  }
  case class NilTree[T]() extends ImmutableTree[T] {
    def height = 0
  }

  @tailrec
  def treeFromStream[T](
    stream: Stream[T],
    tree: ImmutableTree[T] = NilTree[T](),
    ancestors: List[ImmutableTreeNode[T]] = Nil
  ): ImmutableTree[T] = {
    (stream, ancestors) match {
      case (Stream.Empty, _) =>
        ancestors.foldLeft(tree) { case(right, root) => root.copy(right=right) }
      case (_, ancestor :: nextAncestors) if ancestor.left.height == tree.height =>
        treeFromStream(stream, ancestor.copy(right=tree), nextAncestors)
      case (next #:: rest, _) => 
        treeFromStream(
          rest, NilTree(),
          ImmutableTreeNode(next, tree, NilTree()) :: ancestors
        )
    }
  }
}

Answer 1

Чтобы создать сбалансированное дерево, которое, я думаю, вы захотите сделать, вам нужно будет посетить каждый узел хотя бы один раз. Сначала соберите все узлы в буфер, а затем рекурсивно преобразуйте буфер в дерево:

  def tfs[T](stream: Stream[T]): ImmutableTree[T] = {
    val ss = scala.collection.mutable.ArrayBuffer.empty[T]
    def treeFromSubsequence(start: Int, end: Int): ImmutableTree[T] =
      if (end == start) NilTree()
      else if (end - start == 1) ImmutableTreeNode(ss(start), NilTree(), NilTree())
      else {
        val mid = (end - start) / 2
        ImmutableTreeNode(ss(mid), treeFromSubsequence(start, mid), treeFromSubsequence(mid + 1, end))
      }
    stream.foreach { x => ss += x }
    treeFromSubsequence(0, ss.length)
  }

Он будет посещать каждое значение ровно дважды, один раз, чтобы собрать его, и один раз, чтобы поместить его в поле значений дерева.