Eu escrevi umBiblioteca de linguagem C de árvores AVL como contêineres classificados de propósito geral. Para fins de teste, gostaria de ter uma maneira de preencher uma árvore de forma que ela esteja desbalanceada ao máximo, ou seja, de modo que tenha a altura máxima para o número de nós que ela contém.

As árvores AVL têm a boa propriedade de que se, a partir da árvore vazia, você inserir nós em ordem crescente (ou decrescente), a árvore estará sempre exatamente equilibrada (ou seja, terá sua altura mínima para um determinado número de nós). Uma sequência de chaves inteiras que gera uma árvore AVL exatamente balanceadan para cada número de nós n, a partir da árvore vazia T0, e simples

k1 = 0kn + 1 = kn+1, ou seja, kn = n-1

Eu estou procurando por uma sequência (esperançosamente simples) de chaves inteiras que, quando inseridas na árvore inicialmente vazia T0, gera árvores AVL T0... Tn que são todos maximamenteunequilibrado.

Eu também estaria interessado em uma solução onde apenas a última árvore, Tn, é maximamente desbalanceado (o número de nós n seria um parâmetro do algoritmo).

Uma solução que satisfaz a restrição

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

é preferível, mas não estritamente necessário. Um intervalo de chaves de 4 n em vez de 2 n pode ser um alvo razoável.

Eu não consegui encontrar nada na Internet sobre a geração, por inserção, de árvores AVL de altura máxima. É claro que a sequência de árvores geradas que estou procurando incluirá todas as chamadas árvores Fibonacci, que são as árvores AVL de uma determinada profundidade com o número mínimo de nós. Curiosamente, a Wikipédia inglesa nem sequer menciona as árvores de Fibonacci (nem os números de Fibonacci!) No artigo sobre as árvores AVL, enquanto a Wikipédia em alemão tem uma muito boaartigo completamente dedicado a eles. Mas ainda estou no escuro a respeito da minha pergunta.

Os hacks de bit de linguagem C são bem-vindos.