<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: Times New Roman; font-size: 12pt; color: #000000'>I have some more data to add. I did a quick version of AVL trees so the final data is:<br><br><hr id="zwchr"><blockquote style="border-left:2px solid rgb(16, 16, 255);margin-left:5px;padding-left:5px;color:#000;font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt;"><style>p { margin: 0; }</style><div style="font-family: Times New Roman; font-size: 12pt; color: #000000"><br>Here are the figures. I have also included dict, which is the slowest on insertion/deletion but significantly faster lookup times. All times are in usecs for the whole set:<br><br><pre><pre id="DWT259">Operation Load Fetch Load Fetch<br># of elements 100000 10000<br>Overhead time 43000 3700<br></pre></pre></div></blockquote><pre>avldict AVL trees 430000 150000 31000 14500</pre><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div style="font-family: Times New Roman; font-size: 12pt; color: rgb(0, 0, 0);"><pre id="DWT260"><pre></pre>ttdict 2-3 trees 310000 161000 24000 15500<br>ttfdict 2-3-4 trees 312000 173000 24200 16500<br>llrbdict Left Leaning RB trees 390000 164000 27100 14900<br><br>rbdict Red Black trees 380000 167000 27100 15000<br>aadict AA trees 423000 167000 30000 15000<br><br>gb_trees using faster insert/3 370000 190000 26500 16200<br>dict 522000 107000 28000 11000</pre></div></blockquote>I hope the table is still readable. The loading for AVL trees can be made faster as the algorithm I use is quite naive and probably does too much copying. As Richard C pointed out the RB trees, AA trees and now AVL trees all need an extra field, which the 2-3 and 2-3-4 trees do not. So in terms of space 2-3-4 is better than 2-3 is better than gb_trees is better than other trees. The code size for 2-3-4 trees is bigger than for 2-3 trees, more alternatives to consider. Considering the added code size, though not really complexity, 2-3 trees seems to be a reasonable choice for a tree module with the dict API in terms of speed, code size and data size. Or maybe the Left Leaning RB trees and AVL trees. The fastest trees yet.<br><br>Robert<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div style="font-family: Times New Roman; font-size: 12pt; color: rgb(0, 0, 0);"><pre></pre></div></blockquote></div></body></html>