title: Data Structure for fast insertion and random access in already sorted data
body: <pre><code>p = random_point(a,b)
  #random_point() returns a tuple/named-tuple (x,y)
  #0&lt;x&lt;a 0&lt;y&lt;b
  if centers.validates(p):
      centers.insert(p)
  #centers is the data structure to store points
  </code></pre>
  
  <p>In the <code>centers</code> data structure all <code>x</code> and <code>y</code> coordinates are stored in two separate sorted(ascending) lists, one for <code>x</code> and other for <code>y</code>. Each node in <code>x</code> points to the corresponding <code>y</code>, and vice versa, so that they can be separately sorted and still hold the pair property: <code>centers.get_x_of(y)</code> and <code>centers.get_y_of(x)</code></p>
  
  <p><a href="https://i.stack.imgur.com/DTubP.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/DTubP.png" alt="enter image description here"></a></p>
  
  <p>Properties that I require in data structure:</p>
  
  <ol>
  <li>Fast Insertion, in already sorted data (preferably log n)</li>
  <li>Random access</li>
  <li>Sort x and y separately, without losing pair property</li>
  </ol>
  
  <p>Initially I thought of using simple <code>Lists</code>, and using <code>Binary search</code> to get the index for inserting any new element. But I found, that, it can be improved using self balancing trees like AVL or B-trees. I could make two trees each for <code>x</code> and <code>y</code>, with each node having an additional pointer that could point from x-tree node to y-tree node.</p>
  
  <p>But I don't know how to build random access functionality in these trees. The function <code>centers.validate()</code> tries to insert <code>x</code> &amp; <code>y</code>, and runs some checks with the neighboring elements, which requires random access:</p>
  
  <pre><code>def validate(p):
      indices = get_index(p)
      #returns a named tuple of indices to insert x and y, Eg: (3,7)
      condition1 =  func(x_list[indices.x-1], p.x) and func(x_list[indices.x+1], p.x)
      condition2 =  func(y_list[indices.y-1], p.y) and func(y_list[indices.y+1], p.y)
      #func is some mathematical condition on neighboring elements of x and y
      return condition1 and condition2
  </code></pre>
  
  <p>In the above function I need to access neighboring elements of <code>x</code> &amp; <code>y</code>
   data structure. I think implementing this in trees would complicate it. Are there any combination of data structure that can achieve this? I am writing this in Python(if that can help)</p>