c++ - 填充红黑树的最有效方法是什么？

Question

假设我知道关于某个数据集的所有信息以及它的控制顺序——将它组织成红黑树的最有效方法是什么？

或者，在流行的 std::set/map 实现(基于“红黑树”)的上下文中——填充我的 std::set 的最有效方法是什么 与上述数据集？

在你回答之前，请考虑一下:

• afaik，红黑树具有廉价的 O(1)(正确提示)插入...除非树深度违反特定限制，在这种情况下它将被重新平衡(具有 O(log N) 成本)--就像 std::vector::push_back() 的情况一样，我们最终得到摊销的常量复杂度

• 例如如果数据集是值列表 [0,999]，则应该有一系列永远不会触发重新平衡的提示插入(即保持每个插入 O(1))。

非常简单的示例(需要弄清楚如何选择这些 YYY/ZZZ 值):

std::set<int> s;
std::vector< std::set<int>::iterator > helper(1000);

helper[0] = s.insert(0);
helper[1] = s.insert(helper[0], 1);
//...
helper[500] = s.insert(helper[YYY], 500);
//...
helper[999] = s.insert(helper[ZZZ], 999);

我在找什么:

1. 一种算法，允许我使用(特别)准备好的(任意长)序列填充(“基于红黑树”的)std::set，其中保证每次插入 O (1)

2. 应该有一种方法可以减少额外的内存需求(即 helper 的大小)或理想情况下消除对它的需求

3. 在最坏的可能情况下填充树的算法(了解传入数据集应该不的样子)——当我们最终得到最大可能数量的rebalance 事件

4. 奖金目标是获得基于“AVL 树”的问题 1-3 的答案 std::set

谢谢

Answer 1

找到了一种不需要额外内存并且适用于任何二叉搜索树(红黑/AVL/等)的算法:

1. 传入数据数组表示“扁平化”二叉树(根在 [0]，根子节点在 [1] 和 [2]，左节点子节点在 [3] 和 [4]，右节点子节点在 [5] 和 [6] 等处)。技巧是以这样的方式选择每个子树的根，使得生成的二叉树的每个 lvl(但最后一个)都被填充，并且在最后一层上所有节点形成一个“不间断”的线。像这样:

        N11
      /     \
    N21      N22
    / \      /
   N31 N32 N33
   

请参阅下面的代码，了解如何将已排序的数组转换为这样的序列。我相信对于任何序列，只有一种可能的方式将它安排在像这样的二叉搜索树中——也就是说，你在这里得到某种“稳定性”保证(对于给定的序列长度，我们确切地知道每个元素将在哪里结束在树上)。

1. 然后您对数据执行一次传递并逐级填充树。在每个级别，我们都知道在切换到下一个级别(或用完数据)之前要提取多少元素 (2^(lvl-1))。在每次迭代开始时，我们将我们的位置重置为最左边的元素(std::set<T>::begin())，并在插入左右子节点后，我们移动到当前级别的下一个叶子(来自最后一个 ++it 调用的结果的两倍 insert())。

注意事项:

• 与 std::set<int>性能优势(与排序序列的提示插入相比为 5-10%)

• 不幸的是，MS 红黑树实现最终在这里执行了很多不必要的工作——检查相邻元素(以确保插入不会破坏二叉树不变性)、重新绘制节点(由于某种原因新插入的节点)总是红色的)，可能还有其他的。检查邻居涉及额外的比较和内存访问以及遍历树的多个级别

• 如果这种方法在内部实现(不使用 std::set 公共(public)接口(interface))作为期望数据符合要求并在不符合要求时声明“未定义行为”的函数，则该方法的好处会大得多。 ..

• ... 在这种情况下，更好的算法会以深度优先的方式填充树，并且需要以不同方式重新排列输入数据(上例中的 [N11, N21, N31, N32, N22, N33])。我们最终也将只进行一次树遍历......唉，不能使用 std::set 实现这种方法。不过，公共(public)接口(interface) -- 它将在构造的每个步骤中强制执行红黑树不变性，从而导致不必要的重新平衡

代码:(MSVC 2015，请原谅马铃薯质量——不到一个小时就写在了膝盖上)

#include <set>
#include <cassert>
#include <vector>
#include <utility>
#include <chrono>
#include <cstdio>


using namespace std;


