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

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

 = 0 КБп + 1 = кн+1, т.е. = n-1I '

m ищет (надеюсь, простую) последовательность целочисленных ключей, которая при вставке в изначально пустое дерево T0, генерирует AVL деревья T0, ..., Tn которые все максимальноООНсбалансирован.

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

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

макс (k1, ..., кн) - мин (к1, ..., кн) + 1 ≤ 2 н

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

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

С языком немного вертеться хаки приветствуются.