Algorithmen und Datenstrukturen · Middle · Frage 39 von 75
Welches Problem lösen selbstbalancierende Bäume (AVL, Rot-Schwarz)?
- 1Sie halten die Höhe bei O(log n), also bleibt es schnell
- 2Sie speichern doppelte Schlüssel deutlich kompakter
- 3Sie erlauben jedem Knoten mehr als zwei Kinder
Antwort zeigen
Richtige Antwort: Sie halten die Höhe bei O(log n), also bleibt es schnell
Erklärung
Nach Einfügen und Löschen rotieren sie Knoten, um den Baum ungefähr balanciert zu halten. Geordnete Maps in vielen Sprachen (Java TreeMap, C++ std::map) sind Rot-Schwarz-Bäume.