在线性时间内从排序数组构建红黑树

Question

我知道如何使用 n 个插入来构建它（每个插入的效率为 O(log(n))） (n*log(n)) 整体，我也知道 2-3-4 树的等效结构也可以用线性时间从排序数组构建。任何人都可以提供有关红黑版本的简单解释吗？

Answer 1

不管你要构建什么样的BST。算法将是相同的。只需要构建平衡二叉树。

将中间元素放到当前位置
地点[开始; middle) 元素到左子树。
将（中间；末端）元素放在右子树中。

这是O(N)算法。可以看出，结果树是平衡的。

我们有平衡树，所以根据定义：

长度（最长路径）- 长度（最短路径）<= 1

因此您需要将所有节点标记为黑色，除了树中最深的节点（将它们标记为红色）。

Answer 2

一棵高度为H的完全二叉树有2^H-1个节点。

从排序列表中生成红黑树：

每隔一个项目从列表中删除，直到 2^H-1 个项目剩余一些 H。请注意，你总是有足够的。
用剩余的项目构建一棵完整的树，全黑。
现在将您移除的所有项目附加到树中。每个项目都是一个红色节点，附加到其适当位置周围的任何一个黑色节点是一片叶子。

执行步骤 (3) 的最简单方法就是 pre-order 遍历树，将新的红色节点附加到每个黑色叶子，直到运行没有项目。

注意：Sasha 的算法也有效，但这个显然有效。

Answer 3

从功能数据结构的角度来看：Constructing Red-Black Trees有一篇论文，发现了连续插入的模式并将其与1-2数字系统联系起来。

读起来很有趣。

Answer 4

对于 Java 中实现的工作示例，您可能需要查看 Java.util.TreeMap 中的方法 buildFromSorted(int level, int lo, int hi, int redLevel, ...)。

关于 Java 的更多评论：不幸的是，如果您有自己的数据以排序的方式构建（例如排序的 ArrayLists），那么将其放入 TreeMap 中并不容易线性方式。然而，一种可能性是创建自己的 SortedMap 或 NavigableMap 实现，它由 ArrayList 内部支持。那么就可以使用这个构造函数来高效的构造TreeMap：

    MySortedMap myMap = new MySortedMap(keyArray, valueArray);
    new TreeMap<K, V> (myMap)

下面是一些示例代码：

    public class MySortedMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V> {

        private ArrayList<K> keyArray;
        private ArrayList<V> valueArray;

        public Set<Map.Entry<K,V>> entrySet() {
            return new EntrySet();
        }

        class EntryIterator implements Iterator<Map.Entry<K,V>> {

            int i;

            public EntryIterator () {
                i = 0;
            }


            @Override
            public boolean hasNext() {
                if (i < keyArray.size()) {
                    return true;
                } else {
                    return false;
                }
            }

            @Override
            public Map.Entry<K,V> next() {
                if (hasNext()) {
                    Map.Entry<K,V> en = new Entry<K,V> (keyArray.get(i), valueArray.get(i));
                    i++;
                    return en;
                } else {
                    return null;
                }
            }
        }

        final class Entry<K,V> implements Map.Entry<K,V> {
            K key;
            V value;

            @Override
            public K getKey() {
                return key;
            }

            @Override
            public V getValue() {
                return value;
            }

            @Override
            public V setValue(V value) {
                this.value = value;
                return value;
            }

            public Entry(K key, V value) {
                this.key = key;
                this.value = value;
            }
        }

        class EntrySet extends AbstractSet<Map.Entry<K,V>> {
            public Iterator<Map.Entry<K,V>> iterator() {
                return new EntryIterator();
            }

            public int size() {
                return keyArray.size();
            }

            
        }

        public MySortedMap (ArrayList<K> keyArray, ArrayList<V> valueArray) {
            if (keyArray.size() != valueArray.size()) {
                throw new RuntimeException("Key and value arrays must have the same length!");
            }

            this.keyArray = keyArray;
            this.valueArray = valueArray;
        }

        ... some unused methods ...
    }

在线性时间内从排序数组构建红黑树

Building Red-Black Tree from sorted array in linear time

algorithm

tree

big-o

red-black-tree

data-structures