Genau wie Multiset ist eine binäre Search Tree-Implementierung in STL, gibt es eine RB-Baum oder AVL-Tree-Implementierung verfügbar?Gibt es eine rot-schwarze Baum- oder Avl-Tree-Implementierung in der C++ - Standardbibliothek?
Normalerweise würden Sie keinen multiset als Binärbaum implementieren. Die Verwendung eines würde die Leistungsgarantien des Standards brechen, da der Baum wie eine verkettete Liste aussehen könnte, die kein Einfügen und Entfernen von O (logN) aufweist.
std::set/std::multiset/std::map/std::multimap werden als RB Baum Typischerweise implementiert, wie es diese Leistungsgarantien hat. Dies ist jedoch nicht erforderlich. Der Standard garantiert nur die Leistung des Containers in verschiedenen Operationen und es ist die Umsetzung, wie dies zu erreichen ist.
Wenn Sie sicherstellen möchten, dass Sie einen RB-Baum verwenden, müssen Sie entweder Ihre Implementierung überprüfen, Ihre eigenen rollen oder eine Bibliothek eines Drittanbieters erhalten, die garantiert, dass es sich um einen RB-Baum handelt.
Vielen Dank. :) – ash
Ein rot-schwarzer Baum ist ein binärer Baum. Ein ausgewogener Binärbaum. –
std :: map ist ein rot/schwarzer Baum. Der Standard sagt nicht, dass es eins sein muss, aber die Leistungsgarantien machen es unwahrscheinlich, dass etwas anderes verwendet wird. –
Ziemlich sicher, dass die meisten Standard-Bibliothek Implementierungen RB-Bäume für alle vier (multi-) Set | map verwenden. Der Standard spezifiziert jedoch nicht die Implementierung. – Zulan