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

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

Деревья AVL обладают хорошим свойством: если, начиная с пустого дерева, вы вставляете узлы в порядке возрастания (или убывания), дерево всегда точно сбалансировано (т. Е. Имеет минимальную высоту для заданного количества узлов). Одна последовательность целых ключей, которая генерирует точно сбалансированное дерево 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 , которые все максимально не сбалансированы.

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

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

  • max (k 1 , …, k n ) – min (k 1 , …, k n ) + 1 ≤ 2 n

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

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

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

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

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

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

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

  1. Если узел имеет высоту n, то левый ребенок имеет высоту n-2, а правый ребенок имеет высоту n-1.

Объединяя эти свойства, мы обнаруживаем, что число узлов между узлом высоты 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); } 

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

Алгоритм компактного заполнения

Основное решение дает только деревья Фибоначчи, которые всегда имеют 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; } } 

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

Идея состоит в том, чтобы генерировать деревья Фибоначчи до определенной высоты (что должно быть известно заранее), полностью избегая всех вращений дерева. Промежуточные деревья сохраняются 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)); } 

ОБНОВИТЬ

Решение 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); } 

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

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

Вопреки тому, что было моим интуитивным пониманием, когда я написал введение в это решение, эффективность этого алгоритма с или без значительного улучшения godel9 уже оптимальна, так как это 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 , в своеобразном чередующемся шаблоне. Если бы мы знали правило генерации этих различий, мы могли бы заполнить дерево просто двумя вложенными циклами.

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

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

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

  • U (0) = 0

  • U (1) = 1

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

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

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

Выводы:

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

  • count (“L”) + count (“R”) = A или count (“L”) = A – count (“R”)

  • Таким образом, счетчик («R») <= n - A - 1

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

     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