Building Red-Black Tree from sorted array in linea

问题:

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?

回答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).

回答2:

A complete binary tree of height H has 2^H-1 nodes.

To make a red black tree from a sorted list:

1. Remove every second item from the list until you have 2^H-1 items remaining for some H. Note that you will always have enough.
2. Build a complete tree out of the remaining items, all black.
3. Now attach all the items you removed to the tree. Each item will be a red node, attached to whichever of the black nodes around its proper position is a leaf.

The easiest way to do step (3) is just to do a pre-order traversal of the tree, attaching new red nodes to every black leaf until you run out of items.

NOTE: Sasha's algorithm also works, but this one obviously works.

回答3:

From a functional data structure perspective: there is a paper for Constructing Red-Black Trees, which discovered the pattern of continuous insertion and related it to 1-2 number system.

It's a fun read.