performance question

[noemission]

Hello this is more of a question rather than an issue. I understand the theory behind these data structures, but i run a little test in action and i didn't really understand the results. I used a simple array from [0...10000] and the same as btree. I used underscore to give me the min,max and if array contains 9999, so it's the worst situation for array because it will do O(n) for these actions. So benchmarking that, btree is really good 2x faster than underscore functions. But in overall btree is like 10x slower than underscore functions. I believe this has to do with constructing the btree versus constructing a simple array? Is this expected? And if so, what is the point of using structures in javascript?

[mauriciosantos]

Hello,

Please remember that this is a binary tree, but not a self-balancing binary tree. In a self-balancing binary tree, lookup and insertion operations take O(log(n)) time in the worst case. In a normal binary tree these operations take O(log(n)) time on average, but O(n) worst case.

If you add a sequence of already sorted numbers that qualifies as the worst case scenario for the max operation.

For example, adding [1,2,3] in order creates the following tree:

1
 \
  2
    \
      3

To obtain the maximum value you have to traverse the whole tree. So performance is the same as a Linked List.

On the other hand, if you add a sequence of random numbers such as [2,1,3], that creates the following tree:

  2 
 /  \
1   3

In this case the maximum and minimum operations take O(log(n)) time.

[noemission]

Hello! Yes i realized that i was giving a sorted array after i posted this! Even with this sorted array, operations like find min,max or a random value is really good, the performance although is bad when constructing the tree, the add() function is really slow. As you mentioned this is not a balancing binary tree so it doesn't change the root frequently to keep it balanced, so why is it taking so long to build the tree?

ps in your second example you mean 2 / \ 1 3

[mauriciosantos]

Yes, I mean that, sorry. In javascript arrays adding a value is a constant time operation, in trees it's a log(n) operation on average. So constructing an array should take O(n) time and constructing a tree O(nlog(n)) time.