Clever Geek Handbook

Algorithm - How to efficiently combine two binary search trees?

I am not asking how to merge two binary search trees, as this question did How to merge two BSTs efficiently?

I am really asking how to combine two trees. Therefore, if tree A of all nodes is smaller than any node of tree B, we can merge the two trees. But how can I do this efficiently?

My idea is to find the minimum of tree B and then let tree A be the left child of the minimum (tree B).

It's simple enough and time consuming O(height of B)

.

But I think this solution has some problems:

  • this can cause the final big tree to be out of balance.
  • What if the worst running time O(h)

    , where h

    is the maximum height of two trees?

Actually the book " Algorithm Design Guide" has this excise. My simple solution for this exercise?

The concatenation operation takes two sets S1 and S2, where each key in S1 is less than any key in S2, and concatenates them. Provide an algorithm for combining two binary search trees into one binary search tree . In the worst case, the running time should be O (h), where h is the maximum height of two trees.

thank

+3


source to share


2 answers


Let A be a smaller set. Suppose x = maximum_element (A) and y = minimum_element (B).



We know that x <y. take a node with key value equal z = (x+y)/2

and make A its left subtree and B its right subtree. remove the added node (with key z

) from this BST.

+7


source


I'm going to define:

  • h_A

    = maximum height A

  • h_B

    = maximum height B

  • h = min(h_A, h_B)

Your worst case running time of your solution O(h_B)

, which happens when the depth min(B)

is equal h_B

.

Worst case question O(h)

. Solution A O(h)

is preferred as if there is h_B

much more than h_A

, we'd be better off attaching B

to the correct child max(A)

than your current solution, which attaches A

to the left child min(B)

.



Here's how to do it:

  • Recursively navigate to the right of A

    and to the left of B

    .
  • Stop moving when you go to max(A)

    or min(B)

    .
  • One of three is possible:
    • You are in max(A)

      . In this case, setmax(A).right = B

    • You received min(B)

      . In this case, setmin(B).left = A

    • You got max(A)

      and min(B)

      . In this case, do one of the above options.

At best, steps have been taken h_A

or h_B

, whichever is less. Ie h

. Attaching one tree to an element is permanent. So the running time is O (h).

+2


source






More articles:


All Articles