He escrito unBiblioteca en lenguaje C de árboles AVL como contenedores clasificados de propósito general. Para fines de prueba, me gustaría tener una forma de rellenar un árbol para que se desequilibre al máximo, es decir, para que tenga la altura máxima para el número de nodos que contiene.

Los árboles AVL tienen la bonita propiedad de que si, a partir del árbol vacío, usted inserta nodos en orden ascendente (o descendente), el árbol siempre está exactamente equilibrado (es decir, tiene su altura mínima para un número dado de nodos). Una secuencia de teclas enteras que genera un árbol AVL T equilibrado exactamenten para cada número de nodos n, comenzando desde el árbol vacío T0, es simple

k1 = 0kn + 1 = kn+1, es decir, kn = n-1

Estoy buscando una secuencia (con suerte simple) de claves enteras que, cuando se insertan en el árbol inicialmente vacío T0, genera árboles AVL T0, ..., Tn que son todos al maximoNaciones Unidasequilibrado.

También me interesaría una solución donde solo el último árbol, Tn, está desequilibrado al máximo (el número de nodos n sería un parámetro del algoritmo).

Una solución que satisface la restricción.

max (k1, ... kn) - min (k1, ... kn) + 1 ≤ 2 n

Es preferible, pero no estrictamente requerido. Un rango clave de 4 n en lugar de 2 n puede ser un objetivo razonable.

No he podido encontrar nada en Internet con respecto a la generación, por inserción, de árboles AVL de altura máxima. Por supuesto, la secuencia de árboles generados que estoy buscando incluirá todos los llamados árboles de Fibonacci, que son los árboles AVL de una profundidad dada con el número mínimo de nodos. Curiosamente, la Wikipedia en inglés ni siquiera menciona los árboles de Fibonacci (¡ni los números de Fibonacci!) En el artículo sobre árboles AVL, mientras que la Wikipedia en alemán tiene una muy buenaartículo Completamente dedicado a ellos. Pero todavía estoy en la oscuridad con respecto a mi pregunta.

Los trucos del lenguaje C son los trucos.