1
$\begingroup$

I have the following question to solve;

Given $K$ BST consisting of $N$ total elements, show how you can create a Red Black Tree in $O(N\log K)$ time.

I had the following idea but it falls on the last part of insertion into the red black tree;

Get an inorder scan of each BST (total of $O(N)$) into lists. From each list pick the smallest element (the min) and insert it along with the index of the list it originated from (the key-value pair (value,list_index))into an auxiliary min-heap.
Extract the min value from the auxiliary heap and insert it into the RBT. Now take the next element from the list_index list and insert it into the heap.

So the building of the min-heap will take $O(K\log K)$ time ($K$ insertions into the min heap which at most will take $\log K$ time).
Extracting the min $N$ times will take $O(N\log K)$ time.
Inserting into the RBT $N$ times will take $O(N\log N)$ time <-- This is the issue.

As I understand it - the first insertion will take $O(\log 1)$, the next $O(\log 2)$, etc. until we have inserted all $N$ elements - resulting in a total of $O(N\log N)$ instead of the desired $O(N\log K)$.

Anyone has any idea how to perform this in the wanted time or where my solution is wrong?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

Your idea of maintaining a min-heap of $K$ elements of the form (value,list_index) is great.

You "extract the min value from the auxiliary heap and insert it into the RBT". When you insert it into the RBT directly, you are not taking advantage of the information that it is the largest element so far. You are treating it just like an arbitrary element, which slows down your algorithm.

Initialize an empty list of capacity $N$. Append the extracted min value from the auxiliary heap to the list every time instead. The initialization and all $N$ appendments cost $O(N)$ time.

From the list at last, which is a sorted list of $N$ elements, we can build an RBT in $O(N)$ time. (In fact, given a sorted list of $N$ elements, we can build any given type of BST in $O(N)$ time. Or any type of BST that I know of).

Improve this answer
$\endgroup$
4
  • $\begingroup$ So, just so I have the full picture, since my book does not cover how to build an RBT in O(N). I will take this list and recursively build a balanced BST from it (take the middle element, then the middle of the left, middle of the right and so on). Then - if N = (2^h) -1 -> color all nodes black ; else, then for some h N< (2^h) -1, color all 2^(h-1) in black and the rest in red. Is that right? $\endgroup$
    – Alon .G.
    Commented May 5, 2023 at 14:35
  • $\begingroup$ Right basically. Minor correction, for some integer $h$ such that $2^{h-1}-1< N<2^h-1$, color all $2^{h-1}-1$ nodes (that are of depth $<h$) in black and the rest in red. $\endgroup$
    – John L.
    Commented May 5, 2023 at 14:54
  • $\begingroup$ Thanks John, can't upvote your answer cause not enough rep but marked it as correct :) $\endgroup$
    – Alon .G.
    Commented May 5, 2023 at 15:06
  • $\begingroup$ Thanks, Alon .G. $\endgroup$
    – John L.
    Commented May 5, 2023 at 15:10

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.