Подтвердить что ты не робот

Как создать максимально несбалансированные AVL-деревья

Я написал библиотеку языков языка AVL в качестве сортированных контейнеров общего назначения. Для целей тестирования я хотел бы иметь способ заполнить дерево, чтобы он был максимально несбалансированным, т.е. Чтобы он имел максимальную высоту для количества содержащихся в нем узлов.

У деревьев AVL есть свойство nice: если, начиная с пустого дерева, вы вставляете узлы в порядке возрастания (или убывания), дерево всегда точно сбалансировано (т.е. имеет минимальную высоту для заданного количества узлов), Одна последовательность целых ключей, которая генерирует точно сбалансированное дерево AVL T n для каждого числа узлов n, начиная с пустого дерева T 0, просто

  • k 1= 0
  • k n + 1= k n +1, т.е. k n= n-1

Я ищу (целую) последовательность целых ключей, которая при вставке в первоначально пустом дереве T 0 генерирует деревья AVL T 0..., T n, которые максимально сбалансированы un.

Меня также интересовало бы решение, в котором только последнее дерево, T n, максимально не сбалансировано (число узлов n будет параметром алгоритма).

Решение, удовлетворяющее условию

  • max (k 1,..., k n) - min (k 1,..., k n) + 1 ≤ 2 n

предпочтительнее, но строго не требуется. Целевой диапазон 4 n вместо 2 n может быть разумной целью.

Я не смог найти что-либо в Интернете относительно генерации, путем вставки, деревьев AVL максимальной высоты. Конечно, последовательность сгенерированных деревьев, которые я ищу, будет включать в себя все так называемые деревья Фибоначчи, которые являются деревьями AVL заданной глубины с минимальным количеством узлов. Смешно, английская Википедия даже не упоминает деревья Фибоначчи (или числа Фибоначчи!) В статье о деревьях AVL, в то время как в немецкой Википедии есть очень хорошая статья полностью посвященная их. Но я все еще в неведении относительно моего вопроса.

Приветствую вас.

4b9b3361

ОТВЕТЫ

Ответ 1

Основное решение

Деревья Фибоначчи имеют несколько свойств, которые могут быть использованы для формирования компактного дерева Фибоначчи:

  • Каждый node в дереве Фибоначчи сам по себе является деревом Фибоначчи.
  • Число узлов в дереве Фибоначчи высоты n равно F n + 2 - 1.
  • Число узлов между node и его левым дочерним числом равно числу узлов дочернего дочернего дочернего дочернего элемента node.
  • Число узлов между node и его правым дочерним числом равно количеству узлов в дочернем левом дочернем элементе node.

Без ограничения общности будем считать, что наше дерево Фибоначчи обладает следующим дополнительным свойством:

  • Если a node имеет высоту n, то левый дочерний элемент имеет высоту n-2, а правый ребенок имеет высоту n-1.

Объединяя эти свойства, мы обнаруживаем, что количество узлов между a node высоты n и его левого и правого детей равно F n-1 - 1, и мы можем использовать этот факт для создания компактного дерева Фибоначчи:

static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170};

void fibonacci_subtree(int root, int height, int *fib)
{
    if (height == 1) {
        insert_into_tree(root);
    } else if (height == 2) {
        insert_into_tree(root + *fib);
    } else if (height >= 3) {
        fibonacci_subtree(root - *fib, height - 2, fib - 2);
        fibonacci_subtree(root + *fib, height - 1, fib - 1);
    }
}

...

for (height = 1; height <= max_height; height++) {
    fibonacci_subtree(0, height, fibs + max_height - 1);
}

Этот алгоритм генерирует минимальное количество узлов, доступных для заданной высоты, а также дает минимально возможный диапазон. Вы можете сдвинуть область вокруг, сделав корень node чем-то отличным от нуля.

Компактный алгоритм заполнения

Основное решение создает только деревья Фибоначчи, которые всегда имеют F n + 2 - 1 узлы. Что делать, если вы хотите генерировать несимметричное дерево с различным количеством узлов, но при этом минимизируя диапазон?

