1. Provide algorithms that are sensitive to the relative sizes of n and m. (a) L

Question

1. Provide algorithms that are sensitive to the relative sizes of n and m.

(a) Let R1 be a red-black tree with n elements. Let R2 be a red-black tree with m elements, where m ? n. How fast can you construct a red-black tree containing all elements from R1 and R2? (Hint: Take advantage of the structure that you have. What should you do if one tree has just a few elements? What if they both have the same number of elements?)

(b) Same as (a), but suppose that you are given input such that all the values in R1 are smaller than all the values in R2. (Hint: Start with an easy case: what if the black height of both trees is the same? Pick a target time complexity, and then think about all things that you are allowed to do within that time, and how they might help.)

Explanation / Answer

1.a)

Let R1 be the tree with m elements and R2 be the tree with n elemnts.

Now we can create a new tree with elements of R1 and R2 both, as following:

1. Convert both the binary trees into doubly-linked-lists L1 and L2

2. Now merge the two doubly-linked-lists L1 and L2 into one doubly-linked-lists L3.

3. Now we can build a red-black-tree from L3.

Time complexity:

all these 3 steps will take O(m+n) time each.

hence the overall time will be O(m+n).

if we have one tree with a few elements then the running time will be O(n) and if both have same elements also the running time will be O(n), as m<=n.

b)

As we have the condition that all values in R1 are smaller than R2.

So we can construct a new red-black-tree as following:

1. remove the largest element 'l' from R1 and keep in s=m.

2. now traverse the tree R2 starting from its root towards left child till we get the black node 'r' with height (log m)

[we know height of R1 is (log m) and height of R2 is (log n)]

3. now ctreate a red tree with root 's' as red, root of R1 as left child and the black node 'r' as the left child.

4. now before adding the tree having root s in place of r in R2,

i) if r is the root of R2(i.e. both trees heights are same)

then recolor node s as black and add s into R2 in place of r.

ii) if r is not the root of R2, then r has red parent which will not allow s to be the child that is also red.

here we have to use some rebalancing scheme such as Okasaki's rebalancing scheme to add the tree s to R2.

Time complexity:

here we are traversing throught the height of the tree which has height more than the other one. so the time complexity is : O(log (max(m,n))).

as we know here m<=n, So time complexity is O(log n)

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

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