[prev] [index] [next]

Joining Two Trees

Tree operations so far have involved just one tree.

An operation on two trees:   t = join(t1,t2) 

// Pre-conditions:
// takes two BSTs; returns a single BST
// max(key(t1)) < min(key(t2))

Tree join(Tree t1, Tree t2) { ...  }

// Post-conditions:
// result is a BST (i.e. fully ordered)
// result contains all items from t1 and t2

Allows an alternative formulation of delete()