Ist std :: Auto Balance selbst zuordnen

Question

Ich weiß, dass Mainstream-Implementierungen von STL-Karte/set schwarz-rote Bäume verwenden. Meine Frage ist: Haben diese Implementierungen auch automatisch die Balance beim Einfügen/Löschen von Elementen?

Wenn nicht, dann wenn die Elemente sortiert und eingefügt werden, wird es immer an der äußersten rechten Stelle anhängen. Die schlechtesten Nachschlagekosten sind O (n).

Also, gleicht sich der schwarz-rote Baum automatisch aus?

Answer 1

Werfen Sie einen Blick auf die insert und eraseStd :: Karte Operationen.

Es ist garantiert, dass die schlimmste Komplexität für diese Operationen logarithmisch ist.

In der Tat ist es nicht wichtig, welche Art von Baum verwendet wird, um eine Std :: Karte zu implementieren. Aber dieser Baum muss die notwendige Komplexität für einfügen, Erase und einige andere Operationen bereitstellen. Grundsätzlich bedeutet dies, dass der Baum ausgewogen sein muss (und sich selbst automatisch ausbalanciert, wenn Elemente in oder aus Elementen eingefügt werden).

Das gleiche gilt für eine Std :: Set.

Answer 2

Ja. Rot-schwarze Bäume führen Knotenrotationen durch, um sicherzustellen, dass der Baum ausgeglichen bleibt.

Answer 3

Ja. In Rot-Schwarz-Bäumen werden nach jedem Einfügen einige Elemente im Baum an einen neuen Ort verschoben, wenn der Baum nicht ausgeglichen ist.