Enge obere Grenze zum Bilden eines rot-schwarzen Baumes von $ n $

Question

Ich habe das gelernt, dass in einem auftragsstatistischen Baum (Augmented Red-Black Tree, in dem jeder Knoten $ x $ ein zusätzliches Feld enthält, das die Anzahl der Knoten in bezeichnet Der Unterbaum, der in $ x $ ) verwurzelt ist, um den $ I $ th-Bestellstatistiken zu finden $ o (lg (n)) $ Zeit im schlimmsten Fall. Im Falle eines Arrays, das den dynamischen Satz von Elementen darstellt, die den $ I $ , kann in der $ erreicht werden O (n) $ Zeit im schlimmsten Fall. [Wobei $ n $ die Anzahl der Elemente ist].

Jetzt hatte ich das Gefühl, eine enge obere Grenze zu finden, um einen $ n $ Element rot-schwarzer Baum zu bilden, damit ich kommentieren könnte, welche Alternative besser ist: "Beibehaltung Die eingestellten Elemente in einem Array und Führen Sie die Abfrage in $ o (n) $ Time "oder" Aufrechterhalten der Elemente in einem rotschwarzen Baum (deren Bildung aufrechterhalten) Klasse="Math-Container"> $ o (F (n)) $ Time SAY) und dann Abfrage in $ O (LG (N)) $ zeit ".

---

somit ist eine sehr grobe Analyse wie folgt, wobei ein Element in einen $ N $ Element eingesetzt wird Rot-Black Tree, das $ O (lg (n)) $ Uhrzeit und es gibt $ n $ Elemente zum Einfügen, sodass es $ O (nlg (n)) $ Zeit. Nun ist diese Analyse ziemlich locker, als wann nur wenige Elemente im rotschwarzen Baum vorhanden sind. Die Höhe ist ziemlich weniger und ist die Zeit, in den Baum einzufügen.

Ich habe versucht, eine detaillierte Analyse wie folgt zu versuchen (aber fehlgeschlagen):

Während des Versuchs, den $ j= i + 1 $ th-Element einzufügen, ist die Höhe des Baums ganz oben $ 2 .lg (i + 1) +1 $ . Für einen angemessenen $ C $ , die Gesamtlaufzeit,

$$ t (n) \ leq \ sum_ {j= 1} ^ {n} c. (2.lg (i + 1) +1) $$

$$= c. ^ {n-1} ^ {n-1} (2.lg (i + 1) +1) $$ < / p>

$$= c. \ linke [\ sum_ {i= 0} ^ {n-1} 2.lg (i + 1) + \ sum_ {i= 0} ^ {n-1} 1 \ rechts] $$

$$= 2c \ sum_ {i= 0} ^ {n-1} lg (i + 1) + cn \ tag1 $$

jetzt

$$ \ Sum_ {i= 0} ^ {n-1} lg (i + 1)= lg (1) + lg (2) + lg (3) + ... + lg (n)= lg (1.2.3 .... n) \ tag2 $$

jetzt $$ \ prod_ {k= 1} ^ {n} k \ leq n ^ n, \ text {was ist eine sehr lose obere gebundene} \ Tag 3 $$

mit $ (3) $ in $ (2) $ und Ersetzen des Ergebnisses in $ (1) $ Wir haben $ t (n)= o (NLG (N)) $ das ist das wie die grobe Analyse ...

Kann ich etwas Besseres tun als $ (3) $ ?

---

Alle genannten Knoten sind die internen Knoten im rotschwarzen Baum.

Answer 1

Um einen rotschwarzen Baum auf $ N $ -Elements zu erstellen, müssen Sie Zeit verwenden $ \ Omega (N \ log n) $ , wenn Sie nur die Keys der Elemente vergleichen dürfen. Um diese Bekanntmachung zu sehen, besucht ein Besuch eines BST-Besuchs der Knoten in zunehmender Reihenfolge ihrer Schlüssel.

Wenn Sie in der Lage sind, einen rotschwarzen Baum in der Zeit $ t (n)= o (n \ log n) $ zu erstellen konnten, dann wären Sie auch in der Lage, $ N $ Elemente in der Zeit $ o (t (n) + n)= o (n \ log n) ) $ , er widerspricht der unteren Bindung bei der Sortierung für Vergleichsbasierte Algorithmen.

Andererseits, wenn die Elemente bereits sortiert sind, können Sie einen rot-Black-Baum in der Zeit $ o (n) $ erstellen: einfach rekursiv aufbauen Ein ausgewogener BST, wenn die letzte Ebene unvollständig färbt, seine Knoten als rot und jeden anderen Knoten Black färben. Dies erfordert eine lineare Zeit, da die Zeitkomplexität des rekursiven Algorithmus durch die Wiederholungsgleichung $ t (n)= 2t (n / 2) + o (1) $ .