Rot-Schwarz-Baum (RBTree)

[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

[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 ...

[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

[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