Dear list members,

I did more research for balanced trees ...
The conclusion, is really that it is not worth changing the data structure for map
and set in the stdlib.

I produced an algorithm balancing more the 234-trees with the following properties (code attached):

Let d be the depth of the tree and n the number of node we have:

in all cases d <= ln(n)/ln(3) + 1 - I think one can produce a better lower bound

for ordered insertion d = ln(n)/ln(4) + 1 - This is completely optimal and means that for 4^d-1
nodes only 4-nodes appear in the tree.

for random insertion, it seems that d = ln(n)/ln(4) + 2 (I did not prove it, but observed it)
- this is almost optimal !

These good results are obtained because rebalancing is done to have that sons of 3-nodes and 4-nodes
are never 2-nodes.

Despite all this the gain again stdlib set is arround 20% for insertion, and depends on the size of
the trees in all cases for searches. The gain is also much smaller with 3.10 on my intel OS X while
I have a more constant gain on 3.09 on my intel linux box.

So, unless the mem functions are not fairly optimized in the case of 234-tree (maybe someone could
check the generated assembly code for set234 and stdlib set) it is not worth the work.

Here are the timings with 3.09 on linux intel ubuntu 7.10:

raffalli@www:~/Caml$ ocamlopt unix.cmxa set234.ml test234tree.ml
raffalli@www:~/Caml$ ./a.out 4095
construction of random tree with 200000 integers less then 10^6
234: 1.08s
bal: 1.29s
234: 1.10s
bal: 1.29s
234: 1.10s
bal: 1.29s
234: 1.11s
bal: 1.29s
search 10^6 times in tree of size 100000
234: 1.78s
bal: 1.87s
234: 1.78s
bal: 1.86s
234: 1.77s
bal: 1.86s
234: 1.78s
bal: 1.86s
search 10^6 times in tree of size 500000
234: 2.43s
bal: 2.72s
234: 2.43s
bal: 2.68s
234: 2.43s
bal: 2.69s
234: 2.42s
bal: 2.68s
search 10^6 times in tree of size 2000000
234: 2.71s
bal: 3.06s
234: 2.71s
bal: 3.05s
234: 2.71s
bal: 3.05s
234: 2.72s
bal: 3.05s
construction of random tree with 200000 integers less then 10^6  (ordered insertion)
234: 0.35s
bal: 0.40s
234: 0.40s
bal: 0.38s
234: 0.33s
bal: 0.38s
234: 0.36s
bal: 0.38s
search 10^6 times in tree of size 100000 (ordered insertion)
234: 1.33s
bal: 1.21s
234: 1.34s
bal: 1.21s
234: 1.34s
bal: 1.21s
234: 1.34s
bal: 1.21s
search 10^6 times in tree of size 500000 (ordered insertion)
234: 1.90s
bal: 1.90s
234: 1.90s
bal: 1.91s
234: 1.90s
bal: 1.91s
234: 1.90s
bal: 1.91s
search 10^6 times in tree of size 2000000 (ordered insertion)
234: 2.81s
bal: 3.29s
234: 2.85s
bal: 3.27s
234: 2.81s
bal: 3.28s
234: 2.81s
bal: 3.26s

Christophe

PS: I should create a page for "boring ocaml code whose writing is advised for meditation" to
store this code ;-)


-- 
Christophe Raffalli
Universite de Savoie
Batiment Le Chablais, bureau 21
73376 Le Bourget-du-Lac Cedex

tel: (33) 4 79 75 81 03
fax: (33) 4 79 75 87 42
mail: Christophe.Raffalli@univ-savoie.fr
www: http://www.lama.univ-savoie.fr/~RAFFALLI
---------------------------------------------
IMPORTANT: this mail is signed using PGP/MIME
At least Enigmail/Mozilla, mutt or evolution
can check this signature. The public key is
stored on www.keyserver.net
---------------------------------------------