Rot-Schwarz-Baum:Schwarzhöhe/Schwarztiefe

barakneldur

Hallo liebe Community,

ich sitze gerade an der Implementierung eines Rotschwarzbaumes. Dazu möchte ich eine Funktion schreiben, die überprüfen soll ob die Schwarzhöhe gegeben ist.

"Jeder Pfad von einem gegebenen Knoten zu seinen Blattknoten enthält die gleiche Anzahl schwarzer Knoten (Schwarzhöhe/Schwarztiefe)." (siehe: http://de.wikipedia.org/wiki/Rot-Schwarz-Baum )

Hat jemand eine Idee wie das Ganze pseudocodetechnisch aussehen könnte?

Aufgebaut ist mein Rotschwarzbaum über eine Knotenklasse mit 3 Zeigern(parent,child_left,child_right) und der Baumklasse(enthält Wurzelknotenzeiger) selber!

SeppJ

Erst einmal vorweg: Du bist dir im klaren, dass du diese Funktion für die Implementierung nicht benötigst?

Algorithmus:

Funktion Schwarzzähler: 
Nimmt Knoten, gibt zurück die Anzahl schwarzer Knoten vom Knoten bis zu den Blättern
{
 - Falls Knoten ein Blatt ist: 1 zurück geben
 - Falls Knoten schwarz ist: Zähler = 1, sonst Zähler gleich Null
 - linker_zähler = Schwarzzähler(linkes Kind)
 - rechter_zähler = Schwarzzähler(rechtes Kind)
 - Falls rechter_zähler ungleich linker_zähler -> Exception! Schwarztiefe verletzt
 - Gib zurück Zähler + linker_zähler
}

Funktion teste_Schwarztiefe
Nimmt Wurzel, gibt ja oder nein zurück
{
 -Versuche Schwarzzähler(Wurzel)
 - Falls Exception gibt Nein zurück
 - sonst gib Ja zurück
}

Hoffentlich richtig. Das habe ich mir gerade so aus den Fingern gesogen, überprüf es besser noch einmal.

barakneldur

super schon mal vielen Dank!

Ich frage mich grad nur warum du den Zähler gleich 0 setzt bzw. gleich 1.
Musst du nicht um 1 erhöhen?

Habe es verstanden