أفضل طريقة لبناء شجرة ثنائية مستمرة من دفق مفروز

0

بالنسبة لمشروع جانبي ، كنت أرغب في طريقة بسيطة لإنشاء شجرة بحث ثنائية مستمرة من جدول تم فرزه. بعد بعض عمليات البحث السريع ، لم أتمكن من العثور على أوصاف للتقنيات التي تضمنت تخزين مصفوفة مرتبة حيث يمكنك الوصول إلى أي عنصر حسب الفهرس. انتهى بي الأمر بكتابة شيء ما يعمل ولكنني اكتشفت أن هذه منطقة دربت جيدًا ومن المحتمل أن يتم توثيق مثال أساسي في مكان ما (وربما يكون له اسم).

تم تضمين رمز التحويل الذي صنعته من أجل الوضوح فقط. (إنها أيضًا قصيرة)

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
        )
    }
  }
}

1 إجابة

-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)
  }

سيزور كل قيمة مرتين بالضبط ، مرة واحدة لجمعها ومرة لوضعها في حقل القيمة الخاص بالشجرة.

:مؤلف
فوق
قائمة طعام