Ronaldo Persiano rcmpersiano at gmail.com
Wed Jan 31 05:46:28 EST 2018

```Under my initial hyphotesis that copies are made, an insertion or deletion
from a 2-3 tree with N element would be O(N). And to build a tree from
scratch the time would be O(N^2). It is hard to get good time estimates
with the OpenSCAD system but I got worst than linear time building trees by
insertion of 2500-30000 elements.

To minimize stack overflows I have used the tail recursive versions:

function treeinsert(tree,value)=
(0==len(tree))?
[value]  :
(treeinsertiterate(tree,value))[1] ;

function treeinsertlisti(tr,list,i)=
(i==0)?
treeinsert(tr,list[0]) :
treeinsertlisti(treeinsert(tr,list[i]),list,i-1)  ;

BTW, your insertion code does not deal well with some sequences having
repeated values.

ECHO: foo = [40, 57, 65, 14, 65, 80, 82, 65]

ECHO: bar = [[14, 40], 57, [65], 80, [65]]

2018-01-30 21:59 GMT-02:00 NateTG <nate-openscadforum at pedantic.org>:

> > OpenSCAD uses references to reference-counted, immutable values. Multiple
> variables can point to the same immutable list object. There is no need for
> OpenSCAD to make copies of lists, since there are no operations for
> mutating
> a list. AFAIK; I haven't read all the code in the interpreter.
>
> The 2-3 tree implementation should only replace the nodes on the insertion
> or removal path which should individually take a fixed amount of time.  I
> don't understand how it will take O( N^2 ) time and would really like to
> understand.  (Even if OpenSCAD is copying the lists every time, it seems
> like it should be at worst O(N (log N)^2).)
>
>
>
>
>
>
>
>
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list
> Discuss at lists.openscad.org