Vergleich von Suchverfahren mit Beispielen

[acadam71]

Mein Test: der AVL Baum benötigt im Testprogramm bei 100.000 Inserts bereits 1 Sekunde. Mein Laptop: Duo Centrino mit 2 GHz.

Ich habe einen AVL Baum selbst programmiert, der schafft in 1 Sekunde aber fas 1 Mio Inserts. Wie kann das sein? Er hat weit weniger Quellcode (357 Zeilen) und benutzt keinen Assembler. Und trotzdem ist er 10 mal so schnell, und das obwohl ich sogar GUIDS (Jeweils 40 Zeichen) einfüge anstatt wie im Testprogramm Integer Werte. Offensichtlich ist der dort benutzte Quellcode nicht gerade optimal, so dass ich davon ausgehe, dass der AVL Baum die beste Datenstruktur ist. Abgesehen davon macht er alle Funktionen wie Insert, Delete, Update und Select(suche) in O(log(n)) und zwar im WORST CASE! So weit mir die Theorie vertraut ist, schafft das keine der anderen Strukturen.

Edit: Mein Quellcode für den AVL ist von Niklaus Wirth, aber auf Objekte angepasst (anstatt Zeiger).