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

Question

我知道如何通过 n 次插入（每次都具有O(log(n))的效率）来构建它，总共需要(n*log(n))的时间。我还知道从排序后的数组中可以线性时间构建等价于2-3-4树的结构。请问有人能提供关于红黑树版本的简单解释吗？

- Michael G

---

请您详细说明一下您的努力，展示代码中必要的部分。 - Enamul Hassan

我不是在尝试编写代码，只是想理解这个概念。 - Michael G

如果您知道如何构建2-3-4树，那么只需按照通常的对应关系，在3节点处使用红色，而在4节点处使用两个红色即可。 - rici

Answer 1

无论你要构建什么样的BST，算法都是相同的。只需要构建平衡二叉树。

1. 将中间元素放置在当前位置
2. 将[begin; middle)元素放在左子树中。
3. 将(middle; end)元素放在右子树中。

这是一个O(N)的算法。可以证明，结果树将是平衡的。

我们有平衡树，因此根据定义：

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

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

- SashaMN

---

颜色方面怎么样？ - Michael G

@SashaMN，有关“可以证明结果树将是平衡的”这一说法的任何链接吗？ - Rauni Lillemets

另外，我理解得正确吗，这个算法应该递归地应用吗？ - Rauni Lillemets

Answer 2

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

从一个排序列表中创建红黑树的步骤如下：

1. 从列表中删除每隔一个项目，直到剩下2^H-1个项目，其中H是某个整数。请注意，您总会有足够的项目。
2. 使用剩余的所有项目构建一个完整的黑色树。
3. 现在将删除的所有项目连接到树上。每个项目都将成为一个红色节点，连接到其正确位置周围的黑色节点之一。

做第三步最简单的方法就是对树进行前序遍历，在每个黑色叶子节点上附加新的红色节点，直到没有项目为止。

注意：Sasha的算法也可以，但这个算法显然更好。

- Matt Timmermans

Answer 3

从功能数据结构的角度来看：有一篇构建红黑树的论文，发现了连续插入的模式，并将其与1-2数字系统相关联。

这是一篇有趣的阅读材料。

- junjiah

---

该页面无法找到。 - akiva

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 ...
    }

- Rauni Lillemets