В этом случае вам нужно сгенерировать следующее большее дерево Фибоначчи с несколькими изменениями:

  • Некоторое количество элементов в конце последовательности не будет вставлено.
  • Эти элементы создадут пробелы, и необходимо будет отслеживать местоположение этих пробелов.
  • Различие между узлами должно быть соответствующим образом уменьшено.

Здесь один подход, который все еще использует рекурсивный характер решения:

void fibonacci_subtree(int root, int height, int *fib, int num_gaps, bool prune_gaps)
{
    if(height < 1)
        return;
    if(prune_gaps && height <= 2) {
        if(!num_gaps) {
            if(height == 1) {
                insert_into_tree(root);
            } else if(height == 2) {
                insert_into_tree(root + *fib);
            }
        }
        return;
    }
    if(height == 1) {
        insert_into_tree(root);
    } else {
        int max_rr_gaps = *(fib - 1);
        int rr_gaps = num_gaps > max_rr_gaps ? max_rr_gaps : num_gaps;
        num_gaps -= rr_gaps;

        int max_rl_gaps = *(fib - 2);
        int rl_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
        num_gaps -= rl_gaps;

        int lr_gaps = num_gaps > max_rl_gaps ? max_rl_gaps : num_gaps;
        num_gaps -= lr_gaps;

        int ll_gaps = num_gaps;
        fibonacci_subtree(root - *fib + lr_gaps, height - 2, fib - 2, lr_gaps + ll_gaps, prune_gaps);
        fibonacci_subtree(root + *fib - rl_gaps, height - 1, fib - 1, rr_gaps + rl_gaps, prune_gaps);
    }
}

Основной цикл немного сложнее для размещения произвольного диапазона клавиш:

void compact_fill(int min_key, int max_key)
{
    int num_nodes = max_key - min_key + 1;
    int *fib = fibs;
    int max_height = 0;

    while(num_nodes > *(fib + 2) - 1) {
        max_height++;
        fib++;
    }

    int num_gaps = *(fib + 2) - 1 - num_nodes;

    int natural_max = *(fib + 1) - 1;
    int max_r_gaps = *(fib - 1);
    int r_gaps = num_gaps > max_r_gaps ? max_r_gaps : num_gaps;
    natural_max -= r_gaps;

    int root_offset = max_key - natural_max;

    for (int height = 1; height <= max_height; height++) {
        fibonacci_subtree(root_offset, height, fibs + max_height - 1, num_gaps, height == max_height);
    }
}

Закрытое решение формы

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

Слово Фибоначчи - это определенная последовательность двоичных цифр (или символов из любого двухбуквенного алфавита). Слово Фибоначчи формируется путем повторной конкатенации таким же образом, что числа Фибоначчи формируются путем повторного добавления.

Оказывается, закрытое решение для слова Фибоначчи:

static double phi = (1.0 + sqrt(5.0)) / 2.0;

bool fibWord(int n)
{
    return 2 + floor(n * phi) - floor((n + 1) * phi);
}

Вы можете использовать это закрытое решение для решения проблемы с помощью двух вложенных циклов:

// Used by the outer loop to calculate the first key of the inner loop
int outerNodeKey = 0;
int *outerFib = fibs + max_height - 1;

for(int height = 1; height <= max_height; height++) {

    int innerNodeKey = outerNodeKey;
    int *smallFib = fibs + max_height - height + 3; // Hat tip: @WalterTross

    for(int n = fibs[height] - 1; n >= 0; n--) {
        insert_into_tree(innerNodeKey);

        // Use closed-form expression to pick between two elements of the Fibonacci sequence
        bool smallSkip = 2 + floor(n * phi) - floor((n + 1) * phi);
        innerNodeKey += smallSkip ? *smallFib : *(smallFib + 1);
    }

    if(height & 0x1) {
        // When height is odd, add *outerFib.
        outerNodeKey += *outerFib;
    } else {
        // Otherwise, backtrack and reduce the gap for next time.
        outerNodeKey -= (*outerFib) << 1;
        outerFib -= 2;
    }
}

Ответ 2

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

