# 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. – HaloKiller May 13 '14 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. – HaloKiller May 13 '14 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. – Sayan Bandyapadhyay May 13 '14 at 17:49