Napisałem aBiblioteka języka C drzew AVL jako sortowane pojemniki ogólnego przeznaczenia. Dla celów testowych chciałbym mieć sposób na wypełnienie drzewa tak, aby było maksymalnie niezrównoważone, tj. Tak, aby miało maksymalną wysokość dla liczby węzłów, które zawiera.

Drzewa AVL mają ładną właściwość, że jeśli zaczynając od pustego drzewa, wstawia się węzły w porządku rosnącym (lub malejącym), drzewo jest zawsze dokładnie zbalansowane (tj. Ma minimalną wysokość dla danej liczby węzłów). Jedna sekwencja klawiszy całkowitych, która generuje dokładnie zbalansowane drzewo AVL Tn dla każdej liczby węzłów n, począwszy od pustego drzewa T0jest po prostu

k1 = 0kn + 1 = kn+1, tj. Kn = n-1

Szukam (miejmy nadzieję prostej) sekwencji kluczy całkowitych, które po wstawieniu do początkowo pustego drzewa T0, generuje drzewa T AVL0, ..., Tn które są maksymalnieunzrównoważony.

Byłbym również zainteresowany rozwiązaniem, w którym tylko ostatnie drzewo, Tn, jest maksymalnie niezrównoważony (liczba węzłów n byłaby parametrem algorytmu).

Rozwiązanie spełniające ograniczenie

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

jest preferowany, ale nie jest wymagany. Rozsądny cel może mieć zakres 4 n zamiast 2 n.

Nie udało mi się znaleźć niczego w Internecie, jeśli chodzi o generowanie przez wstawianie drzew AVL o maksymalnej wysokości. Oczywiście sekwencja wygenerowanych drzew, które szukam, będzie zawierać wszystkie tak zwane drzewa Fibonacciego, które są drzewami AVL o określonej głębokości z minimalną liczbą węzłów. Co ciekawe, angielska Wikipedia nie wspomina nawet drzew Fibonacciego (ani liczb Fibonacciego!) W artykule o drzewach AVL, podczas gdy niemiecka Wikipedia ma bardzo dobryartykuł całkowicie im poświęcony. Ale wciąż jestem w ciemności, jeśli chodzi o moje pytanie.

Mile widziane hacki w języku C.