Warp wrote:
>   I'd say it's the exact opposite: When you start having more than 2^16
> nodes, that's when you need to star worrying about the amount of space the
> data structure is taking. With less than 2^16 nodes the size of an individual
> node is rather irrelevant.

My thought was that if you have that much data, you're probably running on a 
machine where the memory limits aren't very tight (i.e., a desktop system, 
say).  Of course, the killer is the ratio of the number of nodes to the 
amount of memory, so sure, when you start getting up in the 2^25 number of 
nodes range the size of the nodes is going to be prohibitive on a 32-bit 
machine again.

The nice thing is the tree doesn't need rotations, so you can clip off a 
large sub-tree of the tree and put it in its own address space. That's hard 
to do if you have to balance nodes and stuff.

-- 
   Darren New, San Diego CA, USA (PST)
   Insanity is a small city on the western
   border of the State of Mind.

Post a reply to this message