[prev] 34 [next]

Joining Two Trees (cont)

Method for performing tree-join:
  • find the min node in the right subtree (t2)
  • replace min node by its right subtree
  • elevate min node to be new root of both trees
Advantage: doesn't increase height of tree significantly

x ≤ height(t) ≤ x+1, where x = max(height(t1),height(t2))

Variation: choose deeper subtree; take root from there.