Dies ist eine statische Kopie unseres alten Forums. Es sind keine Interaktionen möglich.
This is a static copy of our old forum. Interactions are not possible.

Feuertaenzer

Trainee

  • "Feuertaenzer" started this thread

Posts: 61

Date of registration: Oct 4th 2003

1

Monday, April 5th 2004, 11:41pm

AVL-Bäume vs. Rot-/Schwarz- Bäume

Ich habe schon vor längerer Zeit für ein paar eigene Programme eine Baumstruktur gebraucht und mich damals dafür entschieden einen Rot-/Schwarz- Baum zu implementieren.
Nun nach der Vorlesung D&A frage ich mich, was eben diesen von AVL-Bäumen unterscheidet. Beides sind höhenbalancierte Bäume. Mein Eindruck ist, das AVL-Bäume ein wenig besser ausbalanciert werden. Aber ich weiß nichts über Laufzeitverhalten bei Einfügen, Suche....

Wenn sich hier einer damit auskennt, wäre es schön, wenn er mir auf die Sprünge helfen könnte.

Feuertaenzer.
  • Send private message

Joachim

Guru

  • "Joachim" is male

Posts: 2,863

Date of registration: Dec 11th 2001

Location: Hämelerwald

Occupation: Wissenschaftlicher Mitarbeiter (Forschungszentrum L3S, TU Braunschweig)

2

Tuesday, April 6th 2004, 12:07am

RE: AVL-Bäume vs. Rot-/Schwarz- Bäume

Quoted

Original von Feuertaenzer
Ich habe schon vor längerer Zeit für ein paar eigene Programme eine Baumstruktur gebraucht und mich damals dafür entschieden einen Rot-/Schwarz- Baum zu implementieren.
Nun nach der Vorlesung D&A frage ich mich, was eben diesen von AVL-Bäumen unterscheidet. Beides sind höhenbalancierte Bäume. Mein Eindruck ist, das AVL-Bäume ein wenig besser ausbalanciert werden. Aber ich weiß nichts über Laufzeitverhalten bei Einfügen, Suche....
Größenordnungsmäßig liegen beide Datenstrukturen beim Einfügen, Suchen und Löschen gleichauf (jeweils O(log n), wobei n die Anzahl der Elemente ist).

Unterschiede in der Performance sind also auf der Ebene konkreter Implementierungen und Anforderungen zu suchen.

Noch ein paar Links:
http://groups.google.com/groups?threadm=…ews.csrlink.net
http://groups.google.com/groups?threadm=….dial.pipex.com
http://discuss.fogcreek.com/joelonsoftwa…ow&ixPost=22948
The purpose of computing is insight, not numbers.
– Richard Hamming, 1962
  • Send private message