# 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. < > 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.
• 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. Commented May 13, 2014 at 9:12
• 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. Commented May 13, 2014 at 9:13
• 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. Commented May 13, 2014 at 17:49