title: How to generate maximally unbalanced AVL trees
body: <p>I have written a <a href="https://github.com/waltertross/avl">C language library of AVL trees as general purpose sorted containers</a>. For testing purposes, I would like to have a way to fill a tree so that it is maximally unbalanced, i.e., so that it has the maximum height for the number of nodes it contains.</p>
  
  <p>AVL trees have the nice property that if, starting from the empty tree, you insert nodes in ascending (or descending) order, the tree is always exactly balanced (i.e., it has its minimum height for a given number of nodes). One sequence of integer keys that generates an exactly balanced AVL tree T<sub>n</sub> for every number of nodes n, starting from the empty tree T<sub>0</sub>, is simply</p>
  
  <ul>
  <li>k<sub>1</sub> = 0</li>
  <li>k<sub>n+1</sub> = k<sub>n</sub>+1 , i.e., k<sub>n</sub> = n-1</li>
  </ul>
  
  <p>I'm looking for a (hopefully simple) sequence of integer keys that, when inserted in the initially empty tree T<sub>0</sub>, generates AVL trees T<sub>0</sub>, ..., T<sub>n</sub> that are all maximally <b>un</b>balanced.</p>
  
  <p>I would also be interested in a solution where only the last tree, T<sub>n</sub>, is maximally unbalanced (the number of nodes n would be a parameter of the algorithm).</p>
  
  <p>A solution satisfying the constraint</p>
  
  <ul>
  <li>max(k<sub>1</sub>, ..., k<sub>n</sub>) - min(k<sub>1</sub>, ..., k<sub>n</sub>) + 1 ≤ 2 n</li>
  </ul>
  
  <p>is preferrable, but not strictly required. A key range of 4 n instead of 2 n may be a reasonable target.</p>
  
  <p>I've not been able to find anything on the Internet regarding the generation, by insertion, of AVL trees of maximal height. Of course, the sequence of generated trees I'm looking for will include all so-called Fibonacci-trees, which are the AVL trees of a given depth with the minimal number of nodes. Funnily, the English Wikipedia does not even mention Fibonacci trees (nor Fibonacci numbers!) in the article on AVL trees, while the German Wikipedia has a very good <a href="http://de.wikipedia.org/wiki/Fibonacci-Baum">article</a> completely dedicated to them. But I'm still in the dark regarding my question.</p>
  
  <p>C language bit twiddling hacks are welcome.</p>