title: What is the most efficient way to implement a BST in such a way the find(value) function is optimized for random values in the tree on x86?
body: <p>Suppose we have a binary search tree of depth $n$, where every level is full, we know in advance how big the tree will be, and we will run the find(value) function a lot. The values(integers) we will want to find will be uniformly random across the acceptable values that can be stored in this bst tree. What is the most efficient way to implement a BST, with this characteristic on x86 architectures?</p>
  
  <p>Please, address the question as written. Any answers to the effect of, there are better data structures or ways of performing this task will not be useful for me.</p>
  
  <p>The only idea that comes to mind is to implement the tree as an array and stores the node as follows:</p>
  
  <blockquote>
  <pre><code>     a              n=1
      / \
     b    c           n=2
    / \  / \
   d   e f  g         n=3
  </code></pre>
  </blockquote>
  
  <p>Memory layout for the nodes is linear by level, so level one is first element, then all elements of level two in order from smallest to biggest, and so on for every level.</p>
  
  <blockquote>
    <p>[a,b,c,d,e,f,g]</p>
  </blockquote>
  
  <p>But, I am not sure how to convince myself that is the best, or even if it is the best. Any help would be appreciated.</p>