Hey. Sind RB-Bäume eigentlich gerichtete Graphen oder nicht? Analog Suchbäume und Heaps?

Ich weiss, es sind keine Pfeile dran, aber man könnte sie ja hirarchisch von oben nach unten lesen(müssen) o.Ä. . Kann mir da einer weiterhelfen?

Hey,

wenn du einen Baum mit (fester) Wurzel hast, dann kannst du dir das immer als
gerichteten Graphen vorstellen, da die Knoten dann einen eindeutigen Abstand
von dieser Wurzel haben. Nur so kannst du ja z.B. Höhe/Tiefe etc. bei einem Baum
überhaupt definieren.

Bei den von dir angesprochenen Bäumen (Suchbäume, RS-Bäume (spezielle Such-
bäume), Heaps, …) hast du stets eine Wurzel gegeben und kannst dann vom linken
und rechten Kind dieser Wurzel reden (und diese Knoten haben dann selbst wieder
Kinder) und du "musst" die Kanten dann auch von oben nach unten lesen (oder auch
immer andersherum, aber halt *immer*), da in all diesen Bäumen ja bestimmte
Bedingung an die einzelnen Knoten gestellt werden. Bei einem Suchbaum sind z.B.
alle Knoten im linken Teilbaum eines Knotens kleiner und alle Knoten im rechten
Teilbaum grösser (oder gleich) des betrachteten Knotens. Bei RS-Bäume ebenso
(ferner gibt's da noch Regeln für die Färbung) und bei (Max-)Heaps ist ein Knoten
immer grösser (oder gleich) als alle seine Kinder (also Kinder und Kindes-Kinder usw.).

Beantwortet das die Frage oder hattest du was anderes gemeint?

Frank :)

Hallo. Danke für deine Antwort, diese Überlegungen habe ich mir auch gemacht. Allerdings wird aus deiner Beschreibung auch nicht klar, ob man diese Bäume als gerichtet ansehen muss oder:

dann kannst du dir das immer als

Es geht mir genauer um die Adjazenzmatrix, die ja je nachdem komplett anders aussehen würde. :/

*Ob man es muss oder kann sollte das heissen, Fettgedrucktes ist irgendwie nicht erschienen.

Naja, so komplett ja nun auch wieder nicht. Entweder stehen da Nullen oder redundante Informationen. Ist das für irgendeinen Algorithmus wichtig? Ansonsten würde ich mir da keine so grossen Gedanken machen.

Ganz klar: Jein Implementationssache
Die Frage, ob ein Graph gerichtet ist, hängt ganz stark mit dem betrachteten Problem zusammen.
Entweder, Du willst/brauchst diese Eigenschaft für Dein untersuchtes Problem, oder nicht.

Wikipedia sagt:

Eine gerichtete Kante verbindet zwei Knoten eines Graphen unter Beachtung einer Reihenfolge. Eine gerichtete Kante wird daher als geordnetes Paar (a,b) zweier Knoten a und b notiert.

In RB-Bäumen ist es sinnvoll anzunehmen, dass man gerichtete Kanten hat, aus folgendem Grund:

• Man weiß bei jeder Kante, die man nutzt, ob man sich der Wurzel nähert oder sich entfernt.

Notiert man die Kanten allerdings in beliebiger Reihenfolge, so gehen nützliche Informationen verloren. Deswegen würde ich einen RB-Baum als gerichteten Graph implementieren.