Gibt es für die Herleitung der maximalen Anzahl an roten Knoten in R-S-Bäumen resp. der minimalen Anzahl an Knoten in AVL-Bäumen kluge Ansätze oder muss man es sich durch try and error mühselig selber herleiten?

Also ich habe mir für a) ein paar Bilder von Bäumen gesucht und dann erstmal abgezählt. Habe mir dann eine Wertetabelle für die Anzahl in Abhängigkeit zur Höhe aufgeschrieben und dann einen Zusammenhang zwischen den Zahlen gesucht… und die war dann auf die Bäume übertragen logisch. Nicht ganz einfach, aber ich hab ne Lösung ;)
Hier ist einmal meine Tabelle, falls dir das weiterhilft:

h Anzahl
0 0
1 0
2 2
3 4
4 10
5 20
6 42

Wie ist das eigentlich mit dem Beweis? Reicht eine schifritliche Begründung, warum das so ist oder muss es eine richtige Beweisführung wie z.B. vollständige Induktion sein?

Du hast also deduktives Verfahren angewandt. Es ist bestimmt nicht die elegante Lösung, aber es ist schon was.
Wie kommst du bei Höhe 1 auf 0???? Das müssten doch 2 sein. Die Wurzel ist schwarz und die beiden Blätter, die dadran hängen, sind beide rot.
Hier kannst du es visualisiert überprüfen: http://fbim.fh-regensburg.de/~saj39122/gikasch/applet.html

Guck dir noch mal die Definition eines Rot-Schwarz-Baumes an (Skript, Cormen, Wikipedia, …). U.a. gilt nämlich, dass alle Blätter schwarz sein müssen! (Die Blätter sind aus bestimmten Gründen meistens keine Knoten mit "Inhalt", sondern werden einfach als 'nil' dargestellt. Aus mathematischer Sicht sind das aber ganz normale Knoten des Baumes.)

Frank :)