Seite 1 von 1
Rot-Schwarz-Baum (RBTree)
Verfasst: 28.12.2011 18:03
von CSHW89
Hi Leute,
hab mal vor Jahren ne kleine Include geschrieben, mit der man Rot-Schwarz-Bäume benutzen kann. Bin wegen diesem Thema
http://www.purebasic.fr/german/viewtopi ... =3&t=25080 wieder darauf gekommen. Da ich eigentlich gar nicht vorhatte, den Code zu veröffentlichen und ich damals auch nichts von Kommentaren gehalten hab
, ist er halt nicht kommentiert. Hab aber eben mal schnell ne kleine Hilfedatei und ein Beispiel geschrieben, das hoffentlich reicht, um damit zurechtzukommen. Falls nicht einfach Fragen
http://cshw89.mevedia.de/RBTree.zip
lg Kevin
Re: Rot-Schwarz-Baum (RBTree)
Verfasst: 28.12.2011 19:52
von Cardian
Schön das Teil ... aber das ist ein halbes MultiSet ...
(ja jetzt meckert er wieder ^^)
Es fehlen halt zwei Sachen:
1. Iterator.prevEl()
(eine echte Map muß rückwärts durchlaufen können)
Insofern fehlt auch ein Zugriff auf das letzte Element.
2. Wo wird der Wert übergeben? (ich rede nicht vom Key)
Jede Map benötigt Key und Wert.
Baum.insert(Key, Wert). Es ist auch oft so, daß der Key
sich ändern kann (dann müsste er neu einsortiert werden)
(Alternativ geht natürlich suchen-löschen-neuanlegen.)
Ein Ändern des Wertes sollte allerdings jederzeit
problemlos funktionieren.
Bsp:
structPerson enthält Alter, Gehalt, Kinder, ...
insert("Hans Schmidt", @structPerson)
Aber ich schau mir das noch mal später an ...
Re: Rot-Schwarz-Baum (RBTree)
Verfasst: 29.12.2011 00:37
von CSHW89
Zu 1.
Stimmt, das könnt ich noch einbauen, wird auch nicht so schwer sein.
Zu 2.
Ich glaub da verwechselst du was. Ein RBTree ansich speichert einfach nur Werte ab und vergleicht diese, benutzt also keine Key/Wert-Paare (genauso wie der AVL-Baum ja auch, auf den du im anderen Thread verwiesen hast). Ich weiß, dass es z.b. in Java auch eine Klasse TreeMap gibt, die mit Rot-Schwarz-Bäumen arbeitet. Aber da ist ja schon der Name Map drin. RBTree ist einfach nur eine Set.
Allerdings kann man sie dennoch als Map benutzen. Man muss sich halt sowas basteln:
Code: Alles auswählen
Structure Pair
key.s
*value
EndStructure
Procedure NewPair(key.s, *value)
Protected *pair.Pair
*pair = AllocateMemory(SizeOf(Pair))
*pair\key = key
*pair\value = *value
ProcedureReturn *pair
EndProcedure
Procedure ComparePair(*pairA.Pair, *pairB.Pair)
ProcedureReturn CompareMemoryString(@*pairA\key, @*pairB\key)
EndProcedure
Define *this.RBTree
Define *pair.Pair
Define *it.Iterator
*this = NewRBTree(@ComparePair())
*this\insert(NewPair("FR", @"France"))
*this\insert(NewPair("UK", @"United Kingdom"))
*this\insert(NewPair("GE", @"Germany"))
*it = *this\iterator()
While (*it\hasNext())
*pair = *it\nextEl()
Debug *pair\key + ", " + PeekS(*pair\value)
Wend
Die Struktur Pair kannst du natürlich nach deinen Bedürfnissen anpassen. Ist nur wichtig, dass die Funktion 'ComparePair' weiterhin nur die Key's vergleicht. Aber selbst ein anderer Typ für die Key's ist denkbar. Ist halt so viel flexibler.
lg Kevin
Re: Rot-Schwarz-Baum (RBTree)
Verfasst: 29.12.2011 20:29
von CSHW89
Update:
ok, hab 'prevEl' und 'hasPrev' im Iterator drin, und bei RBTree die Funktion 'lastIterator' mit der man direkt zum Ende springen kann.
Außerdem hab ich noch ein 'toArray' eingebaut, damit man eine alternative Möglichkeit hat, auf alle Elemente zuzugreifen.
lg Kevin