Das Ergebnis finde ich interessant, weil man, wenn man bei Google nach Empfehlungen für balancierte Bäume sucht, eigentlich immer liest, dass AVL-Bäume bei häufigen Einfüge- und Löschoperationen wegen häufigem Rebalancing nicht so gut geeignet seien, insbesondere im Vergleich zu Rot-Schwarz-Bäumen.
Die AVL-Trees sollten wohl etwas langsamer beim Insert/Remove und dafür etwas schneller beim Locate seien.
Meinen eigenen RB-Tree verwende ich deshalb so gerne, da er ein wenig schneller bei den Masseninserts ist als der AVL-Tree.
Massen-Inserts habe ich immer - Locates und andere Operationen treten oft nicht so gehäuft auf.
Daher denke ich, dass für die Praxis ein RB-Tree oder B-Tree etwas besser als der AVL-Tree sein sollte.
Den AVL-Tree der
FCL zu schlagen ist aber nicht leicht.
Mich wundert es allerdings, dass die Removes hier schneller zu gehen scheinen als die Locates. Vielleicht sollte langsam mal ein repräsentativerer Test her...
Ich teste meine Container einmal mit einer sortierten Liste, und einmal mit einer zufällig zusammengewürfelten Liste.
Die sorted Inserts finde ich recht wichtig, da man damit Masseninserts oft wesentlich beschleunigen kann.
Am Memory-Manager kann man natürlich auch viel herumspielen...
Bei Single-Threaded Sachen hat mir das keinen wirklichen Vorteil gebracht - da poolt der Speichermanager oft selber gut genug.
Sobald aber Multi-Threading ins Spiel gekommen ist, ist bei mir Pooling richtig wichtig geworden.