title: Implementing an AVL tree using a List
body: <p>So I have implemented an Binary search tree using a parameterized List i.e. </p>
  
  <pre><code>List&lt;Node&gt; tree = new List&lt;&gt;();
  </code></pre>
  
  <p>The tree works fine. The node itself doesn't know anything about its parent or children. This is because I calculate the locations based on the index e.g.</p>
  
  <pre><code>                         If i is the index of some None N then:
                                  N's left child is in tree[i*2] 
                                  N's right child is in tree[(i*2)+1]
  </code></pre>
  
  <p>This binary tree works fine. But now I want to put AVL tree features to it. Im am stuck at this point because I do not know how to make the rotations on a List. On rotation, how do i move the children of the new root? Fact is they have to shift indexes don't they? Also doing this on an List gives me the problem that displaying the tree will require looping through the List everytime i add a node. THis wont happen in O(logn) anymore destroying the whole point of an AVL tree. </p>
  
  <p>I am doing this in C#. I just want to know how to make this AVL tree efficiently using a List or any array based data structure thats indexable and not a Linked list. This is important.Some code to illustrate would be greatly appreciated.</p>