Given the red-black trees T1 and T2, which contain m and n elements respectively

Question

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.

(a) 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.

(b) Now suppose our algorithm rst allocates a new hash table H1 of size m (assume H1 uses a uniform hash function) 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.

Explanation / Answer

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

(A) Traversing each node of T1 will have O(m) complexity and then find of any node a1( in T1) in T2 will O(n) complexity.

So total complexity will be O(m*log(n))

(B) Creating a hashtable out of T1 will be of O(m) complexity and traversing every node of T2 will be O(n)

So total complexity will be O(m) (if m > n) or O(n) (if n > m)

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.