填充红黑树的最有效方法是什么？
What is the most efficient way to populate a red black tree?
假设我知道关于某个数据集的所有信息以及它的控制顺序——将它组织成红黑树的最有效方法是什么？
或者，在流行的 std::set/map 实现（基于 "red black tree"）的上下文中——用上述数据集填充我的 std::set 的最有效方法是什么？
在回答之前，请考虑一下：
afaik，红黑树具有廉价的 O(1)（正确提示）插入...除非树深度违反特定限制，在这种情况下它将被重新平衡（使用 O(log N)成本）——就像 std::vector::push_back() 的情况一样，我们最终得到摊销常数复杂度
例如如果数据集是值列表 [0,999]，则应该有一系列永远不会触发重新平衡的提示插入（即保持每个插入 O(1)）。
非常简单的例子（需要弄清楚如何 select 这些 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);
我在找什么：
一种算法，允许我填充（"red black tree"-based）std::set 与（特别）准备好的（任意长）序列，其中保证每个插入 O(1 )
应该有一种方法可以减少额外的内存需求（即 helper 的大小）或理想情况下消除对它的需求
一种在最坏情况下填充树的算法（以了解传入数据集应该而不是的样子）——这是我们结束时的情况最大可能数量 rebalance 事件
和奖励 objective 是获得基于 "AVL tree" 的问题 1-3 的答案 std::set
谢谢
首先，对输入进行排序。
理想的情况是将排序后的输入放入平衡二叉树中，但假装它在树中也可以；只是需要更多的簿记。它实际上不必是真正的树数据结构；您可以使用一个数组，其中根是元素 0，元素 i 的子元素位于 2i+1 和 2i+2。不管怎样，树是可以递归构建的。
一旦您拥有原始数据的平衡二叉树，就需要将其复制到集合中，而不需要进行任何重新平衡。为此，对你的树进行广度优先扫描（如果你使用上面提到的数组，这只是数组的顺序扫描，这使得这一步非常简单）。您可以在 BFS 中保存每个级别的插入点，以便获得下一个级别的提示（因此您需要能够将迭代器保持在树的一半左右），但它会更容易并且可能更快在构建集合时遍历集合，从每个级别的开头开始，否则在每次插入后前进两个元素。
None 这比按顺序构建集合要快。但这是问题的答案。
对于最差的提示插入总体，以反向排序顺序插入元素，用前一个插入点的插入点提示每个插入。
我认为相同的算法也适用于 AVL 树。
找到不需要额外内存且适用于任何二叉搜索树的算法 (red-black/AVL/etc)：
传入数据数组来表示 "flattened" 二叉树（根在 [0]，根子节点在 [1] 和 [2]，左节点子节点在 [3] 和 [ 4]，[5] 和 [6] 等处的右节点子节点）。技巧是 select 每个子树的根，这样生成的二叉树的每个 lvl（但最后一个）都被填充，并且在最后一层所有节点形成 "uninterrupted" 行。像这样：
N11
/ \
N21 N22
/ \ /
N31 N32 N33
请参阅下面的代码，了解如何将已排序的数组转换为这样的序列。我相信对于任何序列，只有一种可能的方式将它安排在像这样的二叉搜索树中——也就是说，你最终会得到某种 "stability" 保证（对于给定的序列长度，我们确切地知道每个元素将在哪里最终在树上）。
- 然后你对你的数据执行一次传递并逐级填充你的树。在每个级别，我们都知道在切换到下一个级别（或 运行 数据之外）之前要提取多少元素 (2^(lvl-1))。在每次迭代开始时，我们将我们的位置重置为最左边的元素 (
std::set<T>::begin())，在插入左右子元素后，我们移动到当前级别的下一个叶子（从最后一个 [=15 的结果加倍 ++it =]打电话）。
备注：
具有 std::set<int> 性能优势（与排序序列的提示插入相比是 5-10%）
不幸的是，MS 红黑树实现最终在这里执行了很多不必要的工作——检查相邻元素（以确保插入不会破坏二叉树不变性），重新绘制节点（新插入由于某种原因，节点总是红色的），可能还有其他原因。检查邻居涉及额外的比较和内存访问以及遍历树的多个级别
如果在内部实现（不使用 std::set public 接口）作为期望数据符合要求并声明的函数，这种方法的好处会高得多"undefined behavior" 如果不是...
... 在这种情况下，更好的算法会优先填充树深度，并且需要以不同方式重新排列输入数据（上例中的 [N11, N21, N31, N32, N22, N33]）。我们最终也将只进行一次树遍历......唉，不能使用 std::set public 接口实现这种方法，尽管它会在构造的每一步强制执行红黑树不变性造成不必要的再平衡
代码：（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
我很确定测量结果并不完全准确，但关系始终成立 -- 优化版本总是更快。另外，请注意，用于重新排列元素的算法可能会得到改进——目的是优化树种群（而不是输入数据准备）。
假设我知道关于某个数据集的所有信息以及它的控制顺序——将它组织成红黑树的最有效方法是什么？
或者，在流行的 std::set/map 实现（基于 "red black tree"）的上下文中——用上述数据集填充我的 std::set 的最有效方法是什么？
在回答之前，请考虑一下：
afaik，红黑树具有廉价的 O(1)（正确提示）插入...除非树深度违反特定限制，在这种情况下它将被重新平衡（使用 O(log N)成本）——就像
std::vector::push_back()的情况一样，我们最终得到摊销常数复杂度例如如果数据集是值列表 [0,999]，则应该有一系列永远不会触发重新平衡的提示插入（即保持每个插入 O(1)）。
非常简单的例子（需要弄清楚如何 select 这些 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);
我在找什么：
一种算法，允许我填充（"red black tree"-based）
std::set与（特别）准备好的（任意长）序列，其中保证每个插入 O(1 )应该有一种方法可以减少额外的内存需求（即
helper的大小）或理想情况下消除对它的需求一种在最坏情况下填充树的算法（以了解传入数据集应该而不是的样子）——这是我们结束时的情况最大可能数量
rebalance事件和奖励 objective 是获得基于 "AVL tree" 的问题 1-3 的答案
std::set
谢谢
首先，对输入进行排序。
理想的情况是将排序后的输入放入平衡二叉树中，但假装它在树中也可以；只是需要更多的簿记。它实际上不必是真正的树数据结构；您可以使用一个数组，其中根是元素 0，元素 i 的子元素位于 2i+1 和 2i+2。不管怎样，树是可以递归构建的。
一旦您拥有原始数据的平衡二叉树，就需要将其复制到集合中，而不需要进行任何重新平衡。为此，对你的树进行广度优先扫描（如果你使用上面提到的数组，这只是数组的顺序扫描，这使得这一步非常简单）。您可以在 BFS 中保存每个级别的插入点，以便获得下一个级别的提示（因此您需要能够将迭代器保持在树的一半左右），但它会更容易并且可能更快在构建集合时遍历集合，从每个级别的开头开始，否则在每次插入后前进两个元素。
None 这比按顺序构建集合要快。但这是问题的答案。
对于最差的提示插入总体，以反向排序顺序插入元素，用前一个插入点的插入点提示每个插入。
我认为相同的算法也适用于 AVL 树。
找到不需要额外内存且适用于任何二叉搜索树的算法 (red-black/AVL/etc)：
传入数据数组来表示 "flattened" 二叉树（根在 [0]，根子节点在 [1] 和 [2]，左节点子节点在 [3] 和 [ 4]，[5] 和 [6] 等处的右节点子节点）。技巧是 select 每个子树的根，这样生成的二叉树的每个 lvl（但最后一个）都被填充，并且在最后一层所有节点形成 "uninterrupted" 行。像这样：
N11 / \ N21 N22 / \ / N31 N32 N33
请参阅下面的代码，了解如何将已排序的数组转换为这样的序列。我相信对于任何序列，只有一种可能的方式将它安排在像这样的二叉搜索树中——也就是说，你最终会得到某种 "stability" 保证（对于给定的序列长度，我们确切地知道每个元素将在哪里最终在树上）。
- 然后你对你的数据执行一次传递并逐级填充你的树。在每个级别，我们都知道在切换到下一个级别（或 运行 数据之外）之前要提取多少元素 (2^(lvl-1))。在每次迭代开始时，我们将我们的位置重置为最左边的元素 (
std::set<T>::begin())，在插入左右子元素后，我们移动到当前级别的下一个叶子（从最后一个 [=15 的结果加倍++it=]打电话）。
备注：
具有
std::set<int>性能优势（与排序序列的提示插入相比是 5-10%）不幸的是，MS 红黑树实现最终在这里执行了很多不必要的工作——检查相邻元素（以确保插入不会破坏二叉树不变性），重新绘制节点（新插入由于某种原因，节点总是红色的），可能还有其他原因。检查邻居涉及额外的比较和内存访问以及遍历树的多个级别
如果在内部实现（不使用
std::setpublic 接口）作为期望数据符合要求并声明的函数，这种方法的好处会高得多"undefined behavior" 如果不是...... 在这种情况下，更好的算法会优先填充树深度，并且需要以不同方式重新排列输入数据（上例中的
[N11, N21, N31, N32, N22, N33]）。我们最终也将只进行一次树遍历......唉，不能使用std::setpublic 接口实现这种方法，尽管它会在构造的每一步强制执行红黑树不变性造成不必要的再平衡
代码：（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
我很确定测量结果并不完全准确，但关系始终成立 -- 优化版本总是更快。另外，请注意，用于重新排列元素的算法可能会得到改进——目的是优化树种群（而不是输入数据准备）。