Допустим:
Если упрощать совсем грубо, то у нас есть какое-то двоичное дерево поиска, нам надо вставить в него огромное количество значений:
int size = много-много; int data[size]={...}; // данные std::map<int> map; for(int n=0; n<size; n++) map.insert(data[n]); |
Представим, что std::map это не балансируемое бинарное дерево. У нас есть какая-то его ветка:
Мы вставляем в дерево два числа X, Y, оба числа больше k, и следовательно попадают в подерево B.
Что происходит, обычно? Чтобы вставить X, надо найти место для вставки. Поиск начинается с корня.
Далее надо вставить Y, мы знаем что Y > k, и нам не обязательно повторять весь поиск, начиная от корня. Достаточно поискать в B.
Аналогично, если у нас миллион отсортированных чисел - которые надо вставить. Совсем не обязательно, для каждого числа, повторять поиск от корня. Поиск можно возобновлять в какой-то конкретной ветке дерева.
Я не берусь точно взвешивать или проверять, сколько холостой работы происходит, когда мы добавляем каждое число в лоб. Это число будет равно суммарное длине всех путей дерева, до каждой вершины. Если грубо накидать в уме, допустим: это идеальное сбалансированное бинарное дерево, вставка происходит только в листья. В таком случае, листев не меньше чем N/2, а длина путей что-то вроде log2 N.
Таким образом для дерева в N вершин, мы перемалываем не менее (N log2 N) / 2 операций. Не знаю, насколько это много, на практике получается - что это не быстро. Тогда как по честному, процедура просто линейная.
Для решения, вовсе не обязательно повторять поиск в каких-то локальных вершинах. А делается это - так:
У нас есть огромный, заранее подготовленный, набор чисел для вставки и он отсортирован.
................... |
Допустим k - это корень, мы начинаем вставку от корня. В таком случае, мы можем разделить наш массив на два диапазона:
....L..... | K | .....R..... |
На практике, на вовсе не обязательно сортировать числа перед работой.
Числа можно разделять в каждом конкретном узле, без сортировки. Помните как qsort работает?
Возму rand-tree для затравки, как самый простой случай.
Я завел два класса:
Data // данные для вставки DataRange // диапазон данных в массиве данных для вставки data::Adjust // метод, который делит данные на два диапазона |
Далее работаем по аналогии с самим rand-tree
Node *RandTree::Insert(Node *node, Data &data, const DataRange &index) { if (!index.Count()) return node; // если в дереве нет ветки, лепим ветку целиком из данных // если ветка есть, то с какой-то вероятностью, один из её узлов станет корнем if (!node || rand() % (node->count + index.Count()) < index.Count()) return InsertRoot(node, data, index); // делим значения для вставки, на два диапазона DataRange index1, index2; data.Adjust(node->v, index, index1, index2); // рекурсия node->p1 = Insert(node->p1, data, index1); node->p2 = Insert(node->p2, data, index2); return node->FixCount(); } |
Node *RandTree::InsertRoot(Node *node, Data &data, const DataRange &index)
{
// если ветки нет, лепим целиком из данных
if (!node) return InsertNew(data, index);
DataRange index1, index2;
data.Adjust(node->v, index, index1, index2);
...
Node *p1 = InsertRoot(node->p1, data, index1);
Node *p2 = InsertRoot(node->p2, data, index2);
if (rand() % (index1.Count()+index2.Count()) < index1.Count() || !p2) {
...
} else {
...
}
return nullptr;
}
|
Node *RandTree::InsertNew(Data &data, const DataRange &index) { ... |
void Join(std::vector<Node *> &nodes, Node **result) { size_t s = nodes.size(); if (s == 1) { *result = nodes[0]; return; } size_t i1, i2; do { i1 = rand() % s; i2 = rand() % s; } while (i1 >= i2); Node *p1 = nodes[i1]; Node *p2 = nodes[i2]; if (rand() & 16) { nodes[i1] = p1->p2; if (!nodes[i1]) nodes.erase(nodes.begin() + i1); Join(nodes, &p1->p2); *result = p1; } else { nodes[i2] = p2->p1; if (!nodes[i2]) nodes.erase(nodes.begin() + i2); Join(nodes, &p2->p1); *result = p2; } } |
Для работы с диапазонами, мы можем заранее отсортировать данные или сортировать их в процессе спуска. По сути это одно и тоже, но вариант с предварительной сортировкой, почему-то работает быстрее. Возможно std::sort работает немного эффективнее, чем моё разбиение - в основном это связанно в с тем, что предварительная сортировка позволяет добиться более точной балансировки дерева, что сказывается уже в процессе построения.
Для разбиения я беру три прозвольных значения из массива, и выбираю среднее из трёх, как значение для разбиения.
Если мне не показалось, то множество построенное на подобном rand-tree, у меня отрабатывало сильно быстрее, чем std::unordered_set с предварительным reserve. Я не сравнивал разные реализации и операционные системы, но полагаю что хороший hash от обычного числа, явление само по себе не быстрое.
На этом мы закончим с rand-tree и передём с более сложным структурам (которые балансируются, не от балды).
2-4 / \ \ 1 3 5 |
2-4-5 / / 1 3 | 4 / \ 2 5 / \ 1 3 |
В нашем случае все элементы, попадают в листья, т.е. останавливаются на нулевой глубине. Далее, начинают применяться модифицированные варианты Skew и Split процедур. AA дерево, ничем не отличается от оригинального, не считая того, что ширина узлов 2-3 дерева, во время работы достигает не 2-3 вершин, а каких-то абсолютно произвольных величин. Соответственно работают и новые Split Skew процедуры.
| 1-2-3-4-5-6-7-8-9 / \ \ \ \ \ \ \ \ \ . . . . . . . . . . | | 1-2-3-4-5-6-7-8-9 / \ \ \ \ \ \ \ \ \ . . . . . . . . . . |
| 1-2-3-4-5-6-7-8-9 / \ \ \ \ \ \ \ \ \ . . . . . . . . . . | | 2-4-6-8 / \ \ \ \ 1 3 5 7 9 ............. | | 4 / \ 2 6-8 / \ / \ \ 1 3 5 7 9 ........... |
проще говоря, просто расщепляем (дробим) узлы, в обычном порядке.
Это делается с помощью рекурсивной процедуры. В процессе рекурсивного обхода дерева, мы находим заданные значения.
Рекурсивная процедура, получает на вход количество элементов, которое надо вытащить из ветки, на место удалённых значений.
Возвращает, заданное количество минимальных элементов, оторванных от ветки:
код не очень красивый, цитирую его очень приблизительно:
// c - сколько минимальных элементов надо выдрать и вернуть из ветки Node *AA_tree::Remove(Node *node, Data & data, DataRange &index, size_t c) { DataRange index1, index2; // del если текущий эл. удаляем bool del = data.Adjust(node->value, index, index1, index2); node->p1 = Remove(node->p1, data, index1, c); if (!node->p1 && up_stack.size() < c) { // вытаскиваем минимальные узлы дерева, пока они не будут в нужном количестве up_stack.Push(node); return Remove(node->p2, data, index2, c); } node->p2 = Remove(node->p2, data, index2, del ? c + 1 : c); if (!del) return node; if (up_stack.size() <= c) { // если в дочерней ветке на нашлось нужного числа узлов, удаляем текущий узел в лоб std::auto_ptr<Node> _(node); return node->p1; } Node *t = up_stack.Pop(); node->value = t->value; std::auto_ptr<Node> _(t); return node; } |
Жизнь осложняется тем, что разрывы между уровнями, теперь не в один элемент, а достигают произвольной величины. Некоторые ветки в дереве изчезают целиком.
А нашем случае, стаскивание отдельного значения вниз, попросту не ограничивается одним шагов.
Если вершина отрывается, от своих веток на три уровня, то её надо стащить на три уровня вниз.
Если после устранения разрыва, вершина не вписывается в структуру дерева, её придётся тащить ещё ниже, вплоть до самых листьев.
Для примера, покажу дерево из 15 значений, у которого целиком удалили левую ветку. Цифра 7 - совсем не вписывается в нормальную структуру дерева.
7 --level:3 / \ x 11 --level:2 / \ 9 13 --level:1 / \ / \ 8 10 12 14 --level:0 |
Если бы мы работали с одиночными значениями, то нам было бы достаточно опустить 7, на один уровень вниз. На нашем примере это не помогает, после спуска, у элемента по прежнему не хватает одной ветки:
7---11 --level:2 \ \ 9 13 --level:1 / \ / \ 8 10 12 14 --level:0 |
В нашем примере вершину придётся спускать до самого конца:
11 --level:2 / \ 9 13 --level:1 / \ / \ 7-8 10 12 14 --level:0 |
На этом и работает наша процедура коррекции. Спукаем вершину вниз, проверяем, если она по прежнему нарушает структуру, спукаем её ещё ниже.
Для наглядности, я убрал из кода предохрантели:
Node *AA_tree::Fix(Node *node) { while (node->p1->Level() < node->level - 1 || node->p2->Level() < node->level - 1) { // стаскиваем вершину пока есть разрыв node->level--; if (node->p2->Level() > node->level) node->p2->level = node->level; Value v = node->value; node = Skew(node); node->p2 = Skew(node->p2); node->p2->p2 = Skew(node->p2->p2); node = Split(node); node->p2 = Split(node->p2); // тащим ещё ниже, если он нарушает структуру node = Fix(node, v); } return node; } |
Небольшая уловка возникает, из-за того что нам надо проложать работать с вершиной после стаскивания, но мы не знаем где-то она находится, после Skew Split процедур, отслеживать это тяжело. Поэтому мы просто находим её по значению:
Node *AA_tree::Fix(Node *node, Value v) { if (node->value == v) return Fix(node); if (v < node->value) node->p1 = Fix(node->p1, v); else node->p2 = Fix(node->p2, v); return node; } |
Этой процедуры, полностью достаточного для того чтобы восстановить, структуру 2-3 дерева, после удаления любых узлов, в любом количестве.
При некоторой доработке, можно сделать так чтобы любое случайное дерево, превращалось в корректное 2-3 дерево, за один обход дерева.
Ссылки:
rand-tree-mul.cpp
aa-tree-mul.cpp