Können wir es besser machen als

7

Ich bin (dummerweise stellt sich heraus) zuversichtlich, dass die Antwort auf diese Frage nein ist. Warum frage ich?

Weil Dr. Aleksandar Prokopec an der EPFL in seinem parallelen Programmierkurs eine Datenstruktur vorstellt, für die er verschiedene Eigenschaften behauptet. Wenn diese Eigenschaften gelten, scheint es mir möglich zu sein, einen ausgeglichenen Binärbaum besser als zu erstellenO(nlogn) Zeit.

Ich glaube das nicht, also frage ich mich, wo der Fehler in meinem Denken liegt.

Die Datenstruktur ist die Conc-Tree-Liste . In seiner Standardform sieht es aus wie ein normaler Binärbaum und wird mit einer concatOperation geliefert, die die Invariante sicherstellt, dass sich der linke und der rechte Teilbaum eines Knotens niemals um mehr als einen in der Höhe unterscheiden. Wie erwartet concathat KomplexitätO(logn).

Es gibt jedoch eine Builder-Variante der Conc-Tree-Liste, die als AppendListe bezeichnet wird. Diese Variante ermöglicht temporäre Höhenunterschiede in Teilbäumen von mehr als einem. AmortisiertO(1) Für diese Variante werden Zeitanhänge beansprucht.

Es scheint also anhängend zu sein n Elemente müssen eine Komplexität von haben O(n).

Es ist jedoch ein Merkmal dieser Variante, dass wann immer nist eine Zweierpotenz, die zu einem vollständig ausgeglichenen Binärbaum führt (der alle bisher eingefügten Elemente enthält). Während vorübergehende Ungleichgewichte zulässig sind, wird der Baum bei jeder Potenz von 2 Einfügungen ausgeglichen.

In dieser Variante wird eine neue Klasse von Knoten eingeführt, die als AppendKnoten bezeichnet werden. Diese Knoten, deren Teilbäume zulässig sind, unterscheiden sich in der Höhe um mehr als einen. Jedoch jeder2k Einfügungen alle diese temporären Knoten werden eliminiert.

Die Wikipedia-Seite beschreibt den Algorithmus ziemlich prägnant (siehe Beschreibung der grundlegenden Datenstruktur und insbesondere der appendMethode).

Also wann n ist eine Zweierpotenz, die unsere Kosten für das Einfügen von Elementen betragen O(n)und wir haben einen ausgeglichenen Binärbaum erstellt. Zumindest scheint es so.

In einer separaten Frage habe ich effektiv gefragt, ob ich die Anzahl der Schritte für einen Algorithmus für bestimmte Werte von angeben kannnzB für n=2k, wo k ist eine ganze Zahl, reicht dies aus, um die Komplexität für alle Werte von angeben zu können n? "

Ich kann der Antwort von Yuval Filmus entnehmen, dass die Antwort nein ist, aber dass "in vielen Fällen wir erwarten würdenT monoton sein in n. In diesem Fall gilt der Abzug. "

So scheint es mir, dass in diesem Fall beim Einfügen n Elemente hat Komplexität O(n) Und jeder 2k Elemente Ich habe einen ausgeglichenen Binärbaum, dann müssen die Kosten für die Erstellung ausgeglichener Binärbäume mit diesem Ansatz der Conc-Tree-Variante sein O(n).

Also, was ist hier falsch? Um ehrlich zu sein, kann ich die amortisierten nicht sehenO(1)Anhängungszeit für diese Variante beanspruchen. Ich kann sehen, dass Einfügungen oft Kosten verursachenO(1)Aber wenn man sich ansieht, was mit den temporären AppendKnoten passiert , scheinen mir die gesamten Einfügungskosten amortisiert zu seinO(logn).

Wenn dies der Fall ist, ist es nicht überraschend, unseren ausgeglichenen Binärbaum zu erstellen O(nlogn) Kosten.

Entschuldigen Sie die lange Frage und entschuldigen Sie, dass Sie nicht näher auf den betreffenden Algorithmus eingegangen sind. Stattdessen können Sie sich auf Wikipedia umschauen.

George Hawkins
quelle
2
Bitte hören Sie auf, neue Fragen an Ihre Frage anzuhängen. Wenn Ihre ursprüngliche Frage beantwortet wurde, beginnen Sie eine andere Frage mit Anfragen oder Verwirrungen, die nicht direkt mit der ursprünglichen Frage zusammenhängen. Die Frage in ihrem aktuellen Zustand ist völlig vom Titel abgewichen.
Aelguindy
1
Entschuldigung, dass Sie hier im Stil einer laufenden Diskussion angehängt haben, anstatt sich an den Q & A-Stil zu halten. Ich werde diese Frage als beantwortet markieren und versuchen, mein Versäumnis, amortisiert zu werden, als separate Frage zu formulierenO(1)in meiner aktuellen Analyse der appendOperation.
George Hawkins
Die stark erweiterte Version dieser Frage wurde in den Bearbeitungsverlauf übernommen . Während ich viel die Antwort von @ gnasher729 schätzen bin ich ein wenig überrascht es so viele Stimmen hat , da die Frage auf jeden Fall über Binärbäumen und nicht die binäre Suchbäume. Meine Verwechslung der Komplexität des einen mit dem anderen ändert daran nichts. In ähnlicher Weise wurde die Frage von Binärbäumen auf Suchbäume umgestellt, was nicht richtig zu sein scheint.
George Hawkins

