Ein Median einer AVL. Wie kann ich die AVL nutzen?

8

Hier ist die Quelle meiner Frage.

Codieren Sie bei einem selbstausgleichenden Baum (AVL) eine Methode, die den Median zurückgibt.

(Median: Der numerische Wert, der die obere Hälfte einer Datenprobe von der unteren Hälfte trennt. Beispiel: Wenn die Reihe ist

2, 7, 4, 9, 1, 5, 8, 3, 6

dann ist der Median 5.)

Ich kann folgende Lösung anbieten:

  1. Durchlaufen Sie den angegebenen Baum und geben Sie die Anzahl der Elemente zurück.
  2. Durchqueren Sie den Baum n / 2 + 1(falls nungerade) und führen Sie erneut einen Baumspaziergang in der richtigen Reihenfolge durch. Der Wert des n / 2 + 1th-Elements ist der Median.

Aber ich kann es mit einem binären Suchbaum machen, oder? Gibt es einen besseren Algorithmus für eine AVL?

Maksim Dmitriev
quelle
1
Der Link beantwortet bereits Ihre Frage - was suchen Sie mehr?
Yuval Filmus
Normalerweise funktionieren Suchalgorithmen für einen binären Suchbaum mit einem AVL-Baum. Mit einer AVL erhalten Sie jedoch die zusätzliche Garantie, dass die Höhe Ihres Baums in Bezug auf die Anzahl der Knoten logarithmisch ist.
jmite

Antworten:

9

Wenn Sie den AVL-Baum ändern, indem Sie die Größe des Teilbaums an jedem Knoten und nicht nur seine Höhe speichern, können Sie den Median in der Zeit anhand der Tatsache ermitteln, dass der Baum ausgeglichen ist. Um dies zu erreichen, schreiben Sie eine allgemeinere Prozedur. Wählen Sie aus, die einen Knoten und eine Zahl akzeptiert und den -kleinsten Knoten im Teilbaum findet, der auf verwurzelt ist .v k k vO(logn)vkkv

Angenommen, der linke Teilbaum (falls vorhanden) hat Knoten. Wenn dann kehren wir zum linken Teilbaum zurück. Wenn ist, geben wir . Andernfalls kehren wir zum rechten Teilbaum zurück und reduzieren um .k L k = L + 1 v k L + 1LkLk=L+1vkL+1

Die Laufzeit dieses Algorithmus ist linear in der Höhe des Baums, also .O(logn)

Yuval Filmus
quelle
Könnten Sie mir bitte ein Beispiel geben?
Maksim Dmitriev
Nein, du musst selbst einen bauen. Versuchen Sie zu verstehen, was mein Algorithmus zu erreichen versucht und wie.
Yuval Filmus
Meine Lösung ist auf codereview.stackexchange.com/q/104525/23821
Maksim Dmitriev
0

AVL ist ein binärer Suchbaum mit einer besonderen Eigenschaft: Es ist ein selbstausgleichender Baum. Die Höhe ist immer logarithmisch. Ein gewöhnlicher Binärbaum in einem schlimmsten Szenario kann eine verknüpfte Liste sein (wenn Sie sortierte Daten hinzufügen), sodass die Höhe n beträgt. Der AVL-Baum im schlimmsten Szenario ist der Fibonacci-Baum.

user3371350
quelle