Дерево Фибоначчи

А это точно не тоже самое, что Фибонначиева куча?

К сожалению - нет

Дерево Фибоначчи это не структура данных, а частный случай устройства бинарного дерева, который используется в доказательствах некоторых оценок, и иногда получается при натуральном построении АВЛ-дерева.

Поэтому вопрос не имеет смысла, для поддержания такого дерева с произвольными элементами не существует алгоритма. Это всё равно, что просить реализацию для полного бинарного дерева.

Кроме того, например, для трёх элементов не существует д.ф. в принципе: зафиксировав корень, мы можем получить высоты детей либо 1-1, либо 2-0, в обоих случаях разница между ними не равна единице.

Но я допускаю существование алгоритма построения фиксированного д.ф. по набору элементов, количество которых допустимо для построения дерева. Нужен этот алгоритм?

Это - максимально несбалансированное AVL-дерево, если коротко.

То есть после каждой операции над деревом (вставка, удаление), чтобы получить д.ф., нужно переформировывать дерево с нуля, при услови, что количество вершин удовлетворяет свойству, правильно?

Нужен этот алгоритм?

Да, почему нет.

Дерево Фибоначчи сбалансировано по определению. Но чтоб его балансировать недостаточно просто совершать повороты

То есть после каждой операции над деревом (вставка, удаление), чтобы получить д.ф., нужно переформировывать дерево с нуля, при услови, что количество вершин удовлетворяет свойству, правильно?

Для такого дерева нельзя вводить классические операции вроде «вставить/удалить один элемент», так как тогда количество элементов будет неподходящим для д.ф.

Можно вводить операции вида «вставить 8 элементов в 12-элементное дерево», но я не представляю, зачем такие могут быть нужны, и как их реализовывать за лучшую асимптотику, чем полное перестроение дерева.

Перебалансировать или поворачивать д.ф. нельзя, так как тогда оно сразу перестанет быть д.ф. Кроме того, для заданных элементов д.ф. единственно.

Алгоритм построения дерева по элементам стандартный, но с пониманием требуемого количества элементов в каждом поддереве. Набросал что-то такое: https://ideone.com/sz4cRo . Разрешаю царю устроить мне кодревью :-)

Спасибо. Интересно, конечно, ваш код читать было)

Значит, заполнять дерево значениями пользователя без их предварительной сортировки или вставлять в дерево элементы таким образом, чтобы при Ф(h+2)-1 (Ф - число фиб. на позиции h+2, где h - высота дерева) вершинах ВСЕГДА получалось д.ф невозможно?

На мой взгляд — невозможно, но гарантировать не могу.