Идея состоит в том, чтобы генерировать деревья Фибоначчи до заданной высоты (что должно быть известно заранее), полностью избегая всех вращений дерева. Промежуточные деревья сохраняются AVL-сбалансированными по выбору порядка вставки. Поскольку они имеют высоту нижнего из двух деревьев Фибоначчи, которые они связывают, они все максимально неуравновешены.

Вставки выполняются путем фактической вставки всех узлов в последовательность деревьев Фибоначчи, но для каждого виртуального дерева эффективно вставляются только узлы, которые являются поддеревами высоты 1. Это "инкрементные" узлы между двумя последовательными деревьями Фибоначчи.

Вот как это работает в случае max_height = 5:

insert 0
=> Fibonacci tree of height 1 (1 node):
                0
insert 8
=> Fibonacci tree of height 2 (2 nodes):
                0
                        8
insert -8
insert 12
=> Fibonacci tree of height 3 (4 nodes):
                0
       -8               8
                           12
insert -4
insert 4
insert 14
=> Fibonacci tree of height 4 (7 nodes):
                0
       -8               8
           -4       4      12
                             14
insert -12
insert -2
insert 6
insert 10
insert 15
=> Fibonacci tree of height 5 (12 nodes):
                0
       -8               8
  -12      -4       4      12
             -2       6  10  14
                              15

И вот код (упрощенный):

void fibonacci_subtree(int root, int height, int child_delta)
{
   if (height == 1) {
      insert_into_tree(root);
   } else if (height == 2) {
      insert_into_tree(root + child_delta);
   } else if (height >= 3) {
      fibonacci_subtree(root - child_delta, height - 2, child_delta >> 1);
      fibonacci_subtree(root + child_delta, height - 1, child_delta >> 1);
   }
}

...
   for (height = 1; height <= max_height; height++) {
      fibonacci_subtree(0, height, 1 << (max_height - 2));
   }


UPDATE

Решение by godel9 решает проблему распространения ключей этого решения. Вот результат кода godel9:

insert 0
=> Fibonacci tree of height 1 (1 node):
                0
insert 3
=> Fibonacci tree of height 2 (2 nodes):
                0
                        3
insert -3
insert 5
=> Fibonacci tree of height 3 (4 nodes):
                0
       -3               3
                            5
insert -2
insert 1
insert 6
=> Fibonacci tree of height 4 (7 nodes):
                0
       -3               3
           -2       1       5
                              6
insert -4
insert -1
insert 2
insert 4
insert 7
=> Fibonacci tree of height 5 (12 nodes):
                0
       -3               3
   -4      -2       1       5
             -1       2   4   6
                               7

И вот код в ближайшей к моей версии (здесь со статическим массивом fibs):

static int fibs[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, 17711, 28657, 46368, 75025, 121393, 196418, 317811, 514229, 832040, 1346269, 2178309, 3524578, 5702887, 9227465, 14930352, 24157817, 39088169, 63245986, 102334155, 165580141, 267914296, 433494437, 701408733, 1134903170 };

void fibonacci_subtree(int root, int height, int *fib)
{
   if (height == 1) {
      insert_into_tree(root);
   } else if (height == 2) {
      insert_into_tree(root + *fib);
   } else if (height >= 3) {
      fibonacci_subtree(root - *fib, height - 2, fib - 2);
      fibonacci_subtree(root + *fib, height - 1, fib - 1);
   }
}

...
   for (height = 1; height <= max_height; height++) {
      fibonacci_subtree(0, height, fibs + max_height - 1);
   }

Конечное дерево Фибоначчи высоты H имеет F H + 2 - 1 узел без "дыр" между значениями ключа и имеет k max - k root= F H + 1 - 1. Диапазон клавиш можно удобно расположить, если необходимо, путем смещения значения ключа корня и, при необходимости, обмена влево и вправо в алгоритме.

То, что остается нерешенным, - это компактное заполнение любого заданного диапазона ключей целыми ключами (в то время как тривиально для точно сбалансированных деревьев). С помощью этого алгоритма, если вы хотите создать максимально несбалансированное дерево с n узлов (с целыми ключами), где n не является числом Фибоначчи - 1, и вы хотите, чтобы малые возможные диапазоны ключей, вы можете найти первую высоту, которая может разместить n узлов, а затем запустить алгоритм для этой высоты, но остановка, когда n узлов были вставлены. Число "дырок" останется (в худшем случае около n/φ ≅ n/1,618).

