title: Clear And Efficient 3D Range Tree Implementation
body: <p>I'm working on this project where I have to search for objects in 3d space, and efficiency is a huge concern, I think <strong>Range Tree</strong> is perfect for what I'm trying to do, Interval Tree would also work but I'm not going to delete anything from the tree, once I add every object in 3D space, I'll only use the structure to do a search.</p>
  
  <p>Here's how I'm going to use the structure:</p>
  
  <p>Let say that I have an array(let's call it <strong>queryArr</strong>) of objects (~ 10,000 objects) each objects have 3 parameter (x,y,z) I have another very large array(let's call it <strong>totalArr</strong>) of objects ( > 5,000,000 objects).</p>
  
  <p>What I'm trying to do here is given element of <strong>queryArr</strong>, find the most similar(or the same element in <strong>totalArr</strong>) In some cases there will be an object with the same parameters in <strong>totalArr</strong>, but in most cases, there won't be an object with same parameters. </p>
  
  <p>So, I'll search all the values in between <code>(x+10,y+10,z+10)</code> and <code>(x-10,y-10,z-10)</code>. If it doesn't yield any result, I'll multiply x,y,z by 2 and try again until it yields some results. </p>
  
  <p>The simplest way of doing this is a naive search method, which will have complexity of  <code>O(N*M) (N = size of queryArr, M = sie of totalArr)</code> but this method is incredibly slow and dumb.</p>
  
  <p>I think Range Tree's is the way to go, but I have never implemented one myself and I don't quite understand how the range tree works on dimensions bigger than 2. So does anyone know a good implementation of the range trees? I believe if I can have a source code, I'll be able to understand how they really work.</p>
  
  <p>By the way if you think, there is a better structure than Range Tree for this task, let me know I'm open to suggestions. (I have already considered kd-Trees and Interval trees)</p>
  
  <p>Thanks,</p>