javascript binary search tree implementation

Question

Anyone know of any good examples of a simple BTree implementation in Javascript? I have a bunch of "things" arriving randomly, and want to insert each one efficiently.

Ultimately, each new one will get inserted into the DOM based on where it ends up in the tree.

I can code this from scratch but would rather not reinvent any wheels.

thanks

Answer 1

If it matters, I found that storing this kind of data as a literal tree was less efficient than storing it as an already-sorted array and doing binary search on the array to splice/insert elements. JavaScript object creation is not free, apparently.

There's also the ol' encode-a-tree-in-an-array trick:

[5, 3, 7, 1, null, 6, 9, null, null, null, null, null, null] 

is the same as

      5
     / \
    3   7
   /   / \
  1   6   9

i.e. children(N[i]) = N[2i+1], N[2i+2] . I don't know if that really gives you any win in JavaScript.

If you try out some alternatives to the binary tree, could you post your findings here? :)