title: AVL Trees: How to do index access?
body: <p>I noticed on the <a href="http://en.wikipedia.org/wiki/AVL_tree" rel="nofollow noreferrer">AVL Tree Wikipedia page</a> the following comment:</p>
  
  <p>"If each node additionally records the size of its subtree (including itself and its descendants), then the nodes can be retrieved by index in O(log n) time as well."</p>
  
  <p>I've googled and have found a few places mentioning <a href="http://www.gap-system.org/Manuals/pkg/orb/doc/chap8.html" rel="nofollow noreferrer">accessing by index</a> but can't seem to find an explanation of the algorithm one would write. </p>
  
  <p>Many thanks</p>
  
  <p>[UPDATE] Thanks people. If found @templatetypedef answer combined with one of @user448810 <a href="http://programmingpraxis.com/2011/11/29/avl-trees-extended/2/" rel="nofollow noreferrer">links</a> to particularly help. Especially this snipit:</p>
  
  <p>"The key to both these functions is that the index of a node is the size of its left child. As long as we are descending a tree via its left child, we just take the index of the node. But when we have to move down the tree via its right child, we have to adjust the size to include the half of the tree that we have excluded."</p>
  
  <p>Because my implementation is immutable I didn't need to do any additional work when rebalancing as each node calculates it's size on construction (same as the scheme impl linked)</p>
  
  <p>My final implementation ended up being:</p>
  
  <pre class="lang-java prettyprint-override"><code>class Node&lt;K,V&gt; implements AVLTree&lt;K,V&gt; { ...
      public V index(int i) {
          if (left.size() == i) return value;
          if (i &lt; left.size()) return left.index(i);
          return right.index(i - left.size() - 1);
      }
  }
  
  class Empty&lt;K,V&gt; implements AVLTree&lt;K,V&gt; { ...
      public V index(int i) { throw new IndexOutOfBoundsException();}
  }
  </code></pre>
  
  <p>Which is slightly different from the other implementations, let me know if you think I have a bug!</p>