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)

Dankeschön für Deine ausführliche Antwort und die Überarbeitungen! (Gerade finde ich nicht die Zeit, die Änderungen genau durchzugehen) --136.199.8.128 6. Jul 2005 13:24 (CEST)

Umfangreiche Änderungen von 136.199.8.128 am 6.7.05

Ich habe:

• Die Einleitung umgeschrieben und die "Farbe" dort unterschlagen, dafür aber die Höhengarantie O(log n) erwähnt.
• Die Definition sauberer an die der "allgemeinen" binären Suchbäume angeschlossen (was haltet Ihr davon?) und in der Definition die NIL-Blätter eingeführt und die Schwarztiefe leicht korrigiert.
• Die Abbildung zur Definition gesetzt und den eigenen Abschnitt Beispielbaum gelöscht.
• Einen Beweis für die Höhengarantie h ≤ 2 log₂ n geschrieben; ist der korrekt? ist der hier fehl am Platze?
• Die wortreiche Beschreibung der Suchoperation gelöscht und nur auf die allg. binären Suchbäume verwiesen. Das finde ich etwas besser – so wiederholen wir das nicht – hoffe aber, niemanden zu verärgern. Falls das doch der Fall ist ⇒ mach's ruhig rückgängig.

Viele Grüße, --136.199.8.128 6. Jul 2005 18:49 (CEST)

Hi!

Ein paar Anmerkungen von meiner Seite: Prinzipiell finde ich die meisten der Änderungen gut. Ob man die Farbe in der Einleitung unterschlagen sollte? Hm, das ist der einzige Unterschied in der Datenstruktur zu einen normalen Baum... Die Schwarztiefe bedurfte übrigens keiner Korrektur. Es ist egal ob du den aktuellen Knoten mitzählst. Egal welchen Pfad du gehst: Du bekommst auf beiden Pfaden entweder +1 oder -1 je nach dem ob du den aktuellen Knoten mitzählst. Wenn du ihn mitzählst ist die Schwarztiefe halt um eins geringer, aber ändert nichts daran dass der Knoten auf beiden Pfaden "fehlt"

Den Beweis habe ich mir noch nicht genauer angesehen, aber momentan habe ich mit dem Beweis h <= log(n) noch ein paar Bauchschmerzen. Eigentlich kenne ich nur h <= log(n+1). So habe gerade mal ein Gegenbeispiel für deinen Beweis gebaut: Sei ein Baum wie folgt kodiert: (Linker Unterbaum, Wurzel, Rechter Unterbaum), so gilt dein Beweis für den folgenden Baum nicht: ( ( ( (NIL, 3, NIL), 7, NIL), 10, (NIL, 12, NIL)), 14, ( (NIL, 15, NIL), 16, NIL) <- Ich hoffe du kannst den Baum halbwegs nachmalen, falls nicht, schreib' was, dann texe ich ihn schnell. Aber baue einfach mal einen Baum mit einer ungeraden Anzahl von Knoten. Da bekommst du dann die oben genannten Probleme.

Aber wie gesagt: Den Beweis gucke ich mir gleich nochmal genauer an. (Aber auf den ersten Blick sah er gar nicht mal falsch aus)

Ach so, und eine Sache noch: Es gibt durchaus einen RB - Baum mit Höhe 0, nämlich den leeren Baum :) Regnaron 6. Jul 2005 20:23 (CEST)