title: How to check if my AVL tree implementation is correct?
body: <p>I have created an AVL tree implementation, but as an AVL tree is quite a complex structure, I need to test it. So the question is - how can I test it?</p>
  <p>Up to this moment I have the following tests:</p>
  <ol>
  <li><p>basic sanity check - checks that
  for every node height equals max.
  height of child nodes + 1, balance is in [-1, 1], left child's
  key &lt; this node's key &lt;     right
  child's key, and there are no
  circular references (like left child
  of a node is a node himself);</p>
  </li>
  <li><p>check that inorder traversal on an AVL tree
  (and on a binary search tree in the whole)
  will return values from the underlying set in order;</p>
  </li>
  <li><p>check that an AVL tree's height is strictly less than
  1.44*log2(N+2)-1 (there N is number of elements) - proved by AVL tree creators;</p>
  </li>
  <li><p>visual check - doesn't work that well, I try to draw a tree (rootnode in the first line, his direct children on the next line, childen of rootnode's direct childen on the third line and so on), but that works only on small trees, for big trees it becomes a complete mess;</p>
  </li>
  <li><p>Russian wikipedia says that it is proven experimentally, that for two insertions one rebalancing needed and for five removals also one rebalancing needed, but is it really so? English wikipedia says nothing about it, and for my AVL one rebalancing needed for two insertions or for four removals, which is not quite the same.</p>
  </li>
  </ol>
  <p>Maybe these tests are enough, but if there are any more tests, not difficult to implement, why not do it?</p>