3.21

Since all the elements in S2 have keys larger than the keys of the elements in S1, those two trees can be subtrees of one tree whose root node will have a key larger than the largest key in S1 and smaller than the smallest key in S2. Then S2 will be the right subtree and S1 the left subtree. The easiest way to do this is to find the minimum element of S2 (or the maximum of S1) and put it as the root of the concatenated tree and than update its left and right pointer to point to the root of S1 and S2 respectively. The worst-case running time will be O(h), which is the time of retrieving the minimum (maximum) element of a tree.

Back to Chapter 3