Given the redblack trees T1 and T2 which contain m and n ele

Given the red-black trees T1 and T2, which contain m and n elements respectively, we want to determine whether they have some particular key in common. Assume an adversarial sequence that placed the m and n items into the two trees. Suppose our algorithm traverses each node of T1 using an in-order traversal and checks if the key corresponding to the current node traversed exists in T2. Express the asymptotic running time of this procedure, in terms of m and n. Now suppose our algorithm first allocates a new hash table H1 of size m and then inserts every key in T1 into H1 during a traversal of T1. Then, we traverse the tree T2 and search for whether the key of each node traversed already exists in H1. Give the asymptotic running time of this algorithm in the average case. Justify your answer.

Solution

As insertion, search and find in red black tree is O(n) wherever n is the no. of nodes in a tree.

(A) Traversing each node of T1 can have O(m) quality and then notice of any node a1( in T1) in T2 can O(n) quality.

So total quality can be O(m*log(n))

(B) Creating a hashtable out of T1 are of O(m) quality and traversing each node of T2 can be O(n)

So total quality can be O(m) (if m > n) or O(n) (if n > m)