В отличие от моего интуитивного понимания, когда я писал введение в это решение, эффективность этого алгоритма с или без улучшения важности уже была оптимальной, так как это O (n) (так что, когда вставки включены, он становится O (n log n)). Это связано с тем, что количество операций пропорционально сумме узлов всех деревьев Фибоначчи от T F 1= T 1 до T F H= T n, т.е. N = Σ h = 1... H (F h + 2 - 1) = F H + 4 - H - 1. Но два последовательных числа Фибоначчи имеют асимптотическое отношение φ ≅ 1,618, золотой коэффициент, так что N/n ≅ φ 2 ≅ 2.618. Вы можете сравнить это с полностью сбалансированными бинарными деревьями, где применяются очень похожие формулы, только с "логарифмом" 2 вместо φ.

Хотя я сомневаюсь, что было бы полезно избавиться от фактора φ 2 учитывая простоту текущего кода, все же интересно отметить следующее: когда вы добавляете "инкрементный" узлы любого промежуточного дерева Фибоначчи высоты h, разница между двумя последовательными ключами этого "границы Фибоначчи" (мой термин) является либо F H-h + 3, либо F H-h + 4, в своеобразном чередующемся шаблоне. Если бы мы знали правило генерации этих различий, мы могли бы заполнить дерево просто двумя вложенными циклами.

Ответ 3

Интересный вопрос. Похоже, у вас уже есть хорошее решение, но я бы нашел более комбинаторный подход.

Предположения:

  • Пусть U (n) представляет число узлов в максимально неуравновешенном дереве AVL высоты n.

  • U (0) = 0

  • U (1) = 1

  • U (n) = U (n-1) + U (n-2) + 1 при n >= 2 (т.е. корень node плюс два максимально несбалансированных поддерева)

  • Для удобства предположим, что U (n-1) всегда является левым поддеревом, а U (n-2) всегда правым.

  • Пусть каждый node будет представлен уникальной строкой, представляющей путь от корня до node. Корень node является строкой emptry, узлы уровня 1 - "L" и "R" , узлы уровня 2 - "LL", "LR", "RL" и "RR" и т.д.

Выводы:

  • Допустимая строка для node на уровне A в U (n) является символом A длинной и удовлетворяет неравенству: n - count ( "L" ) - 2 * count ( "R" ) >= 1

  • count ( "L" ) + count ( "R" ) = A или count ( "L" ) = A - count ( "R" )

  • Таким образом, count ( "R" ) <= n - A - 1

  • Мы можем использовать следующие функции для генерации всех допустимых путей на заданном уровне и для определения значения ключа в каждом node.

    void GeneratePaths(int height, int level)
{
  int rLimit = height - level - 1;
  GeneratePaths(height, rLimit, level, string.Empty, 0);
}

void GeneratePaths(int height, int rLimit, int level, string prefix, int prefixlen)
{
  if (prefixlen + 1 < level)
  {
    GeneratePaths(height, rLimit, level, prefix + "L", prefixlen + 1);
    if (rLimit > 0)
        GeneratePaths(height, rLimit - 1, level, prefix + "R", prefixlen + 1);
  }
  else if (prefixlen + 1 == level)
  {
    InsertNode(prefix + "L", height)
    if (rLimit > 0)
        InsertNode(prefix + "R", height);
  }
}

void InsertNode(string path, int height)
{
  int key = fibonacci(height);
  int index = height - 2;

  for (int i=0; i < path.length(), i++)
  {
    int difference = fibonacci(index);
    char c = path.charAt(i);
    if (c == 'L')
    {
      key -= difference;
      index -= 1;
    }
    else if (c == 'R')
    {
      key += difference;
      index -= 2;
    }
  }

  InsertKey(key);
}

Если вы используете эти функции для генерации дерева U (5), вы получите этот результат. (Обратите внимание, что клавиши на левом краю дерева соответствуют последовательности фибоначчи от 1 до 5,)

            5
      3           7
   2     4      6   8
  1 3   4      6
 1