Rot Scharz Baum von Binärbaum erben

[Laren]

Hi,

Ich soll anhand eines Binärbaumes einen Rot-Schwarz-Baum schreiben.
Jetzt bin ich mir nur nicht so sicher, wie das funktionieren soll.
Ich habe schon eine Klasse Rot-Schwarz-Baum geschrieben, die von einer Klasse Binärtree erbt.
Der Prof hat sich nicht so klar ausgedrückt, wie man die Aufgabe realiesieren soll, er meinte nur, wir haben eine Klasse Bineartree, die wir benutzen sollen.
Der Binärbaum hat einen Comperator, der übergeben Strings richtig im Baum einordnet, es würde aber theoretisch auch mit keys gehen.
Ist dies überhaupt mit Vererbung möglich?

Ps: Es sollen wieder Strings richtig eingeordnet werden

Viele Grüße

 

[SlaterB]

> Ich habe schon eine Klasse Rot-Schwarz-Baum geschrieben, die von einer Klasse Binärtree erbt.
du bist also fertig? perfekt

> Der Binärbaum hat einen Comperator, [..] Ist dies überhaupt mit Vererbung möglich?
bei Suche dürfte sich nicht viel ändern, denke ich (nach bisher nur 5 Min. Nachlesen zu Rot-Schwarz-Baum)

wo immer aber dein Code zur Entscheidung über linken oder rechten Nachfolger bei Einfügen usw. steht, muss diese ja anders sein,
ob in einem Comparator oder sonstwo, Vererbung kann da eine Rolle spielen, ja,
ist jetzt aber extrem allgemein gesprochen, hast du irgendeine konkrete Frage?

 

[Oli]

Nun der Unterschied zwischen einem Binär und einem RS - Baum ist ja, dass der RS-Baum sich ausgleicht. Im Prinzip musst du nur folgende Regeln implementieren:

Jeder Knoten hat einen Wert

Der Wert eines Vaterknotens ist grösser als der Wert seines linken und kleiner als der Wert seines rechten Kinderknotens.

Jeder Knoten ist entweder rot oder schwarz.

Die Wurzel ist immer schwarz.

Jeder Pfad von der Wurzel zu einem Endnoten enthält dieselbe Anzahl von schwarzen Knoten. Dadurch wird garantiert, dass der Baum in Bezug auf die schwarzen Knoten vollständig ausgeglichen ist.

Jeder rote Knoten, welcher nicht ein Endknoten ist, hat nur schwarze Kinderknoten, d.h. es folgen niemals zwei rote Knoten aufeinander. So ist sichergestellt, dass in einem Pfad mit n schwarzen Knoten niemals mehr als n-1 rote Knoten enthalten sind, wodurch sich die Tiefe (Länge) zweier Unterbäume um höchstens n-1 Knoten unterscheidet (-> annähernd ausgeglichen).

Wenn ich die Aufgabenstellung richtig verstehe, dann sollst du die Funktionen insert, update, delete des Binärbaumes nach oben stehenden Regeln überschreiben.

Oder hab ich die Frage falsch verstanden?

 

[muckelzwerg]

Hast Du Dir das hier mal angeschaut?
Rot-Schwarz-Baum ? Wikipedia
Das sieht doch ziemlich gut aus, oder nicht? Wo genau sind die Probleme?

 

[Laren]

mein Problem ist einfach, wenn ich von dem Binärbaum erbe, dann bin ich ja beim Insert (wir sollen nur Insert umsetzen) an den Binärbaum gebunden, da dieser ja beim insert einfach nur prüft, wo der knoten hin soll(rechts oder links). Der Binärbaum hat ja ein festes Konzept, dieses muss ich doch dann durch Methoden des Rot.Schwarz Baumes erweitern. Also muss ich doch die Klasse Binärbaum verändern.

nehmen wir mal an, ich will vom Binärbaum die Mehtode insert erben:

public void insert(Node node)
{
super.insert(node);
//alles was danach kommt ist eh egal, weil der Knoten schon im Binärbaum ist
// viel. noch die Methode changeColor
// aber rotate ist ja unmöglich, oder?
}

Viele Grüße

 

[Michael...]

public class RotSchwarzBaum extends BinaerBaum {
    public void insert(Node node) {
        ...
        // Hier muss die RotSchwarzBaum spezifische Implementierung der insert Methode definiert werden
    }
}

 

[SlaterB]

tja, also super.insert(node); besser nicht aufrufen sondern neu implementieren, oder?
das ist noch innerhalb der Regeln und des Sinns der Vererbung

 

[Laren]

public class RotSchwarzBaum extends BinaerBaum {
    public void insert(Node node) {
        ...
        // Hier muss die RotSchwarzBaum spezifische Implementierung der insert Methode definiert werden
    }
}

Aber ist es nicht so, dass man bei einfügen prüfen muss ob alles an der rechten Stelle steht. Das wäre hier ja nicht mehr gewährleistet.

 

[Crian]

Du musst ja

super.insert()

nicht aufrufen.

Edit: Mmmh man sollte Threads vor dem Antworten nicht so lange offen haben.

 

[Michael...]

Aber ist es nicht so, dass man bei einfügen prüfen muss ob alles an der rechten Stelle steht. Das wäre hier ja nicht mehr gewährleistet.

insert == einfügen. Wo sonst sollte die Prüfung stattfinden als in der Methode insert? Hier nimmst Du das Node Objekt entgegen, prüfst ob es gültig ist und legst fest, wie es in die Struktur eingefügt werden soll.