0
$\begingroup$

This is a question I have stumbled upon in an old Algorithms test I found online:

A) Plan an algorithm that does the following: Input: Red-Black tree Output: $\sqrt{n}$ seperate trees, so that every tree has $\sqrt{n}$ nodes. What is the complexity of the Algorithm you planned? must show analysis.

B) Assume that you have started from an empty Red Black tree, and that the input is a set of nodes and not a Red Black tree. Show how can you make a more efficient algorithm of partitioning the nodes to $\sqrt{n}$ Red Black trees so that every tree has $\sqrt{n}$ nodes. What is the complexity of the new Algorithm you planned and how does it affect existing Red Black tree functions? must show analysis.

Now I have answered A and I am pretty sure that's the best answer there is, but I need your help in telling me if I can do better. This is without analysis:

Algorithm: 1. Scan the Red Black tree using In-Order traversal to build a sorted array out of it. < > O(n). 2. Divide the array to $\sqrt{n}$ sub-arrays and build a Red Black tree out of every sub > array - O(n) total.

Now what I don't really understand is how do I solve B. I'm not exactly sure if the input in B is a Red Black tree or just a set of nodes, so both will be acceptable if you want to share your answer to B with me. I have asked a student and he told me that the complexity that I should get in B is $O(\sqrt{n}*log(n))$.

I need help reaching that, or maybe something better (hints and stuff).

Improve this question
$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

For question B) you need to make $O(\sqrt{n})$ RB trees from $n$ nodes (there is no tree to start with just bunch of nodes). Thus you need to process each node at least once. Thus time complexity of this building should be $\Omega(n)$. Thus I think there is no hope of getting the $O(\sqrt{n}\log n)$ bound.

Improve this answer
$\endgroup$
6
  • $\begingroup$ I actually though about an idea: Red Black trees are balanced, so their height is $O(logn)$. So the idea: 1. Go down $O(log\sqrt{n})$ levels so that we have covered a complete binary tree of $2\sqrt{n}+1$ nodes. 2. Go through it's leaves, taking out each leaf. thus we have $\sqrt{n}$ trees. 3. Create an array of pointers to binary trees and assing a counter for each index in it. 4. Build a Red Black tree in each index from all the trees we have at the same time using pointers, raising the counter for each node we add. $\endgroup$
    – HaloKiller
    Commented May 13, 2014 at 9:12
  • $\begingroup$ I think the complexity sums up to $O(\sqrt{n}log(\sqrt{n}))$, but there are a few changes to be done so that it will fit (B). P.S.: No changes in RB Tree functions are needed in my solution. $\endgroup$
    – HaloKiller
    Commented May 13, 2014 at 9:13
  • $\begingroup$ what do you think? $\endgroup$
    – HaloKiller
    Commented May 13, 2014 at 17:19
  • $\begingroup$ You create a RB tree having $2\sqrt{n}+1$ nodes. Then you create $\sqrt{n}$ more trees. And how many nodes are you adding in those $\sqrt{n}$ trees? Note that you are adding nodes and not just connecting a pointer to existing RB tree. Thus to construct each tree you need $\Omega(\sqrt{n})$ time. Thus in total you need $\Omega(n)$ time. The lower bound is applicable to your algorithm also. $\endgroup$
    – Sayan Bandyapadhyay
    Commented May 13, 2014 at 17:49
  • $\begingroup$ And what if I connect the pointer to an existing RB tree? $\endgroup$
    – HaloKiller
    Commented May 15, 2014 at 7:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.