Diskussion:Rot-Schwarz-Baum

Definition unvollständig?

Ist nicht in der Definition außerdem zu forden: Jeder innere Knoten hat zwei Kinder?

Betrachte folgenden Baum:

   K1
  ´  \
     K2                   alle Knoten sind schwarz
    ´  \
        .                 kein Knoten hat ein linkes Kind
         .
          .
           \
           Kn      <---  das einzige Blatt!
         ´  `

Dieser Baum ist ein Binärbaum (gerichteter Graph, genau eine Wurzel, keine Zyklen, max. je zwei Kinder). Mit geeigneten Schlüsseln ist er natürlich auch ein binärer Suchbaum.

Außerdem ist es ein Rot-Schwarz-Baum:

• Jeder Knoten ist entweder rot oder schwarz
• Die Wurzel K₁ des Baums ist schwarz
• Es folgen nie zwei rote Knoten aufeinander
• Die Anzahl der schwarzen Knoten von jedem beliebigen Knoten im Baum zum einzigen Blatt K_n ist auf allen Pfaden gleich (denn es gibt nur je genau einen Pfad)

Die Abbildung im Artikel zeigt zwar, dass außerdem jeder innere Knoten zwei Kinder hat (notfalls ein NIL-Kind), aber wenn wir Rot-Schwarz-Bäume als spezielle binäre Suchbäume beschreiben, sollten wir das explizit fordern (NIL-Kinder kommen bisher bei Graphen, Bäumen oder binären Suchbäumen auch gar nicht vor).

Viele Grüße, --136.199.8.128 4. Jul 2005 09:53 (CEST)

Hi, danke erstmal für den Hinweis. Die Definition ist so wie sie hier steht leider konsistent mit der Literatur. In der Literatur wird das Problem in der Tat meist dadurch gelöst dass jeder Knoten in der Tat zwei Kinder hat, und im Fall dass ein Kind fehlt der Knoten einen schwarzen "Dummy - Knoten" bekommt. Den von dir gemalten Baum gibt es also in der Art nicht direkt. Die Wurzel hätte implizit als linkes Kind einen Schwarzen NIL Knoten, womit es auch einen Pfad zu diesem Knoten (Blatt) gibt, und die Schwarzhöhe somit nicht mehr auf allen Pfaden gleich wäre. Somit haben RB Bäume also keine Blätter die Werte enthalten. Alle Knoten die Werte enthalten sind mehr oder minder innere Knoten und haben auf jeden Fall zwei Nachfolger (im schlimmsten Falle halt zwei NIL Knoten). Nun ist nur noch die Frage wie wir das in den Artikel einbauen. Deine Forderung nach "innere Knoten müssen genau zwei Kinder haben" ist ohne die erwähnung der NIL Knoten jedoch zu stark. [(1,black),(2,red)] wäre ein gültiger RB Baum, kollidiert jedoch mit deiner Definition (wenn man die impliziten Blätter weglässt). Ich wäre dafür dass wir hier irgendwie die NIL Knoten erwähnen. Und in der Tat kommen sie ja in allen Bäumen vor. Sie sind ja nicht sehr viel mehr als der NULL Pointer auf die Kinder bei den Blättern von normalen Bäumen Regnaron 5. Jul 2005 15:44 (CEST)

So, habe mal den Artikel etwas überarbeitet, und mal ein paar Vorlagen für Erweiterungen eingebaut. Ich hoffe das die Definition nun stimmt, und ich die Sache mit den NIL Knoten halbwegs verständlich niedergeschrieben habe. Regnaron 5. Jul 2005 19:32 (CEST)