Theorie Rot-Schwarz-Bäume

[BlackParrot]

Hallo zusammen,
Leider weiß ich nicht, ob ich hier richtig bin - falls nicht: könntet Ihr mir evtl. sagen, wo ich dann am ehesten meine Frage reinstellen könnte?
Und zwar geht es nicht direkt ums Programmieren, sondern um etwas Theoretisches zur Datenstruktur Rot-Schwarz-Bäume. Denn ich bin auf der Suche nach einem binären Suchbaum der Höhe 3 (die nil-Knoten nicht hinzugerechnet), für den es keine Färbung gibt, um ihn nach den Regeln von Rot-Schwarz-Bäumen in eine solchen umzufärben. Dieser binäre Suchbaum soll die hierfür maximal mögliche Anzahl an Knoten besitzen.
Hat jemand eine Idee, wie ein derartiger binärer Suchbaum aussehen könnte?
Vielen Dank - und bitte entschuldigt, falls ich hier mit meiner Frage völlig am falschen Ort bin.
Grüße!

 

[Meniskusschaden]

Ich würde einfach ausrechnen, wie viele Knoten ein Rot-Schwarz-Baum der Höhe drei mindestens haben muß und dann einen binären Baum der Höhe drei zeichnen, der einen Knoten weniger hat. Das müßte doch eigentlich die Lösung sein. Die nötige Formel steht z.B. im Wikipedia-Artikel.

 

[Meniskusschaden]

Ich glaube, mein voriges Posting war zu voreilig. Man könnte so zwar einen Baum finden, der kein RW-Baum ist, aber er hätte nicht zwingend die maximale Knotenzahl.

Es folgen ein paar Beispiele der Höhe drei (jeweils ohne nil-Knoten und ohne Färbung).

Das wäre meines Erachtens ein RW-Baum mit minimaler Knotenzahl:

  O
  |
+-+-+
|   |
O   O
    |
    O

Mit einem Knoten weniger erhält man folgenden Nicht-RW-Baum:

O
|
O
|
O

Aber mit der ursprünglichen Knotenzahl lässt sich auch folgender Baum zeichnen, der jedoch kein RW-Baum sein dürfte:

  O
  |
  O
  |
+-+-+
|   |
O   O