title: Comparison between AVL trees and WAVL trees regarding a series of inserts, deletes, and searches
body: <p>We starts with an empty tree and do the same sequence of inserts, deletes, and searches. Once with an AVL tree and once with a WAVL tree. The question is to determine if the number of times that we change the ranks of nodes in the AVL tree is the same number of times that we change the ranks of nodes in the WAVL tree (or the number multiplied by a constant).</p>
  
  <p>I think that it's not true. Let call the length of the sequence n. First we do n/2 inserts. The inserts take more or less the same number of rank promotes in both trees. We end up up with two balanced trees. Then we take a node with key which is less than every key that was before and do the sequence insert(x), delete(x), insert(x), delete(x),... (we do it the remaining n/2 times).</p>
  
  <p>In that way, the final n/2 operations in the AVL tree will take at least (n/2)logn time, while in the WAVL it will take n/2 time (can be proved with potential function).</p>