Rot-schwarz Bäume vs binäre Heaps
-
Die Komplexität der Operationen bei beiden doch gleich, außer das man bei Heaps auch noch das kleinste Element in O(1) finden kann? Warum verwendet man dann Rot-schwarz-Bäume und keine Heaps?
-
- Komplexität ist nicht alles. In der echten Welt zählen auch die Konstanten (wobei der Heap auch da eher noch im Vorteil ist).
- Heaps und Rot-Schwarz Bäume sind zwei völlig verschiedene Dinge. Ein Heap ist z.B. nicht völlständig sortiert.
-
Ein Rot-schwarz-Baum entartet nicht.
-
-
Dafür kann man in Heaps nicht effizient suchen.
