Suppose we have 2 AVL trees (with methods insert(key) and delete(key)), but in one of them there exist corrupted nodes (the number of corrupted nodes is much less than the total number of nodes in that tree).

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).

The "naive" algorithm 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 "merged" tree we want.

Now the question is coming up with a more efficient way to merge 2 trees, better than the naive algorithm above.

Anyone has any idea? Thanks for your help!

CodePudding user response：

A binary search tree can list its nodes in increasing order in linear time O(N). You can organize a merging process where you enumerate the nodes of both trees simultaneously, fetching the nodes in global order (and dropping the corrupt ones).

If you store the sorted elements in an array, it is possible to convert to a new balanced BST in linear time. You make it AVL by just setting all balance factors.

I doubt that it is possible to construct the new tree without first merging to an intermediate array. (Which only needs to be an array of pointers.)