Nachteil(e) von AVL-Bäumen

D.Cent

Guten Abend zusammen

ich mache gerade eine Ausbildung zum Fachinformatiker und habe als Aufgabenstellung einen funktionierenden AVL-Baum in C++ geschrieben. Zum Schluss soll ich folgende Frage beantworten: Welchen Nachteil hat der AVL-Baum?

Nach gründlicher Überlegung bin ich zu dem Schluss gekommen, dass ein AVL-Baum niemals zu 100% optimiert sein kann, da ein vollständig optimierter Baum viel zeitaufwändiger zu programmieren ist (weiteres dazu siehe Wikipedia).

Wie auch immer, man sagte mir, dass das damit nicht gemeint sei - man könne es in Kauf nehmen. Es gebe noch einen weiteren Nachteil bzw. noch eine bessere Methode als den AVL-Baum.

Ich möchte nicht, dass ihr mir die Lösung verratet, aber vielleicht ein kleiner Hinweis, in welche Richtung ich denken muss? Wenn ich heute nicht von selbst darauf komme, kriege ich morgen die Auflösung.

rage_quit

schau dir doch mal auf wiki die unterschiede von Binary/RB/AVL - trees an dann sollte das schon schnell klar werden

sry war da gerade:(

krümelkacker

Nachteil gegenüber was? Für welche Anwendung? Vielleicht guckst Du Dir noch den Rot/Schwarzbaum an und vergleichst damit. Interessante Aspekte für einen Vergleich:

Wie kompliziert ist die Implementierung?
Wie effizient ist das Einfügen? (Wird die Struktur viel umorganisiert?)
Wie effizient ist das Lookup? (Worst-Case Tiefe bzgl Knotenzahl?)

Gruß,
kk

Jester

D.Cent schrieb:

Nach gründlicher Überlegung bin ich zu dem Schluss gekommen, dass ein AVL-Baum niemals zu 100% optimiert sein kann, da ein vollständig optimierter Baum viel zeitaufwändiger zu programmieren ist (weiteres dazu siehe Wikipedia).

Die Aussage verstehe ich nicht. Was ist ein "vollständig optimierter Baum"? Wo steht dazu was bei Wikipedia?

rapso

Jester schrieb:

D.Cent schrieb:

Nach gründlicher Überlegung bin ich zu dem Schluss gekommen, dass ein AVL-Baum niemals zu 100% optimiert sein kann, da ein vollständig optimierter Baum viel zeitaufwändiger zu programmieren ist (weiteres dazu siehe Wikipedia).

Die Aussage verstehe ich nicht. Was ist ein "vollständig optimierter Baum"? Wo steht dazu was bei Wikipedia?

ich glaube damit meint er einen baum der so gut ausbalanziert ist wie nur moeglich.

und afaik trifft das auf AVL zu, sollte eigentlich keine leafs mit einem tiefenunterschied >1 haben.

Eine ziemlich anspruchsvolle FI aufgabe, hab so einige studenten java AVLs gesehen die nicht funzten.

Fedaykin

Prinzipiell sind AVL-Bäume eine sehr optimale Datenstruktur für größere Datenmengen. Der Einzig wirklich nachteil den ich sehe ist das Einfügen: Erfordert halt das umstrukturieren des Baums. Sofern ich mich recht erinnere gabs da aber maximal 2 versionen der Doppelrotation, sollte also alles im Rahmen liegen, nicht desto trotz ist es umkopierarbeit.
Für eine Datenstruktur in der viel Eingefügt aber wenig Gesucht wird ists also denkbar schlecht.

D.Cent schrieb:

Nach gründlicher Überlegung bin ich zu dem Schluss gekommen, dass ein AVL-Baum niemals zu 100% optimiert sein kann, da ein vollständig optimierter Baum viel zeitaufwändiger zu programmieren ist (weiteres dazu siehe Wikipedia).

Ich hoffe ich habe deine Aussage richtig verstanden, aber dem muss ich wiedersprechen. Ein AVL TRee ist immer 100% Optimiert, das ist ja gerade der Sinn der Sache. Nach jeden Einfügen wird geprüft ob der Baum entartet ist, wenn ja wird neu Rotiert. Der Nachteil, ist wie beschrieben, dass bei jeden Einfügen ggf solch eine Rotation erforderlich sein könnte. Diese kostet Zeit.

D.Cent schrieb:

Es gebe noch einen weiteren Nachteil bzw. noch eine bessere Methode als den AVL-Baum

Wirklich weitere Nachteile fallen mir (spontan) nicht ein.
und zum Thema "bessere Methode": Was ist mit besser gemeint? Wenn ich etwas schnelleres als AVL-Tree haben will nehme ich Hashes. Dort ist aber auch der Speicherverbrauch unweigerlich höher. Ich kann normale Binary-Trees nehmen, dort habe ich das Risiko das sie entarten. Wenn der Speicher knapp ist, kann ich sortierte Listen nehmen. Im Allgemeinen kann man sagen: Je schneller du etwas haben willst, umso mehr speicher verbraucht der Algo. Bzw will ich Speicherplatz sparen, brauch ich meist mehr Rechenzeit.

Wäre Nett wenn du heute mal die "Richtige Antwort" auf die Fragen postest.

rapso schrieb:

und afaik trifft das auf AVL zu, sollte eigentlich keine leafs mit einem tiefenunterschied >1 haben.
Eine ziemlich anspruchsvolle FI aufgabe, hab so einige studenten java AVLs gesehen die nicht funzten.

Ich glaube wenn er einen Tiefenunterschie >1 hat, wäre es laut Definition kein AVL Baum mehr.
Ich finde die Aufgabe aber auch nur mittelmäßig Anspruchsvoll, wenn man vorher die Rotationen definiert. Im Grunde hat man damit ja schon den Algo vorliegen und gießt den nur noch in Code. In Studienzeiten mussten wir das in C machen. Man muss nur Testen ob die jeweiligen Rotationen richtig funktionieren. Schwierig wirds erst, wenn man sich die Rotationen noch selber überlegen muss. Dann kommt halt noch der Zeitfaktor hinzu. Wenn man das in 90 min schreiben muss ist das schon sehr Knapp. Für FI's würde ich sowas als Hausaufgabe für ca 1 Woche geben. Da hat man schon genügend Zeit was anständiges zustande zu bringen.

D.Cent

Fedaykin schrieb:

D.Cent schrieb:

Nach gründlicher Überlegung bin ich zu dem Schluss gekommen, dass ein AVL-Baum niemals zu 100% optimiert sein kann, da ein vollständig optimierter Baum viel zeitaufwändiger zu programmieren ist (weiteres dazu siehe Wikipedia).

Ich hoffe ich habe deine Aussage richtig verstanden, aber dem muss ich wiedersprechen. Ein AVL TRee ist immer 100% Optimiert, das ist ja gerade der Sinn der Sache. Nach jeden Einfügen wird geprüft ob der Baum entartet ist, wenn ja wird neu Rotiert. Der Nachteil, ist wie beschrieben, dass bei jeden Einfügen ggf solch eine Rotation erforderlich sein könnte. Diese kostet Zeit.

Damit war eigentlich folgendes gemeint:

Der folgende Baum ist laut AVL-Regel vollkommen ausbalanciert:

8
    /   \
   3     12
  /     / \
 1     9   13
            \
             14

Ein 100%-ig optimierter Baum sieht aber so aus:

9
    /   \
   3      13
  / \     / \
 1   8  12   14

Das geht mit einem AVL-Baum aber nicht!

---

Aber zum Thema...
Die "Lösung" für mein Problem ist folgende: Um bei einem AVL-Baum herauszufinden, in welche Richtung eine Rotation durchgeführt werden muss, muss die Höhe der Teilbäume bestimmt werden. Dafür muss man allerdings durch den gesamten Teilbaum gehen, was bei sehr großen Bäumen sehr ineffizient sein kann. Bei einem rot-schwarz-Baum (Lösung!) ist das aber nicht so, da man sich anhand der Farben der 2 (3?) vorhergehenden Knoten orientieren kann.

Ich hoffe, ich habe das so richtig erklärt
Zum Glück muss ich das jetzt nicht programmieren!

Zeus

Sag mir die Einfügereihenfolge die so ein Baum erzeugt,
http://alfi.ira.uka.de/lehre/sommer2002/AVLTreeApplet/avl.html.

Fedaykin schrieb:

Prinzipiell sind AVL-Bäume eine sehr optimale Datenstruktur für größere Datenmengen.

das totaler quatsch... normalerweise hat jede structur ihre daseinsberechtigung. kommt immer darauf an. im mittel scheint aber rb relativ gut zu sein.

Ben04

D.Cent schrieb:

Aber zum Thema...
Die "Lösung" für mein Problem ist folgende: Um bei einem AVL-Baum herauszufinden, in welche Richtung eine Rotation durchgeführt werden muss, muss die Höhe der Teilbäume bestimmt werden. Dafür muss man allerdings durch den gesamten Teilbaum gehen, was bei sehr großen Bäumen sehr ineffizient sein kann. Bei einem rot-schwarz-Baum (Lösung!) ist das aber nicht so, da man sich anhand der Farben der 2 (3?) vorhergehenden Knoten orientieren kann.

Ich hoffe, ich habe das so richtig erklärt

Nein, das ist nicht notwendig:
http://magazin.c-plusplus.net/artikel/AVL-Baum

Beim Einfügen musst du einmal bis an die Stelle wo der Knoten eingefügt wird laufen und dann wieder einmal hoch. Beim Hochlaufen kann es sein, dass du Rotationen durchführen musst. Diese gehen aber immer in konstanter Zeit.

Jester

Zeus schrieb:

Sag mir die Einfügereihenfolge die so ein Baum erzeugt,
http://alfi.ira.uka.de/lehre/sommer2002/AVLTreeApplet/avl.html.

bei mir geht grad kein java, aber vielleicht kannst dus verifizieren?

8,3,12,1,9,13,14

Zeus

Oh ok, war doch leichter als ich dachte,
ja der Baum ist nicht optimal ausbalanciert.

Jester

Zeus schrieb:

Oh ok, war doch leichter als ich dachte,
ja der Baum ist nicht optimal ausbalanciert.

Kann nicht sogar jeden Baum, der die AVL-Bedingungen erfüllt einfach ohne Auftreten von Rotationen erhalten, indem man die Knoten Layer-weise in beliebiger Reihenfolge einfügt? Müsste eigentlich passen.