Building Red-Black Tree from sorted array in linear time

Question

i know how to build it with n insertions ( each with O(log(n)) efficiency ) (n*log(n)) overall ,i also know that the equivalent structure of 2-3-4 tree can also be build with linear time from sorted array. can anyone please provide a simple explanation about the red-black version?

Answer 1

No matter what kind of BST you are going to build. The algorithm will be the same. Only need to build balanced binary tree.

1. Place middle element to the current position
2. Place [begin; middle) elements to the left subtree.
3. Place (middle; end) elements to the right subtree.

This is O(N) algorithm. It can be shown, that the result tree will be balanced.

We have balanced tree, so by definition:

length(longest path) - length(shortest path) <= 1

So you need to mark all nodes as black, except the deepest nodes in the tree (mark them as red).