Antworten:

7

Wenn ich Ihre Frage richtig verstehe, können Sie natürlich einen ausgeglichenen Binärbaum einbauen O(n)Zeit. Hier ist ein einfacher Pseudocode:

L = [2, 4, 1, 3, 5, 6, 8]
q = Queue()
node root{value = L[0]}
q.add(root)
k = 1
while !q.isEmpty:
  n = q.pop
  if k < L.size:
     n.left = node{value=L[k]}
     k++
     q.add(n.left)
  if k < L.size:
     n.right = node{value=L[k]}
     k++
     q.add(n.right)

Es ist nicht schwer zu erkennen, dass dieser Code in linearer Zeit ausgeführt wird und einen ausgeglichenen Binärbaum erstellt.

Was Sie nicht tun können, ist einen ausgeglichenen binären Suchbaum (geordnet) in zu erstellenO(n)Zeit (nur mit Vergleichen der Werte). Der obige Algorithmus garantiert nicht, dass der Wert in der Wurzel größer oder gleich jedem Wert im linken Teilbaum und kleiner oder gleich jedem Wert im rechten Teilbaum für jeden Teilbaum ist.

Der obige Algorithmus garantiert dies nicht und der Conc-Baum (unter Verwendung von Anhängen und Voranhängen) auch nicht. Von der Wikipedia-Seite garantiert es nurO(1)Amortisierte Zeit für Anhänge und Voranmeldungen . Für Einsätze kann nur garantiert werdenO(logn) Zeit.

aelguindy
quelle
Zum zweiten Mal in so vielen Tagen fühle ich mich ziemlich dumm, hier zuversichtlich etwas zu behaupten, das sich auf der Grundlage von halb erinnerten Vorträgen von vor 20 Jahren als falsch herausstellt. In Ihrem Beispiel erstellen Sie eine etwas andere Art von Baum als den Conc-Baum, bei dem nur Blätter Werte haben, aber dennoch nur die Anzahl der Knoten (Blätter und innere Knoten) erhöht2n1 Die Komplexität bleibt also wie in Ihrem Fall O(n). Jetzt frage ich mich, was an der Conc-Tree- appendOperation klug ist . Ich habe am Ende meiner bereits langen Frage einen weiteren Abschnitt hinzugefügt.
George Hawkins
@ GeorgeHawkins keine Sorge, es ist eine häufige Verwirrung :). Mein Beispiel ist nicht die Knoten auf den Blättern platzieren, legt sie die Werte an allen Knoten des Baumes. Es gibt einige sehr clevere Dinge bei Conc-Bäumen. Der Versuch, eine Datenstruktur zu entwickeln, die die gleichen Grenzen erreicht, sollte Ihnen zeigen, warum sie clever ist. Wenn Sie beispielsweise schnell anhängen möchten, könnten Sie versucht sein, verknüpfte Listen zu verwenden. Wie können Sie dann schnell auf interne Elemente zugreifen?
Aelguindy
Ich habe endlich mein Update zu meiner Frage hinzugefügt. In diesem Stadium interessiert mich jedoch am meisten, was Sie als die Klugheit der Conc-Tree-Datenstruktur bezeichnen. Ich kann sehen, dass Bäume Pluspunkte über Listen haben (wo bestimmte Merkmale erforderlich sind), aber ich bin nicht so klar über Pluspunkte von Conc-Bäumen gegenüber anderen Baumimplementierungen. Gleich am Ende meiner Frage habe ich einige Gedanken in diese Richtung hinzugefügt. Aber genauso wichtig ist, dass ich die Amortisierten immer noch nicht sehen kannO(1) Zeit anhängen :( Meine Analyse, was im Fall von passiert 2k Anhänge führt mich immer noch zu einer falschen Amortisation O(logn).
George Hawkins
2
Ihre Frage wird sehr groß und weicht vom Titel Ihrer Frage ab. Ich denke, Sie möchten vielleicht ein paar separate Fragen stellen.
Aelguindy
2
Versuchen Sie bezüglich der Klugheit des Conc-Baums, einen Baum zu implementieren, der sich mit Anhängen und Voranhängen im Gleichgewicht hält O(1)Amortisierte Zeit und Sie werden sehen, warum Conc-Bäume klug sind. Überlegen Sie sich auch, wie Sie concat für zwei Binärbäume implementieren.
Aelguindy
6

Hinzu kommt die Antwort von aelguindy: Sie können einfach keine n unsortierten Gegenstände in irgendwelche einfügen Datenstruktur und sie dann in sortierter Reihenfolge , besser als O (n log n) Gesamtzeit - denn wenn Sie könnten, könnten Sie sortieren ein Array in einer besseren Zeit als O (n log n).

Wenn wir eine "sortierte" Datenstruktur als eine Datenstruktur definieren, die in sortierter Reihenfolge in O (n) -Zeit aufgelistet werden kann, können wir keine sortierte Datenstruktur schneller als in O (n log n) erstellen. Dazu gehören sortierte Bäume, sowohl ausgeglichen als auch unausgeglichen.

gnasher729
quelle