Finden median in O(1) in den binären Baum

Angenommen ich habe eine ausgewogene BST (binary search tree). Jeder Knoten enthält einen speziellen Bereich count zählt alle Nachkommen des Knotens + der Knoten selbst. Sie nennen diese Datenstruktur order statistics binary tree.

Diese Datenstruktur unterstützt zwei Operationen in O(logN):

  • rank(x) -- Anzahl der Elemente, die kleiner sind als x
  • findByRank(k) -- den Knoten finden, der mit rank == k

Nun möchte ich einen neuen Vorgang hinzufügen median() zu finden, der median. Kann ich davon ausgehen diese operation ist O(1) wenn der Baum ausgeglichen ist?

  • ich denke, der median wäre die Wurzel des Baumes
  • Ich Stimme mit Gir. Aber dies ist nur der Fall, wenn der Baum vollständig ausgeglichen ist.
InformationsquelleAutor Michael | 2012-08-10
  1. 1

    Wenn der Baum vollständig ist (d.h. alle Ebenen vollständig gefüllt ist), kann man sich ja.

    • Was ist, wenn ein Baum ist ausgeglichen, aber nicht complete?
    • man könnte die Zählung verwenden, um zu entscheiden, welche Art zu Reisen. nicht sicher O(1) in diesem Fall ist aber
    • Es hängt von Ihrer definition von ausgewogen, wenn Sie wissen beide Teilbäume der Wurzel hat genau die gleiche Anzahl von Kindern, die Wurzel wird den median.
    • bedeutet, dass die Höhen des linken und rechten Teilbäume jedes Knotens unterscheiden sich nicht um mehr als 1.
    • In diesem Fall glaube ich nicht, dass die Suche nach dem median wird ein O(1) - operation.
    • es ist wohl log(n)
    • Es hängt davon ab, welche Daten Sie zur Verfügung haben, wenn Sie wissen, die Anzahl der Knoten in jedem Unterbaum es ist O(log n), sonst nicht.

    InformationsquelleAutor Andreas Brinck
  2. 2

    Es sei denn, der Baum ist komplett, der mittlere könnte ein Blattknoten. Also im Allgemeinen Fall sind die Kosten O(logN). Ich denke, es ist eine Datenstruktur, die mit den angeforderten Eigenschaften und mit einem O(1) findMedian Betrieb (Vielleicht eine skip-Liste + einen Zeiger auf die median Knoten; ich bin mir nicht sicher über findByRank und Rang operations, obwohl), aber eine ausgewogene BST ist nicht einer von Ihnen.

    • Ja, können wir implementieren eine special - Daten-Struktur zu finden, die den median in O(1), z.B. 2 binäre heaps oder eine skip-Liste wie Sie Sie vorschlagen. Ich Frage mich aber, wenn ich es tun kann mit der augmented ausgewogene BST.
    InformationsquelleAutor Ali Ferhat
  3. 1

    In einem ausgewogenen Ordnung Statistik Baum, der Suche nach dem median in O(log N). Wenn es wichtig ist, zu finden, die den median in O(1) Zeit, können Sie erweitern die Datenstruktur mithilfe eines Zeigers auf den median. Der Haken ist natürlich, dass, würden Sie brauchen, zu aktualisieren, dieser Zeiger bei jedem Insert oder Delete-operation. Die Aktualisierung der Zeiger nehmen würde O(log N) Zeit, aber da diese Vorgänge bereits in O(log N) Zeit, die zusätzliche Arbeit für die Aktualisierung der median Zeiger ändert nicht Ihre big-O Kosten.

    Als eine praktische Sache, das macht nur Sinn, wenn Sie eine Menge von "finden " median" - Operationen im Vergleich zu der Anzahl der Insertionen/Deletionen.

    Wenn gewünscht, Sie könnten die Kosten für die Aktualisierung der median Zeiger beim Einfügen/Löschen O(1) mit einem (doppelt) threaded binary tree, aber Einfügen/Löschen wäre immer noch O(log N).

    InformationsquelleAutor Chris Okasaki
Schreibe einen Kommentar