title: Merge 2 AVL trees with corrupted nodes in one of them
body: <p>Suppose we have 2 AVL trees (with methods <code>insert(key)</code> and <code>delete(key)</code>), but <strong>in one of them</strong> there exist corrupted nodes (the number of corrupted nodes is much less than the total number of nodes in that tree).</p>
  <p>We want to merge 2 AVL trees into 1 single AVL tree such that the corrupted nodes are removed (we have the list of keys of corrupted nodes).</p>
  <p>The <em>&quot;naive&quot; algorithm</em> is (assume tree 1 contains corrupted nodes): For each of the corrupted nodes, delete it from tree 1. Then insert all remaining nodes from tree 1 to tree 2, so the final AVL tree is the &quot;merged&quot; tree we want.</p>
  <p><strong>Now the question is coming up with a more efficient way to merge 2 trees, better than the <em>naive algorithm</em> above.</strong></p>
  <p>Anyone has any idea? Thanks for your help!</p>