Множественная вставка в деревья
или бинарные деревья - оффлайн

Проблема:

Чтобы озучить проблему, приведу небольшой пример из жизни, с которым много раз сталкивался.

Допустим:

Если упрощать совсем грубо, то у нас есть какое-то двоичное дерево поиска, нам надо вставить в него огромное количество значений:

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

Мы спускаемся в ветку A, с отрезком L, и в ветку B, с отрезком R. Далее, процесс повторяется рекурсивно. Кроме того его можно сделать параллельным (т.е. в разных потоках).

На практике, на вовсе не обязательно сортировать числа перед работой. Числа можно разделять в каждом конкретном узле, без сортировки. Помните как qsort работает?






Балансировка деревьев, offline

AVL - деревья

Не проблема, но я, это пропущю.

Рандомизированные деревья

[введение rand-tree]

Возму 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();
}

Если мы вставляем одиночное значение в ветку с count узлов, то с вероятностью 1/(count+1) - оно станет корнем ветки. Если мы вставляем n узлов, то с вероятностью 1/(count+n) - один из них новый корень ветки.
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) 
{
  ...
создание ветки из данных. Тут можно поступить просто, и накидать данные в дерево, в случайном порядке. Но это будет именно то, с чем мы боролись, множественный поиск от корня ветки. Поэтому я сделал по другому и скорость не сравнивал. Если интересно смотрите код.

Технические моменты:

Множественное удаление я не делал. Намекну просто про процедуру многопутевого join, пути в который можно добавлять не ходу (если соблюдается алфавитный порядок вершин).
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 и передём с более сложным структурам (которые балансируются, не от балды).






АА дерево, офлайн

[введение aa-tree]

Вставка

работает, так же как в остальных случаях. По другому работает коррекция дерева. В оригинальном AA-tree применяются две процедуры Skew и slit:

  2-4
 / \ \
1   3 5

  2-4-5
 / /
1 3
    4
   / \
  2   5
 / \
1   3

В нашем случае все элементы, попадают в листья, т.е. останавливаются на нулевой глубине. Далее, начинают применяться модифицированные варианты Skew и Split процедур. AA дерево, ничем не отличается от оригинального, не считая того, что ширина узлов 2-3 дерева, во время работы достигает не 2-3 вершин, а каких-то абсолютно произвольных величин. Соответственно работают и новые Split Skew процедуры.

Skew процедура:

Переупорядочивает элементы узла, имеющего произвольную ширину:

        |
  1-2-3-4-5-6-7-8-9
 / \ \ \ \ \ \ \ \ \
.   . . . . . . . . .
  |
  1-2-3-4-5-6-7-8-9
 / \ \ \ \ \ \ \ \ \
.   . . . . . . . . .

Split процедура:

Разбивает широкий узел на много мелких узлов, приемлемой ширины, образуя один широкий узел, уровнем выше. Вытаскивает каждый второй элемент наверх (можно брать не каждый второй, а каждый третий).

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

Восстановление формы:

Восстановление формы 2-3 дерева, после удаления любых произвольных узлов, это самая сложная часть процесса. Процесс чем-то похож на удаление одиночного узла. Находим разрывы между уровнями. Стаскиваем элементы на более низкие уровни, чтобы сравнять уровни. Расщепляем слишком большие узлы.

Жизнь осложняется тем, что разрывы между уровнями, теперь не в один элемент, а достигают произвольной величины. Некоторые ветки в дереве изчезают целиком.

А нашем случае, стаскивание отдельного значения вниз, попросту не ограничивается одним шагов.
Если вершина отрывается, от своих веток на три уровня, то её надо стащить на три уровня вниз.
Если после устранения разрыва, вершина не вписывается в структуру дерева, её придётся тащить ещё ниже, вплоть до самых листьев.

Для примера, покажу дерево из 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 дерево, за один обход дерева.

Одиночные операции

Есть большой простор для оптимизации одиночных операций. Например, при удалении вершин, можно не удалять узлы, а помечать их как удалённые. Оптимизацию проводить только иногда, и оптимизацию можно размазать по времени. Если мы удалили половину значений из дерева, время поиска по дереву увеличивается, только на один шаг. А выигрыш, по времени огромный.

эпилог:

В целом, это всё. Конкретно для AA-дерева, можно сделать более сложную в эффективную реализацию. Можно по другому организовать стаcкивание вершин после удаления. Тут я привожу, только первые простые наброски:

Ссылки:
rand-tree-mul.cpp
aa-tree-mul.cpp