Finden Sie die Anzahl der möglichen binären Suchbaum

Question

Angenommen, wir haben die Schlüssel 1,2,3,4,5,6,7. Ich muss die Gesamtzahl der möglichen binären Suchbäume finden, so dass die Höhe des binären Suchbaums 6 ist. Die Antwort lautet . Aber ich bin nicht in der Lage, ein Muster zu finden, um die Antwort mathematisch abzuleiten. Nur durch Brute-Force-Zeichnen sind alle möglichen Bäume nicht möglich.

Ein einfaches Beispiel für mögliche Bäume sind unsymmetrische Bäume, bei denen die Schlüssel in aufsteigender und absteigender Reihenfolge eingefügt werden. Beide Bäume werden von Höhe 6 sein. Aber wie erreicht man die Gesamtsumme 64?

Answer 1

Dies kann durch Konstruktion nachgewiesen werden.

Nehmen wir an,
F (n) = Anzahl binärer Suchbaum mit höhen n für n+1 Zahlen
Claim: F(n) = 2^n

Beweis:

F(0) = 1 (by construction) 
F(1) = 2 (by construction) 

Nun berechnen F (n), dann kann entweder die kleinste Zahl oder die größte Zahl die Wurzel des Baumes sein. Verbleibende n Zahlen müssen in der Teilstruktur auf der linken Seite angeordnet sein (wenn größte Zahl Wurzel ist) oder nach rechts (wenn kleinste Zahl ist root)

So

F(n) = 2*F(n-1) 
F(n) = 2^n