unsigned hibit(size_t n)
{
    unsigned long l;
    auto r = _BitScanReverse(&l, n);
    assert(r);
    return l;
}


int const* pick_root(int const* begin, int const* end)
{
    assert(begin != end);
    size_t count = end - begin;

    unsigned tree_order = hibit(count);         // tree height minus 1
    size_t max_tail_sz = 1 << tree_order;       // max number of nodes on last tree lvl
    size_t filled_sz = max_tail_sz - 1;         // number of nodes on all but last tree lvl
    size_t tail_sz = count - filled_sz;         // number of nodes on last lvl

    return (tail_sz >= max_tail_sz/2) ?         // left half of tree will be completely filled?
        begin + max_tail_sz - 1                 // pick (2^tree_order)'s element from left
        :
        end - max_tail_sz/2;                    // pick (2^(tree_order - 1))'s element from right
}


vector<int> repack(vector<int> const& v)
{
    vector<int> r; r.reserve(v.size());
    if (!v.empty())
    {
        unsigned tree_order = hibit(v.size());  // tree height minus 1

        vector<pair<int const*, int const*>> ranges(1, make_pair(&v[0], &v[0] + v.size()));
        for(size_t i = 0; i <= tree_order; ++i)
        {
            vector<pair<int const*, int const*>> ranges2; ranges2.reserve(ranges.size()*2);

            for(auto const& range: ranges)
            {
                auto root = pick_root(range.first, range.second);
                r.push_back(*root);

                if (root != range.first)
                {
                    ranges2.push_back(make_pair(range.first, root));

                    if (root + 1 != range.second)
                        ranges2.push_back(make_pair(root + 1, range.second));
                }
            }

            ranges.swap(ranges2);
        }
        assert(ranges.empty());
    }
    return r;
}


set<int> populate_simple(std::vector<int> const& vec)
{
    set<int> r;
    for(auto v: vec) r.insert(v);
    return r;
}


set<int> populate_hinted(std::vector<int> const& vec)
{
    set<int> r;
    for(auto v: vec) r.insert(r.end(), v);
    return r;
}


set<int> populate_optimized(std::vector<int> const& vec)
{
    set<int> r;
    if (vec.empty()) return r;

    int const* p = &vec[0];
    int const* pend = &vec[0] + vec.size();

    r.insert(*p++);                   // take care of root
    if (p == pend) return r;

    for(size_t count = 1; ; count *= 2) // max number of pairs on each tree lvl
    {
        auto pos = r.begin();

        for(size_t i = 1; ; ++i)
        {
            r.insert(pos, *p++);
            if (p == pend) return r;

            //++pos;            // MS implementation supports insertion after hint

            pos = r.insert(pos, *p++);
            if (p == pend) return r;
                            // pos points to rightmost leaf of left subtree of "local" tree
            ++pos;          // pos points to root of "local" tree (or end())

            if (i == count) break;

            ++pos;      // pos points to leftmost leaf of right subtree of "local" tree
        }
    }
}


struct stopwatch
{
    chrono::high_resolution_clock::time_point start_;

    stopwatch() : start_(std::chrono::high_resolution_clock::now()) {}

    auto click()
    {
        auto finish = std::chrono::high_resolution_clock::now();
        auto mks = std::chrono::duration_cast<std::chrono::microseconds>(finish - start_);
        return mks.count();
    }
};


int main()
{
    size_t N = 100000;
    vector<int> v(N, 0);
    for(unsigned i = 0; i < N; ++i) v[i] = i;   // sorted array

    auto rv = repack(v);

    {
        stopwatch w;
        auto s = populate_simple(v);
        printf("simple   : %I64d mks\n", w.click());
    }

    {
        stopwatch w;
        auto s = populate_hinted(v);
        printf("hinted   : %I64d mks\n", w.click());
    }

    {
        stopwatch w;
        auto s = populate_optimized(rv);
        printf("optimized: %I64d mks\n", w.click());
    }

    return 0;
}

典型结果:

simple   : 14904 mks
hinted   : 7885 mks
optimized: 6809 mks

simple   : 15288 mks
hinted   : 7415 mks
optimized: 6947 mks

我很确定测量结果并不完全准确，但关系始终成立——优化版本总是更快。另外，请注意，用于重新排列元素的算法可能会得到改进——目的是优化树种群(而不是输入数据准备)。