Ich habe ein geschriebenC-Sprachbibliothek von AVL-Bäumen als sortierte Container für allgemeine Zwecke. Zu Testzwecken hätte ich gerne eine Möglichkeit, einen Baum so zu füllen, dass er maximal unausgeglichen ist, d. H. So, dass er die maximale Höhe für die Anzahl der darin enthaltenen Knoten hat.

AVL-Bäume haben die nette Eigenschaft, dass, wenn Sie ausgehend von dem leeren Baum Knoten in aufsteigender (oder absteigender) Reihenfolge einfügen, der Baum immer exakt ausgeglichen ist (d. H., Er hat seine Mindesthöhe für eine bestimmte Anzahl von Knoten). Eine Folge von Ganzzahlschlüsseln, die einen exakt ausgeglichenen AVL-Baum T erzeugtn für jede Anzahl von Knoten n, beginnend mit dem leeren Baum T0, ist einfach

k1 = 0kn + 1 = kn+1, d. H. Kn = n-1

Ich suche eine (hoffentlich einfache) Folge von Integer-Schlüsseln, die in den anfangs leeren Baum T eingefügt werden0, erzeugt AVL-Bäume T0, ..., Tn das sind alle maximalunausgewogen.

Mich würde auch eine Lösung interessieren, bei der nur der letzte Baum, Tnist maximal unsymmetrisch (die Anzahl der Knoten n wäre ein Parameter des Algorithmus).

Eine Lösung, die die Bedingung erfüllt

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

ist vorzuziehen, aber nicht unbedingt erforderlich. Ein Schlüsselbereich von 4 n anstelle von 2 n kann ein vernünftiges Ziel sein.

Ich konnte im Internet nichts über die Erzeugung von AVL-Bäumen mit maximaler Höhe durch Einfügen finden. Natürlich werden in der von mir gesuchten Folge generierter Bäume alle sogenannten Fibonacci-Bäume enthalten sein, also die AVL-Bäume einer bestimmten Tiefe mit der minimalen Anzahl von Knoten. Lustigerweise erwähnt die englische Wikipedia im Artikel über AVL-Bäume nicht einmal Fibonacci-Bäume (noch Fibonacci-Zahlen!), Während die deutsche Wikipedia einen sehr guten hatArtikel ganz auf sie gewidmet. Aber ich bin immer noch im Dunkeln über meine Frage.

C-Sprach-Bit-Twiddling-Hacks sind willkommen.