Red black tree partition to $\sqrt{n}$ trees 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. &lt; > 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).
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.