Как с учетом заранее определенного набора ключей переупорядочить ключи так, чтобы при вставке в B-дерево использовалось минимальное количество узлов?

Приведенный ниже алгоритм должен работать для B-деревьев с минимальным количеством ключей в node = d и максимальным = 2 * d. Я полагаю, что его можно обобщить для 2 * d + 1 максимальных ключей, если известен способ выбора медианы.

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

Метод основан на идее помещения ключей в любой неполный лист или, если все листья заполнены, чтобы поместить ключ под нижний неполный узел.

Точнее, дерево, сгенерированное предлагаемым алгоритмом, удовлетворяет следующим требованиям: иметь минимально возможную высоту; У него не более двух неполных узлов на каждом уровне. (Это всегда два самых правых узла.)

Поскольку мы знаем, что количество узлов на любом уровне, за исключением корня, строго равно сумме количества узлов и общего числа ключей на уровне выше, мы можем доказать, что не существует действительной перестановки узлов между уровнями, которая уменьшает общее количество узлов. Например, увеличение количества ключей, вставленных выше любого определенного уровня, приведет к увеличению количества узлов на этом уровне и, как следствие, увеличению общего количества узлов. Хотя любая попытка уменьшить количество ключей выше определенного уровня приведет к уменьшению количества узлов на этом уровне и не сможет вместить все ключи на этом уровне без увеличения высоты дерева. Также очевидно, что расположение ключей на каком-то определенном уровне является одним из оптимальных. Используя рассуждения выше, можно также построить более формальное доказательство посредством математической индукции.

Идея состоит в том, чтобы хранить список счетчиков (размер списка не больше высоты дерева), чтобы отслеживать, сколько ключей добавлено на каждом уровне. Как только я добавляю d ключей на некоторый уровень, это означает, что узел заполнен наполовину, созданный на этом уровне, и если есть достаточно ключей, чтобы заполнить другую половину этого узла, мы должны пропустить эти ключи и добавить корень для более высокого уровня. Таким образом, корень будет помещен точно между первой половиной предыдущего поддерева и первой половиной следующего поддерева, это вызовет разделение, когда корень займет его место, и две половины поддерева разделятся. Место для пропущенных ключей будет безопасным, пока мы перебираем ключи большего размера, и его можно будет заполнить позже.

Вот почти рабочий (псевдо) код, массив нужно отсортировать:

PushArray(BTree bTree, int d, key[] Array)
{
    List<int> counters = new List<int>{0};
    //skip list will contain numbers of nodes to skip 
    //after filling node of some order in half
    List<int> skip  = new List<int>();
    List<Pair<int,int>> skipList = List<Pair<int,int>>();

    int i = -1;
    while(true)
    {     
       int order = 0;
       while(counters[order] == d) order += 1;
       for(int j = order - 1; j >= 0; j--) counters[j] = 0;

       if (counters.Lenght <= order + 1) counters.Add(0);
       counters[order] += 1;

       if (skip.Count <= order)
              skip.Add(i + 2);    
       if (order > 0)
           skipList.Add({i,order}); //list of skipped parts that will be needed later
       i += skip[order];

       if (i > N) break;

       bTree.Push(Array[i]);
    }

    //now we need to add all skipped keys in correct order
    foreach(Pair<int,int> p in skipList)
    {
        for(int i = p.2; i > 0; i--)
            PushArray(bTree, d, Array.SubArray(p.1 + skip[i - 1], skip[i] -1))
    }
}

Пример:

Вот как должны быть расположены числа и соответствующие ключи счетчиков для d = 2 при первом проходе через массив. Я пометил ключи, которые были вставлены в B-дерево во время первого прохода (до цикла с рекурсией), с помощью «o» и пропустил с помощью «x».

                                                              24
        4         9             14             19                            29 
0 1 2 3   5 6 7 8   10 11 12 13    15 16 17 18    20 21 22 23    25 26 27 28    30 ...
o o x x o o o x x o  o  o  x  x  x  x  x  x  x  x  x  x  x  x  o  o  o  x  x  o  o ...
1 2     0 1 2     0  1  2                                      0  1  2        0  1 ...
0 0     1 1 1     2  2  2                                      0  0  0        1  1 ...
0 0     0 0 0     0  0  0                                      1  1  1        1  1 ...
skip[0] = 1 
skip[1] = 3 
skip[2] = 13

Поскольку мы не перебираем пропущенные ключи, у нас есть временная сложность O (n) без добавления самого B-Tree и для отсортированного массива;

В этой форме может быть неясно, как это работает, когда недостаточно ключей для заполнения второй половины узла после пропущенного блока, но мы также можем избежать пропуска всех ключей skip [order], если общая длина массива меньше ~ i + 2 * skip [order] и skip вместо клавиш skip [order - 1], такая строка может быть добавлена ​​после изменения счетчиков, но до изменения переменной i:

while(order > 0 && i + 2*skip[order] > N) --order;

это будет правильно, потому что если общее количество ключей на текущем уровне меньше или равно 3 * d, они все равно будут правильно разделены, если добавить их в исходном порядке. Это приведет к немного иному расположению ключей между двумя последними узлами на некоторых уровнях, но не нарушит никаких описанных требований и, возможно, упростит понимание поведения.

Возможно, есть смысл найти какую-нибудь анимацию и посмотреть, как она работает, вот последовательность, которая должна быть сгенерирована в диапазоне 0..29: 0 1 4 5 6 9 10 11 24 25 26 29 / конец первого прохода < / em> / 2 3 7 8 14 15 16 19 20 21 12 13 17 18 22 23 27 28