Können wir es besser machen als

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 erstellen$O(n\log n)$ 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ät$O(\log n)$.

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. Amortisiert$O(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 $n$ist 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 jeder$2^k$ 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 kann$n$zB für $n = 2^k$, 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ürden$T$ 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 $2^k$ 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 sehen$O(1)$Anhängungszeit für diese Variante beanspruchen. Ich kann sehen, dass Einfügungen oft Kosten verursachen$O(1)$Aber wenn man sich ansieht, was mit den temporären AppendKnoten passiert , scheinen mir die gesamten Einfügungskosten amortisiert zu sein$O(\log n)$.

Wenn dies der Fall ist, ist es nicht überraschend, unseren ausgeglichenen Binärbaum zu erstellen $O(n\log n)$ 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.

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 erstellen$O(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 nur$O(1)$Amortisierte Zeit für Anhänge und Voranmeldungen . Für Einsätze kann nur garantiert werden$O(\log n)$ Zeit.

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.