Frage von Twinna, 8

Wie erkennt man Rot-Schwarz-Bäume als Graphen?

Hallo! Wir nehmen gerade Rot-Schwarz-Bäume in der Informatik durch. Es wird viel erklärt vonwegen wie man einfügt und löscht, aber auf unserem Übungsblatt war dann gefragt welche von den 4 Beispielbäumen man als Rot-Schwarz-Baum einfärben könnte. Gibt es da vielleicht kurze Merkregeln über die man solche grob erkennt?

Danke schonmal!

Antwort
von PWolff, 4

Wenn du dir die entscheidenden Eigenschaften von Rot-Schwarz-Bäumen anschaust und die Reparatur-Operationen im Auge behältst, müssten dies folgende Eigenschaften sein:

- alle Blatt-Knoten müssen Null-Knoten sein
- der längste Weg von Wurzel zu Blatt ist maximal doppelt so lang wie der kürzeste

Keine passende Antwort gefunden?

Fragen Sie die Community

Weitere Fragen mit Antworten