Enge obere Grenze zum Bilden eines rot-schwarzen Baumes von $ n $
Frage
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
Jetzt hatte ich das Gefühl, eine enge obere Grenze zu finden, um einen
somit ist eine sehr grobe Analyse wie folgt, wobei ein Element in einen
Ich habe versucht, eine detaillierte Analyse wie folgt zu versuchen (aber fehlgeschlagen):
Während des Versuchs, den
$$ 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
Kann ich etwas Besseres tun als
Alle genannten Knoten sind die internen Knoten im rotschwarzen Baum.
Lösung
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) $ .