Algorithmus zum Auflisten aller Binärbäume einer bestimmten Höhe

7

Ich habe versucht, einen Algorithmus zu finden, um alle Binärbäume einer bestimmten Höhe .h

Beachten Sie, dass ich nicht versuche, sie zu zählen: Die Anzahl solcher Bäume ist im OEIS ( A001699 ) angegeben.

Alle Algorithmen, die ich sehen konnte, listen alle Binärbäume für eine bestimmte Anzahl von Knoten auf. Eine sehr ineffiziente Methode zur Lösung des Problems würde darin bestehen, alle Bäume mit einer Anzahl von Knoten zwischen und überprüfen. Dies ist jedoch überhaupt nicht großartig.h+12h+11

Alle Hinweise oder Referenzen wäre sehr dankbar.

Shiwen Yao
quelle
3
Die Wiederholungsformeln implizieren einen solchen Algorithmus. (In der Tat nicht die Formeln selbst, sondern ihr Beweis.)
Yuval Filmus
@ YuvalFilmus Danke für deinen Kommentar. Meinen Sie einen Beweis wie den (unter Verwendung von OGFs), der unter math.stackexchange.com/questions/1183643/… bereitgestellt wird ? Ich bin völlig neu auf dem Gebiet - tut mir leid, dass ich langsam bin.
Shiwen Yao
Ihr Link hat auch andere Formeln. Jede vernünftige Wiederholung würde funktionieren.
Yuval Filmus

Antworten:

2

Folgen Sie, wie in den Kommentaren angedeutet, einfach der rekursiven Struktur von Binärbäumen.

Wir erstellen eine Funktion listbt(h), die alle Binärbäume mit exakter Höhe auflistet h.

type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
|   listbt h = {
  result = []
  for T in (listbt h-1) {
    for k in (0..h-1) {
      for t in (listbt k) {
         result += Node(T, t)
         result += Node(t, T) if k < h-1 || t != T
      }
    }
  }
  return result
}

Die Korrektheit folgt mit einem elementaren induktiven Beweis h.

Wenn Sie sich die Ergebnisse merken listbt, wird dies so effizient wie möglich sein. Die schiere Anzahl der Bäume und damit die Anzahl der Schecks t != Tdominieren.

Beachten Sie, dass Sie die Größe der Ausgabe erheblich reduzieren können , wenn Sie Term Sharing verwenden (dh nur Link tund TIn, Node(t, T)aber nicht kopieren). Dies ist jedoch nur dann sinnvoll, wenn Ihre BTreeImplementierung unveränderlich ist.

Raphael
quelle
-1

Mein erster Gedanke war, dass dies nur Bäume betrifft, die aus Pfaden der Länge h gebaut wurden, die isomorph zu h-Bit-Ganzzahlen sind, aber dies ist nur eine Teilmenge dessen, was benötigt wird. Beginnen Sie jedoch damit, dass Sie jeden nicht vollständigen Zwischenknoten mit Bäumen füllen müssen, die nicht bis zur Blattebene reichen.

Das heißt: Zählen Sie die nicht leeren Mengen von h-Bit-Ganzzahlen auf und konvertieren Sie sie in Bäume. Fügen Sie dann für jeden Baum T für jeden nicht vollständigen Nicht-Blatt-Knoten N (dh nur ein Kind, da er sich per Definition bereits auf einem Pfad zu mindestens einem Blatt befindet) alle möglichen Teilbäume hinzu, die die Blattebene nicht erreichen (Höhe <Höhe (N) -1, einschließlich des leeren Baums). Geben Sie dann das kartesische Produkt über alle N in T aus.22h1

Meine Behauptung ist, dass dies alle Bäume erzeugt und nicht zweimal erzeugt, da die Bedingung, dass das Blatt nicht erreicht wird, es unmöglich macht, mit einem T zu beginnen und es in ein anderes T 'mit einem anderen Blatt der Tiefe h umzuwandeln.

KWillets
quelle
1
Das ist wirklich ineffizient.
Yuval Filmus