World's most popular travel blog for travel bloggers.

# [Solved]: Red black tree partition to $\sqrt{n}$ trees

, ,
Problem Detail:

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.