Найден алгоритм, который не требует дополнительной памяти и работает для любого бинарного дерева поиска (красно-черный / AVL / и т. Д.):
массив входящих данных для представления «уплощенного»"двоичное дерево (root в [0], корневые дочерние элементы в [1] и [2], дочерние узлы в левом узле в [3] и [4], дочерние узлы в правом узле в [5] и [6] и т. д.).Хитрость заключается в том, чтобы выбрать корни каждого поддерева таким образом, чтобы в полученном двоичном дереве каждый lvl (но последний) был заполнен, а на последнем уровне все узлы образовывали «непрерывную» линию.Например:
N11
/ \
N21 N22
/ \ /
N31 N32 N33
См. Код ниже о том, как преобразовать отсортированный массив в такую последовательность.Я полагаю, что для любой последовательности есть только один возможный способ упорядочить ее в бинарном дереве поиска, например, таким образом, - здесь вы получите какую-то гарантию «стабильности» (для данной длины последовательности мы точно знаем, где будет находиться каждый элемент).в дереве).
затем вы выполняете один проход над вашими данными и заполняете дерево по уровням.На каждом уровне мы точно знаем, сколько элементов нужно потянуть (2 ^ (lvl-1)), прежде чем перейти к следующему lvl (или исчерпать данные).В начале каждой итерации мы сбрасываем нашу позицию на крайний левый элемент (
std::set<T>::begin()) и после вставки левого и правого потомков мы переходим на следующий лист на текущем уровне (удваивается
++it от результата последнего вызова
insert()).
Примечания:
с std::set<int> выигрышем в производительности (по сравнению с подсказкой вставки отсортированной последовательности 5-10%)
к сожалению, реализация красно-черного дерева MS в итоге выполняет здесь много ненужной работы - проверка соседних элементов (чтобы убедиться, что вставка не нарушает инвариант двоичного дерева), перерисовывание узлов (вновь вставленныеузел по какой-то причине всегда красный) и, вероятно, что-то еще.Проверка соседей включает в себя дополнительные сравнения и доступ к памяти, а также обход дерева на несколько уровней
. Преимущество этого подхода было бы значительно выше, если бы он был реализован внутри (без использования открытого интерфейса std::set).как функция, которая ожидает, что данные будут соответствовать требованиям и объявляет «неопределенное поведение», если это не так ...
... в этом случае еще лучший алгоритм будет заполнять глубину дерева.сначала и потребует, чтобы входные данные были переставлены по-другому ([N11, N21, N31, N32, N22, N33] в примере выше).В конечном итоге мы также проведем только один обход дерева ... Увы, мы не можем реализовать этот подход с использованием std::set открытого интерфейса, хотя - он будет приводить в действие инвариант красно-черного дерева на каждом этапе построения, вызывая ненужную перебалансировку
Код: (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
Я почти уверен, что измерения не совсем точны, но соотношение всегда сохраняется - оптимизированная версия всегда быстрее.Также обратите внимание, что алгоритм, используемый для перестановки элементов, возможно, будет улучшен - целью было оптимизировать популяцию деревьев (не подготовку входных данных).