[prev] [index] [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 depth of tree significantly

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

Variation: choose deeper subtree; take root from there.